Document Open Access Logo

Dual-Mode Greedy Algorithms Can Save Energy

Authors Barbara Geissmann , Stefano Leucci , Chih-Hung Liu , Paolo Penna , Guido Proietti

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.64.pdf
  • Filesize: 0.76 MB
  • 18 pages

Document Identifiers

Author Details

Barbara Geissmann
  • Department of Computer Science, ETH Zürich, Switzerland
Stefano Leucci
  • Department of Algorithms and Complexity, Max Planck Institute for Informatics, Germany
Chih-Hung Liu
  • Department of Computer Science, ETH Zürich, Switzerland
Paolo Penna
  • Department of Computer Science, ETH Zürich, Switzerland
Guido Proietti
  • Dipartimento di Ingegneria e Scienze dell'Informazione e Matematica, Università dell'Aquila, Italy
  • Istituto di Analisi dei Sistemi ed Informatica "A. Ruberti", CNR, Roma, Italy

Funding

Research supported by the Swiss National Science Foundation (SNFS project 200021_165524).

Acknowledgements

We are grateful to Peter Widmayer for many inspiring discussions.

Cite AsGet BibTex

Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, Paolo Penna, and Guido Proietti. Dual-Mode Greedy Algorithms Can Save Energy. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.64

Abstract

In real world applications, important resources like energy are saved by deliberately using so-called low-cost operations that are less reliable. Some of these approaches are based on a dual mode technology where it is possible to choose between high-energy operations (always correct) and low-energy operations (prone to errors), and thus enable to trade energy for correctness. In this work we initiate the study of algorithms for solving optimization problems that in their computation are allowed to choose between two types of operations: high-energy comparisons (always correct but expensive) and low-energy comparisons (cheaper but prone to errors). For the errors in low-energy comparisons, we assume the persistent setting, which usually makes it impossible to achieve optimal solutions without high-energy comparisons. We propose to study a natural complexity measure which accounts for the number of operations of either type separately. We provide a new family of algorithms which, for a fairly large class of maximization problems, return a constant approximation using only polylogarithmic many high-energy comparisons and only O(n log n) low-energy comparisons. This result applies to the class of p-extendible system s [Mestre, 2006], which includes several NP-hard problems and matroids as a special case (p=1). These algorithmic solutions relate to some fundamental aspects studied earlier in different contexts: (i) the approximation guarantee when only ordinal information is available to the algorithm; (ii) the fact that even such ordinal information may be erroneous because of low-energy comparisons and (iii) the ability to approximately sort a sequence of elements when comparisons are subject to persistent errors. Finally, our main result is quite general and can be parametrized and adapted to other error models.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • matroids
  • p-extendible systems
  • greedy algorithm
  • approximation algorithms
  • high-low energy

Metrics

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

