Show simple item record

dc.contributor.author
Geissmann, Barbara
dc.contributor.author
Leucci, Stefano
dc.contributor.author
Liu, Chih-Hung
dc.contributor.author
Penna, Paolo
dc.contributor.author
Proietti, Guido
dc.contributor.editor
Lu, Pinyan
dc.contributor.editor
Zhang, Guochuan
dc.date.accessioned
2019-12-13T14:14:29Z
dc.date.available
2019-12-12T17:51:35Z
dc.date.available
2019-12-13T14:14:29Z
dc.date.issued
2019
dc.identifier.isbn
978-3-95977-130-6
en_US
dc.identifier.issn
1868-8969
dc.identifier.other
10.4230/LIPICS.ISAAC.2019.64
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/385241
dc.identifier.doi
10.3929/ethz-b-000385241
dc.description.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.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rights.uri
http://creativecommons.org/licenses/by/3.0/
dc.subject
Matroids
en_US
dc.subject
p-extendible systems
en_US
dc.subject
Greedy algorithms
en_US
dc.subject
Approximation algorithms
en_US
dc.subject
High-low energy
en_US
dc.title
Dual-Mode Greedy Algorithms Can Save Energy
en_US
dc.type
Conference Paper
dc.rights.license
Creative Commons Attribution 3.0 Unported
ethz.book.title
30th International Symposium on Algorithms and Computation (ISAAC 2019)
en_US
ethz.journal.title
Leibniz International Proceedings in Informatics (LIPIcs)
ethz.journal.volume
149
en_US
ethz.journal.abbreviated
Leibniz Int. Proc. Inform.
ethz.pages.start
64:1
en_US
ethz.pages.end
64:18
en_US
ethz.size
18 p.
en_US
ethz.version.deposit
publishedVersion
en_US
ethz.event
30th International Symposium on Algorithms and Computation (ISAAC 2019)
en_US
ethz.event.location
Shanghai, China
en_US
ethz.event.date
December 9-11, 2019
en_US
ethz.grant
Energy-Tunable Combinatorial Algorithms
en_US
ethz.identifier.scopus
ethz.publication.place
Wadern
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02661 - Institut für Maschinelles Lernen / Institute for Machine Learning::03659 - Buhmann, Joachim M. / Buhmann, Joachim M.
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02661 - Institut für Maschinelles Lernen / Institute for Machine Learning::03659 - Buhmann, Joachim M. / Buhmann, Joachim M.
en_US
ethz.leitzahl.certified
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science::02643 - Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03672 - Steger, Angelika / Steger, Angelika::03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
ethz.grant.agreementno
165524
ethz.grant.agreementno
165524
ethz.grant.fundername
SNF
ethz.grant.fundername
SNF
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.funderDoi
10.13039/501100001711
ethz.grant.program
Projekte MINT
ethz.date.deposited
2019-12-12T17:51:46Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2019-12-13T14:14:41Z
ethz.rosetta.lastUpdated
2024-02-02T10:01:47Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Dual-Mode%20Greedy%20Algorithms%20Can%20Save%20Energy&rft.jtitle=Leibniz%20International%20Proceedings%20in%20Informatics%20(LIPIcs)&rft.date=2019&rft.volume=149&rft.spage=64:1&rft.epage=64:18&rft.issn=1868-8969&rft.au=Geissmann,%20Barbara&Leucci,%20Stefano&Liu,%20Chih-Hung&Penna,%20Paolo&Proietti,%20Guido&rft.isbn=978-3-95977-130-6&rft.genre=proceeding&rft_id=info:doi/10.4230/LIPICS.ISAAC.2019.64&rft.btitle=30th%20International%20Symposium%20on%20Algorithms%20and%20Computation%20(ISAAC%202019)
 Search print copy at ETH Library

Files in this item

Thumbnail

Publication type

Show simple item record