Approximate separable multichoice optimization over monotone systems

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10455312" target="_blank" >RIV/00216208:11320/22:10455312 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mIMnrhuiN0" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=mIMnrhuiN0</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.disopt.2021.100629" target="_blank" >10.1016/j.disopt.2021.100629</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Approximate separable multichoice optimization over monotone systems

Popis výsledku v původním jazyce

With each separable optimization problem over a given set of vectors is associated its multichoice counterpart which involves choosing n rather than one solutions from the set so as to maximize the given separable function over the sum of the chosen solutions. Such problems have been studied in various contexts under various names, such as load balancing in machine scheduling, congestion routing, minimum shared and vulnerable edge problems, and shifted optimization. Separable multichoice optimization has a very broad expressive power and can be hard already for explicitly given sets of binary points. In this article we consider the problem over monotone systems, also called independence systems. Typically such a system has exponential size, and we assume that it is presented implicitly by a linear optimization oracle. Our main results for separable multichoice optimization are the following. First, the problem over any monotone system with any separable concave function can be approximated in polynomial time with a constant approximation ratio which is independent of n. Second, the problem over any monotone system with an arbitrary separable function can be approximated in polynomial time with an approximation ratio of 1/(O(log n)). (C) 2021 Elsevier B.V. All rights reserved.

Název v anglickém jazyce

Approximate separable multichoice optimization over monotone systems

Popis výsledku anglicky

With each separable optimization problem over a given set of vectors is associated its multichoice counterpart which involves choosing n rather than one solutions from the set so as to maximize the given separable function over the sum of the chosen solutions. Such problems have been studied in various contexts under various names, such as load balancing in machine scheduling, congestion routing, minimum shared and vulnerable edge problems, and shifted optimization. Separable multichoice optimization has a very broad expressive power and can be hard already for explicitly given sets of binary points. In this article we consider the problem over monotone systems, also called independence systems. Typically such a system has exponential size, and we assume that it is presented implicitly by a linear optimization oracle. Our main results for separable multichoice optimization are the following. First, the problem over any monotone system with any separable concave function can be approximated in polynomial time with a constant approximation ratio which is independent of n. Second, the problem over any monotone system with an arbitrary separable function can be approximated in polynomial time with an approximation ratio of 1/(O(log n)). (C) 2021 Elsevier B.V. All rights reserved.

Druh

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

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA17-09142S" target="_blank" >GA17-09142S: Moderní algoritmy: Nové výzvy komplexních dat</a><br>

Návaznosti

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

Rok uplatnění

2022

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

Discrete Optimization

ISSN

1572-5286

e-ISSN

1873-636X

Svazek periodika

44

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

100629

Kód UT WoS článku

000832713200006

EID výsledku v databázi Scopus

—