Approximate separable multichoice optimization over monotone systems

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Approximate separable multichoice optimization over monotone systems
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project
<a href="/en/project/GA17-09142S" target="_blank" >GA17-09142S: Modern algorithms: New challenges of complex data sets</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)