@inproceedings{567b355046234d93bb602f5623f22ac7,
title = "Approximation algorithms that take advice",
abstract = "Many recently designed approximation algorithms use a simple but apparently powerful idea. The algorithm is allowed to ask a trusted oracle for a small number (say O(log n)) bits of “advice.” For instance, it could ask for O(log n) bits of the optimum answer. Of course, strictly speaking, a polynomial-time algorithm has no need for log n bits of advice: it could just try all possibilities for this advice and retain the one that works the best. Nevertheless, this is a useful way of thinking about some approximation algorithms. In the talk I will present a few examples. My title is a play on the title of a classic paper on nonuniform computation “Turing Machines that take advice” (Karp and Lipton 1982).",
author = "Sanjeev Arora",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2000.; 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000 ; Conference date: 05-09-2000 Through 08-09-2000",
year = "2000",
doi = "10.1007/3-540-44436-x_1",
language = "English (US)",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "1",
editor = "Klaus Jansen and Samir Khuller",
booktitle = "Approximation Algorithms for Combinatorial Optimization - 3rd International Workshop, APPROX 2000, Proceedings",
address = "Germany",
}