Show simple item record

dc.contributor.author
Komm, Dennis
dc.contributor.author
Královič, Richard
dc.date.accessioned
2020-12-20T08:55:00Z
dc.date.available
2017-06-09T13:22:42Z
dc.date.available
2020-12-20T08:55:00Z
dc.date.issued
2011-04
dc.identifier.issn
0988-3754
dc.identifier.issn
0296-1598
dc.identifier.issn
1290-385X
dc.identifier.other
10.1051/ita/2011105
en_US
dc.identifier.uri
http://hdl.handle.net/20.500.11850/38928
dc.description.abstract
Recently, a new measurement – the advice complexity – was introduced for measuring the information content of online problems. The aim is to measure the bitwise information that online algorithms lack, causing them to perform worse than offline algorithms. Among a large number of problems, a well-known scheduling problem, job shop scheduling with unit length tasks, and the paging problem were analyzed within this model. We observe some connections between advice complexity and randomization. Our special focus goes to barely random algorithms, i.e., randomized algorithms that use only a constant number of random bits, regardless of the input size. We adapt the results on advice complexity to obtain efficient barely random algorithms for both the job shop scheduling and the paging problem. Furthermore, so far, it has not yet been investigated for job shop scheduling how good an online algorithm may perform when only using a very small (e.g., constant) number of advice bits. In this paper, we answer this question by giving both lower and upper bounds, and also improve the best known upper bound for optimal algorithms.
en_US
dc.language.iso
en
en_US
dc.publisher
EDP Sciences
en_US
dc.subject
Barely random algorithms
en_US
dc.subject
Advice complexity
en_US
dc.subject
Information content
en_US
dc.subject
Online problems
en_US
dc.title
Advice Complexity and Barely Random Algorithms
en_US
dc.type
Journal Article
dc.date.published
2011-06-24
ethz.journal.title
RAIRO - Theoretical Informatics and Applications
ethz.journal.volume
45
en_US
ethz.journal.issue
2
en_US
ethz.journal.abbreviated
RAIRO-Theor. Inf. Appl.
ethz.pages.start
249
en_US
ethz.pages.end
267
en_US
ethz.identifier.wos
ethz.publication.place
Paris
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::03666 - Hromkovic, Juraj / Hromkovic, Juraj
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::03666 - Hromkovic, Juraj / Hromkovic, Juraj
ethz.date.deposited
2017-06-09T13:23:03Z
ethz.source
ECIT
ethz.identifier.importid
imp59364e5818f5c83701
ethz.ecitpid
pub:62601
ethz.eth
yes
en_US
ethz.availability
Metadata only
en_US
ethz.rosetta.installDate
2017-07-14T19:06:10Z
ethz.rosetta.lastUpdated
2022-03-29T04:37:24Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Advice%20Complexity%20and%20Barely%20Random%20Algorithms&rft.jtitle=RAIRO%20-%20Theoretical%20Informatics%20and%20Applications&rft.date=2011-04&rft.volume=45&rft.issue=2&rft.spage=249&rft.epage=267&rft.issn=0988-3754&0296-1598&1290-385X&rft.au=Komm,%20Dennis&Kr%C3%A1lovi%C4%8D,%20Richard&rft.genre=article&rft_id=info:doi/10.1051/ita/2011105&
 Search print copy at ETH Library

Files in this item

FilesSizeFormatOpen in viewer

There are no files associated with this item.

Publication type

Show simple item record