License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.11
URN: urn:nbn:de:0030-drops-111320
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11132/
Go to the corresponding LIPIcs Volume Portal

Bampis, Evripidis ; Escoffier, Bruno ; Schewior, Kevin ; Teiller, Alexandre

Online Multistage Subset Maximization Problems

pdf-format:
LIPIcs-ESA-2019-11.pdf (0.5 MB)

Abstract

Numerous combinatorial optimization problems (knapsack, maximum-weight matching, etc.) can be expressed as subset maximization problems: One is given a ground set N={1,...,n}, a collection F subseteq 2^N of subsets thereof such that the empty set is in F, and an objective (profit) function p: F -> R_+. The task is to choose a set S in F that maximizes p(S). We consider the multistage version (Eisenstat et al., Gupta et al., both ICALP 2014) of such problems: The profit function p_t (and possibly the set of feasible solutions F_t) may change over time. Since in many applications changing the solution is costly, the task becomes to find a sequence of solutions that optimizes the trade-off between good per-time solutions and stable solutions taking into account an additional similarity bonus. As similarity measure for two consecutive solutions, we consider either the size of the intersection of the two solutions or the difference of n and the Hamming distance between the two characteristic vectors.
We study multistage subset maximization problems in the online setting, that is, p_t (along with possibly F_t) only arrive one by one and, upon such an arrival, the online algorithm has to output the corresponding solution without knowledge of the future.
We develop general techniques for online multistage subset maximization and thereby characterize those models (given by the type of data evolution and the type of similarity measure) that admit a constant-competitive online algorithm. When no constant competitive ratio is possible, we employ lookahead to circumvent this issue. When a constant competitive ratio is possible, we provide almost matching lower and upper bounds on the best achievable one.

BibTeX - Entry

@InProceedings{bampis_et_al:LIPIcs:2019:11132,
  author =	{Evripidis Bampis and Bruno Escoffier and Kevin Schewior and Alexandre Teiller},
  title =	{{Online Multistage Subset Maximization Problems}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{11:1--11:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11132},
  URN =		{urn:nbn:de:0030-drops-111320},
  doi =		{10.4230/LIPIcs.ESA.2019.11},
  annote =	{Keywords: Multistage optimization, Online algorithms}
}

Keywords: Multistage optimization, Online algorithms
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI