Approximation algorithms that take advice

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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).

Original languageEnglish (US)
Title of host publicationApproximation Algorithms for Combinatorial Optimization - 3rd International Workshop, APPROX 2000, Proceedings
EditorsKlaus Jansen, Samir Khuller
PublisherSpringer Verlag
Pages1
Number of pages1
ISBN (Electronic)9783540679967
DOIs
StatePublished - 2000
Event3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000 - Saarbrucken, Germany
Duration: Sep 5 2000Sep 8 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1913
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, APPROX 2000
Country/TerritoryGermany
CitySaarbrucken
Period9/5/009/8/00

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Approximation algorithms that take advice'. Together they form a unique fingerprint.

Cite this