Document Open Access Logo

Online Multistage Subset Maximization Problems

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.11.pdf
  • Filesize: 491 kB
  • 14 pages

Document Identifiers

Author Details

Evripidis Bampis
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Bruno Escoffier
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
Kevin Schewior
  • Fakultät für Informatik, Technische Universität München, Germany
  • Départment d'Informatique, École Normale Supérieure Paris, PSL University, France
Alexandre Teiller
  • Sorbonne Université, CNRS, LIP6, F-75005 Paris, France

Funding

  • Schewior, Kevin: Supported by the DAAD within the PRIME program using funds of BMBF and the EU Marie Curie Actions.

Acknowledgements

This research benefited from the support of FMJH program PGMO and from the support of EDF-Thalès-Orange.

Cite AsGet BibTex

Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller. Online Multistage Subset Maximization Problems. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.11

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Online algorithms
Keywords
  • Multistage optimization
  • Online algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Susanne Albers and Jens Quedenfeld. Optimal Algorithms for Right-Sizing Data Centers. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 363-372, 2018. Google Scholar
  2. Hyung-Chan An, Ashkan Norouzi-Fard, and Ola Svensson. Dynamic Facility Location via Exponential Clocks. ACM Trans. Algorithms, 13(2):21:1-21:20, 2017. Google Scholar
  3. Barbara M. Anthony and Anupam Gupta. Infrastructure Leasing Problems. In Conference on Integer Programming and Combinatorial Optimization (IPCO), pages 424-438, 2007. Google Scholar
  4. Antonios Antoniadis and Kevin Schewior. A Tight Lower Bound for Online Convex Optimization with Switching Costs. In Workshop on Approximation and Online Algorithms (WAOA), pages 164-175, 2017. Google Scholar
  5. Evripidis Bampis, Bruno Escoffier, Michael Lampis, and Vangelis Th. Paschos. Multistage Matchings. In Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 7:1-7:13, 2018. Google Scholar
  6. Evripidis Bampis, Bruno Escoffier, and Sasa Mladenovic. Fair Resource Allocation Over Time. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), pages 766-773, 2018. Google Scholar
  7. Evripidis Bampis, Bruno Escoffier, Kevin Schewior, and Alexandre Teiller. Online Multistage Subset Maximization Problems. CoRR, abs/1905.04162, 2019. URL: http://arxiv.org/abs/1905.04162.
  8. Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Clifford Stein. A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs. In Workshop on Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX/RANDOM), pages 96-109, 2015. Google Scholar
  9. Nicolas K. Blanchard and Nicolas Schabanel. Dynamic Sum-Radii Clustering. In International Conference and Workshops on Algorithms and Computation (WALCOM), pages 30-41, 2017. Google Scholar
  10. Niv Buchbinder, Shahar Chen, and Joseph Naor. Competitive Analysis via Regularization. In ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 436-444, 2014. Google Scholar
  11. Niv Buchbinder, Shahar Chen, Joseph Naor, and Ohad Shamir. Unified Algorithms for Online Learning and Competitive Analysis. Math. Oper. Res., 41(2):612-625, 2016. URL: https://doi.org/10.1287/moor.2015.0742.
  12. Edith Cohen, Graham Cormode, Nick G. Duffield, and Carsten Lund. On the Tradeoff between Stability and Fit. ACM Trans. Algorithms, 13(1):7:1-7:24, 2016. URL: https://doi.org/10.1145/2963103.
  13. David Eisenstat, Claire Mathieu, and Nicolas Schabanel. Facility Location in Evolving Metrics. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 459-470, 2014. Google Scholar
  14. Albert Gu, Anupam Gupta, and Amit Kumar. The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online. SIAM J. Comput., 45(1):1-28, 2016. URL: https://doi.org/10.1137/140955276.
  15. Anupam Gupta, Kunal Talwar, and Udi Wieder. Changing Bases: Multistage Optimization for Matroids and Matchings. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 563-575, 2014. Google Scholar
  16. Vinay Joseph and Gustavo de Veciana. Jointly optimizing multi-user rate adaptation for video transport over wireless systems: Mean-fairness-variability tradeoffs. In IEEE International Conference on Computer Communications (INFOCOM), pages 567-575, 2012. Google Scholar
  17. Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Dynamic Right-Sizing for Power-Proportional Data Centers. IEEE/ACM Trans. Netw., 21(5):1378-1391, 2013. Google Scholar
  18. Minghong Lin, Adam Wierman, Lachlan L. H. Andrew, and Eno Thereska. Dynamic Right-Sizing for Power-Proportional Data Centers. IEEE/ACM Trans. Netw., 21(5):1378-1391, 2013. Google Scholar
  19. Zhenhua Liu, Iris Liu, Steven H. Low, and Adam Wierman. Pricing data center demand response. In ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS), pages 111-123, 2014. Google Scholar
  20. Nicole Megow, Martin Skutella, José Verschae, and Andreas Wiese. The Power of Recourse for Online MST and TSP. SIAM J. Comput., 45(3):859-880, 2016. URL: https://doi.org/10.1137/130917703.
  21. Chandrashekhar Nagarajan and David P Williamson. Offline and online facility leasing. Discrete Optimization, 10(4):361-370, 2013. Google Scholar
  22. Neil Olver, Kirk Pruhs, Rene Sitters, Kevin Schewior, and Leen Stougie. The Itinerant List-Update Problem. In Workshop on Approximation and Online Algorithms (WAOA), pages 310-326, 2018. Google Scholar
  23. Kirk Pruhs and Gerhard J. Woeginger. Approximation schemes for a class of subset selection problems. Theor. Comput. Sci., 382(2):151-156, 2007. Google Scholar
  24. Cécile Rottner. Combinatorial Aspects of the Unit Commitment Problem. PhD thesis, Sorbonne Université, 2018. Google Scholar
  25. Daniel Dominic Sleator and Robert Endre Tarjan. Amortized Efficiency of List Update and Paging Rules. Commun. ACM, 28(2):202-208, 1985. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact