- Advice Complexity of Priority Algorithms.
- Allan Borodin, Joan Boyar, Kim S. Larsen, and Denis Pankratov.
Theory of Computing Systems. Accepted for publication.
The priority model of "greedy-like" algorithms was introduced by
Borodin, Nielsen, and Rackoff in 2002. We augment this model by
allowing priority algorithms to have access to advice, i.e., side
information precomputed by an all-powerful oracle. Obtaining lower
bounds in the priority model without advice can be challenging and
may involve intricate adversary arguments. Since the priority model
with advice is even more powerful, obtaining lower bounds presents
additional difficulties. We sidestep these difficulties by
developing a general framework of reductions which makes lower bound
proofs relatively straightforward and routine. We start by
introducing the Pair Matching problem, for which we are able to
prove strong lower bounds in the priority model with advice. We
develop a template for constructing a reduction from Pair Matching
to other problems in the priority model with advice - this part is
technically challenging since the reduction needs to define a valid
priority function for Pair Matching while respecting the priority
function for the other problem. Finally, we apply the template to
obtain lower bounds for a number of standard discrete optimization
problems.
-
open access (407 KB)
-
The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.
-
other publications
-
Other publications by the author.