Document Open Access Logo

General Bounds for Incremental Maximization

Authors Aaron Bernstein, Yann Disser, Martin Groß

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.43.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Aaron Bernstein
Yann Disser
Martin Groß

Cite As Get BibTex

Aaron Bernstein, Yann Disser, and Martin Groß. General Bounds for Incremental Maximization. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.43

Abstract

We propose a theoretical framework to capture incremental solutions to cardinality constrained maximization problems. The defining characteristic of our framework is that the cardinality/support of the solution is bounded by a value k in N that grows over time, and we allow the solution to be extended one element at a time. We investigate the best-possible competitive ratio of such an incremental solution, i.e., the worst ratio over all k between the incremental solution after~$k$ steps and an optimum solution of cardinality k. We define a large class of problems that contains many important cardinality constrained maximization problems like maximum matching, knapsack, and packing/covering problems. We provide a general 2.618-competitive incremental algorithm for this class of problems, and show that no algorithm can have competitive ratio below 2.18 in general.
  
In the second part of the paper, we focus on the inherently incremental greedy algorithm that increases the objective value as much as possible in each step. This algorithm is known to be 1.58-competitive for submodular objective functions, but it has unbounded competitive ratio for the class of incremental problems mentioned above. We define a relaxed submodularity condition for the objective function, capturing problems like maximum (weighted) (b-)matching and a variant of the maximum flow problem. We show that the greedy algorithm has competitive ratio (exactly) 2.313 for the class of problems that satisfy this relaxed submodularity condition.
  
Note that our upper bounds on the competitive ratios translate to approximation ratios for the underlying cardinality constrained problems.

Subject Classification

Keywords
  • incremental optimization
  • maximization problems
  • greedy algorithm
  • competitive analysis
  • cardinality constraint

Metrics

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

References

  1. Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, and Madhu Sudan. The minimum latency problem. In Proceedings of the 26th Annual ACM Symposium on Theory of computing (STOC), pages 163-171, 1994. Google Scholar
  2. A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, UK, 1998. Google Scholar
  3. Moses Charikar, Chandra Chekuri, Tomas Feder, and Rajeev Motwani. Incremental clustering and dynamic information retrieval. SIAM Journal on Computing, 33(6):1417-1440, 2004. Google Scholar
  4. Marek Chrobak, Claire Kenyon, John Noga, and Neal E. Young. Incremental medians via online bidding. Algorithmica, 50(4):455-478, 2007. Google Scholar
  5. Varsha Dani and Thomas P. Hayes. Robbing the bandit: less regret in online geometric optimization against an adaptive adversary. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 937-943, 2006. Google Scholar
  6. Sanjoy Dasgupta and Philip M. Long. Performance guarantees for hierarchical clustering. Journal of Computer and System Sciences, 70(4):555-569, 2005. Google Scholar
  7. Yann Disser, Max Klimm, Nicole Megow, and Sebastian Stiller. Packing a Knapsack of Unknown Capacity. SIAM Journal on Discrete Mathematics, to appear. Google Scholar
  8. U. Faigle, W. Kern, and G. Turan. On the performance of on-line algorithms for partition problems. Acta Cybernetica, 9(2):107-119, 1989. Google Scholar
  9. A. Fiat and G. J. Woeginger, editors. Online Algorithms: The State of the Art. Springer, Berlin, 1998. Google Scholar
  10. Dimitris Fotakis. Incremental algorithms for facility location and k-median. Theoretical Computer Science, 361(2-3):275-313, 2006. URL: http://dx.doi.org/10.1016/j.tcs.2006.05.015.
  11. Ryo Fujita, Yusuke Kobayashi, and Kazuhisa Makino. Robust matchings and matroid intersections. SIAM Journal on Discrete Mathematics, 27(3):1234-1256, 2013. URL: http://dx.doi.org/10.1137/100808800.
  12. Michel Goemans and Jon Kleinberg. An improved approximation ratio for the minimum latency problem. Mathematical Programming, 82(1-2):111-124, 1998. Google Scholar
  13. C. Greg Plaxton. Approximation algorithms for hierarchical location problems. Journal of Computer and System Sciences, 72(3):425-443, 2006. Google Scholar
  14. Magnús M. Halldórsson and Hadas Shachnai. Return of the boss problem: Competing online against a non-adaptive adversary. In Proceedings of the 5th International Conference on Fun with Algorithms (FUN), pages 237-248, 2010. Google Scholar
  15. Jeff Hartline and Alexa Sharp. Incremental flow. Networks, 50(1):77-85, 2007. Google Scholar
  16. Refael Hassin and Shlomi Rubinstein. Robust matchings. SIAM Journal on Discrete Mathematics, 15(4):530-537, 2002. URL: http://dx.doi.org/10.1137/S0895480198332156.
  17. Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. Journal of the ACM, 22(4):463-468, 1975. Google Scholar
  18. Naonori Kakimura and Kazuhisa Makino. Robust independence systems. SIAM Journal on Discrete Mathematics, 27(3):1257-1273, 2013. URL: http://dx.doi.org/10.1137/120899480.
  19. Naonori Kakimura, Kazuhisa Makino, and Kento Seimi. Computing knapsack solutions with cardinality robustness. Japan Journal of Industrial and Applied Mathematics, 29(3):469-483, 2012. URL: http://dx.doi.org/10.1007/s13160-012-0075-z.
  20. Yusuke Kobayashi and Kenjiro Takazawa. Randomized strategies for cardinality robustness in the knapsack problem. Theoretical Computer Science, pages 1-10, 2016. URL: http://dx.doi.org/10.1016/j.tcs.2016.12.019.
  21. A. Krause, H. B. McMahan, C. Guestrin, and A. Gupta. Robust submodular observation selection. Journal of Machine Learning Research, 9:2761-2801, 2008. Google Scholar
  22. Eugene L. Lawler. Fast approximation algorithms for knapsack problems. Mathematics of Operations Research, 4(4):339-356, 1979. Google Scholar
  23. Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, and David P. Williamson. A general approach for incremental approximation and hierarchical clustering. SIAM Journal on Computing, 39(8):3633-3669, 2010. URL: http://dx.doi.org/10.1137/070698257.
  24. Jannik Matuschke, Martin Skutella, and José A. Soto. Robust randomized matchings. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1904-1915, 2014. Google Scholar
  25. Nicole Megow and Julian Mestre. Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science (ITCS), pages 495-504, 2013. Google Scholar
  26. Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM Journal on Computing, 32(3):816-832, 2003. URL: http://dx.doi.org/10.1137/S0097539701383443.
  27. G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming, 14(1):265-294, 1978. 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 About DROPS Imprint Privacy Contact