Abstract
In real world applications, important resources like energy are saved by deliberately using socalled lowcost operations that are less reliable. Some of these approaches are based on a dual mode technology where it is possible to choose between highenergy operations (always correct) and lowenergy 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: highenergy comparisons (always correct but expensive) and lowenergy comparisons (cheaper but prone to errors). For the errors in lowenergy comparisons, we assume the persistent setting, which usually makes it impossible to achieve optimal solutions without highenergy 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 highenergy comparisons and only O(n log n) lowenergy comparisons. This result applies to the class of pextendible system s [Mestre, 2006], which includes several NPhard 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 lowenergy 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.
BibTeX  Entry
@InProceedings{geissmann_et_al:LIPIcs:2019:11560,
author = {Barbara Geissmann and Stefano Leucci and ChihHung Liu and Paolo Penna and Guido Proietti},
title = {{DualMode Greedy Algorithms Can Save Energy}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {64:164:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11560},
URN = {urn:nbn:de:0030drops115604},
doi = {10.4230/LIPIcs.ISAAC.2019.64},
annote = {Keywords: matroids, pextendible systems, greedy algorithm, approximation algorithms, highlow energy}
}
Keywords: 

matroids, pextendible systems, greedy algorithm, approximation algorithms, highlow energy 
Collection: 

30th International Symposium on Algorithms and Computation (ISAAC 2019) 
Issue Date: 

2019 
Date of publication: 

28.11.2019 