An optimization problem for continuous submodular functions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F21%3A00540823" target="_blank" >RIV/67985556:_____/21:00540823 - isvavai.cz</a>

Výsledek na webu

<a href="http://www.cs.ubbcluj.ro/~studia-m/index.php/journal/article/view/1152" target="_blank" >http://www.cs.ubbcluj.ro/~studia-m/index.php/journal/article/view/1152</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.24193/subbmath.2021.1.17" target="_blank" >10.24193/subbmath.2021.1.17</a>

Jazyk výsledku

angličtina

Název v původním jazyce

An optimization problem for continuous submodular functions

Popis výsledku v původním jazyce

Real continuous submodular functions, as a generalization of the corresponding discrete notion to the continuous domain, gained considerable attention recently. The analog notion for entropy functions requires additional properties: a real multivariate function defined on the non-negative orthant of dimension n is entropy-like (EL) if it is submodular, takes zero at zero, non-decreasing, and has the Diminishing Returns property. Motivated by problems concerning the Shannon complexity of multipartite secret sharing, a special case of the following general optimization problem is considered: find the minimal cost of those EL functions which satisfy certain constraints. In our special case the cost of an EL function is the maximal value of the n partial derivatives at zero. Another possibility could be the supremum of the function range. The constraints are specified by a smooth bounded surface S cutting off a downward closed subset. An EL function is feasible if at the internal points of S the left and right partial derivatives of the function differ by at least one. A general lower bound for the minimal cost is given in terms of thennormals of the surface S. The bound is tight when S is linear. In the two-dimensional case the same bound is tight for convex or concave S. It is shown that the optimal EL function is not necessarily unique. The paper concludes with several open problems.

Název v anglickém jazyce

An optimization problem for continuous submodular functions

Popis výsledku anglicky

Real continuous submodular functions, as a generalization of the corresponding discrete notion to the continuous domain, gained considerable attention recently. The analog notion for entropy functions requires additional properties: a real multivariate function defined on the non-negative orthant of dimension n is entropy-like (EL) if it is submodular, takes zero at zero, non-decreasing, and has the Diminishing Returns property. Motivated by problems concerning the Shannon complexity of multipartite secret sharing, a special case of the following general optimization problem is considered: find the minimal cost of those EL functions which satisfy certain constraints. In our special case the cost of an EL function is the maximal value of the n partial derivatives at zero. Another possibility could be the supremum of the function range. The constraints are specified by a smooth bounded surface S cutting off a downward closed subset. An EL function is feasible if at the internal points of S the left and right partial derivatives of the function differ by at least one. A general lower bound for the minimal cost is given in terms of thennormals of the surface S. The bound is tight when S is linear. In the two-dimensional case the same bound is tight for convex or concave S. It is shown that the optimal EL function is not necessarily unique. The paper concludes with several open problems.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GA19-04579S" target="_blank" >GA19-04579S: Struktury podmíněné nezávislosti: metody polyedrální geometrie</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2021

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Studia Universitatis Babes-Bolyai Mathematica

ISSN

0252-1938

e-ISSN

2065-961X

Svazek periodika

66

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

RO - Rumunsko

Počet stran výsledku

12

Strana od-do

211-222

Kód UT WoS článku

000631641400018

EID výsledku v databázi Scopus

2-s2.0-85103502175