References

  1. Bilge ES Akgul, Lakshmi N Chakrapani, Pinar Korkmaz, and Krishna V Palem. Probabilistic CMOS technology: A survey and future directions. In Very Large Scale Integration, 2006 IFIP International Conference on, pages 1-6. IEEE, 2006. Google Scholar
  2. Christoph Ambühl. An optimal bound for the MST algorithm to compute energy efficient broadcast trees in wireless networks. In Proc. of International Colloquium on Automata, Languages, and Programming (ICALP), pages 1139-1150. Springer, 2005. Google Scholar
  3. Elliot Anshelevich and Shreyas Sekar. Blind, Greedy, and Random: Algorithms for Matching and Clustering Using Only Ordinal Information. In Proc. of the Thirtieth AAAI Conference on Artificial Intelligence, pages 390-396, 2016. Google Scholar
  4. Elliot Anshelevich and Shreyas Sekar. Truthful mechanisms for matching and clustering in an ordinal world. In International Conference on Web and Internet Economics, pages 265-278. Springer, 2016. Google Scholar
  5. Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for Greedy Maximization of Non-submodular Functions with Applications. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 498-507, International Convention Centre, Sydney, Australia, 06-11 August 2017. PMLR. Google Scholar
  6. Mark Braverman and Elchanan Mossel. Noisy Sorting Without Resampling. In Proc. of the 19th Annual Symposium on Discrete Algorithms (SODA), pages 268-276, 2008. URL: http://arxiv.org/abs/0707.1051.
  7. Lakshmi N. B. Chakrapani, Jason George, Bo Marr, Bilge E. S. Akgul, and Krishna V. Palem. Probabilistic Design: A Survey of Probabilistic CMOS Technology and Future Directions for Terascale IC Design. In Giovanni De Micheli, Salvador Mir, and Ricardo Reis, editors, VLSI-SoC: Research Trends in VLSI and Systems on Chip, pages 101-118, Boston, MA, 2008. Springer US. Google Scholar
  8. Vaggos Chatziafratis, Tim Roughgarden, and Jan Vondrák. Stability and Recovery for Independence Systems. In Proc. of the 25th Annual European Symposium on Algorithms (ESA), volume 87 of LIPIcs, pages 26:1-26:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ESA.2017.26.
  9. Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy algorithm: tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete applied mathematics, 7(3):251-274, 1984. Google Scholar
  10. Uriel Feige, Prabhakar Raghavan, David Peleg, and Eli Upfal. Computing with Noisy Information. SIAM Journal on Computing, 23(5):1001-1018, 1994. URL: https://doi.org/10.1137/S0097539791195877.
  11. Irene Finocchi, Fabrizio Grandoni, and Giuseppe F. Italiano. Optimal resilient sorting and searching in the presence of memory faults. Theor. Comput. Sci., 410(44):4457-4470, 2009. URL: https://doi.org/10.1016/j.tcs.2009.07.026.
  12. Stefan Funke, Kurt Mehlhorn, and Stefan Näher. Structural filtering: a paradigm for efficient and exact geometric programs. Comput. Geom., 31(3):179-194, 2005. Google Scholar
  13. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Sorting with Recurrent Comparison Errors. In ISAAC, volume 92 of LIPIcs, pages 38:1-38:12. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  14. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal Dislocation with Persistent Errors in Subquadratic Time. In Proc. of the 35th Symposium on Theoretical Aspects of Computer Science (STACS), volume 96 of LIPIcs, pages 36:1-36:13, 2018. Google Scholar
  15. Barbara Geissmann, Stefano Leucci, Chih-Hung Liu, and Paolo Penna. Optimal Sorting with Persistent Comparison Errors. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany., pages 49:1-49:14, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.49.
  16. Barbara Geissmann and Paolo Penna. Inversions from Sorting with Distance-Based Errors. In Proc. of the 44th InternationalConference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 10706 of Lecture Notes in Computer Science, pages 508-522. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-73117-9_36.
  17. Lefteris M Kirousis, Evangelos Kranakis, Danny Krizanc, and Andrzej Pelc. Power consumption in packet radio networks. Theoretical Computer Science, 243(1-2):289-305, 2000. Google Scholar
  18. Rolf Klein, Rainer Penninger, Christian Sohler, and David P. Woodruff. Tolerant Algorithms. In Proc. of the 19th Annual European Symposium on Algorithm (ESA), pages 736 - -747, 2011. Google Scholar
  19. Bernhard Korte and Dirk Hausmann. An Analysis of the Greedy Heuristic for Independence Systems. In B. Alspach, P. Hell, and D.J. Miller, editors, Algorithmic Aspects of Combinatorics, volume 2 of Annals of Discrete Mathematics, pages 65-74. Elsevier, 1978. URL: https://doi.org/10.1016/S0167-5060(08)70322-4.
  20. Stefano Leucci, Chih-Hung Liu, and Simon Meierhans. Resilient Dictionaries for Randomly Unreliable Memory. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany., pages 70:1-70:16, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.70.
  21. Itamar Levi and Alexander Fish. Dual mode logic—Design for energy efficiency and high performance. IEEE access, 1:258-265, 2013. Google Scholar
  22. Sven Leyffer, Stefan M. Wild, Mike Fagan, Marc Snir, Krishna V. Palem, Kazutomo Yoshii, and Hal Finkel. Doing Moore with Less - Leapfrogging Moore’s Law with Inexactness for Supercomputing. CoRR, abs/1610.02606, 2016. URL: http://arxiv.org/abs/1610.02606.
  23. Edo Liberty and Maxim Sviridenko. Greedy Minimization of Weakly Supermodular Set Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM-17), volume 81 of LIPIcs, pages 19:1-19:11, 2017. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.19.
  24. Julián Mestre. Greedy in approximation algorithms. In European Symposium on Algorithms, pages 528-539. Springer, 2006. Google Scholar
  25. Julián Mestre. Greedy in Approximation Algorithms. In Algorithms - ESA 2006, 14th Annual European Symposium, Zurich, Switzerland, September 11-13, 2006, Proceedings, pages 528-539, 2006. URL: https://doi.org/10.1007/11841036_48.
  26. Matúš Mihalák, Marcel Schöngens, Rastislav Šrámek, and Peter Widmayer. On the complexity of the metric tsp under stability considerations. In Proc. of International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), pages 382-393. Springer, 2011. Google Scholar
  27. George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions - I. Mathematical Programming, 14(1):265-294, 1978. Google Scholar
  28. Andrzej Pelc. Searching games with errors - fifty years of coping with liars. Theor. Comput. Sci., 270(1-2):71-109, 2002. Google Scholar
  29. Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In Proc. of the fortieth Annual ACM Symposium on Theory of computing (STOC), pages 67-74. ACM, 2008. Google Scholar
  30. Jan Vondrák. Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algorithms). Mathematical Analysis Laboratory of Kyoto University, 2010. 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