Advice complexity of priority algorithms

Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

54 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publicationApproximation and Online Algorithms - 16th International Workshop, WAOA 2018, Revised Selected Papers
EditorsLeah Epstein, Thomas Erlebach
PublisherSpringer
Publication date2018
Pages69-86
ISBN (Print)9783030046927
DOIs
Publication statusPublished - 2018
Event16th Workshop on Approximation and Online Algorithms, WAOA 2018 - Helsinki, Finland
Duration: 23. Aug 201824. Aug 2018

Conference

Conference16th Workshop on Approximation and Online Algorithms, WAOA 2018
Country/TerritoryFinland
CityHelsinki
Period23/08/201824/08/2018
SeriesLecture Notes in Computer Science
Volume11312
ISSN0302-9743

Fingerprint

Dive into the research topics of 'Advice complexity of priority algorithms'. Together they form a unique fingerprint.

Cite this