2026-07-20T14:34:32Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11560 2024-03-06T10:48:19Z ddc:004 open_access

Dual-Mode Greedy Algorithms Can Save Energy Geissmann, Barbara Leucci, Stefano Liu, Chih-Hung Penna, Paolo Proietti, Guido matroids p-extendible systems greedy algorithm approximation algorithms high-low energy 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Barbara Geissmann and Stefano Leucci and Chih-Hung Liu and Paolo Penna and Guido Proietti 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.64 urn:nbn:de:0030-drops-115604 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.64 eng https://creativecommons.org/licenses/by/3.0/legalcode