Advice Complexity of Priority Algorithms
| Autor: | Kim S. Larsen, Allan Borodin, Joan Boyar, Denis Pankratov |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Advice complexity Optimization problem Computer science Priority algorithms 0102 computer and information sciences 02 engineering and technology Adversary Mathematical proof 01 natural sciences Oracle Greedy algorithms Theoretical Computer Science Reduction (complexity) Computational Theory and Mathematics 010201 computation theory & mathematics Computer Science - Data Structures and Algorithms Theory of computation 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing Greedy algorithm Advice (complexity) Algorithm Optimization problems |
| Zdroj: | Borodin, A, Boyar, J, Larsen, K S & Pankratov, D 2020, ' Advice Complexity of Priority Algorithms ', Theory of Computing Systems, vol. 64, no. 4, pp. 593-625 . https://doi.org/10.1007/s00224-019-09955-7 |
| ISSN: | 1433-0490 1432-4350 |
| Popis: | 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. 29 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink