Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Using easy optimization problems to solve hard ones
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
2004 (English)In: Classical and New Paradigms of Computation and Their Complexity Hierarchies / [ed] Lowe, B; Piwinger, B; Rasch, T, DORDRECHT: SPRINGER , 2004, Vol. 23, 77-93 p.Conference paper, Published paper (Refereed)
Abstract [en]

In combinatorial optimization one typically wants to minimize some cost function given a set of constraints that must be satisfied. A classical example is the so called Traveling Salesman Problem (TSP), in which we are given a set of cities with certain distances between them and we are asked to find the shortest possible tour that visits every city exactly once and then returns to the starting point. This problem is believed to be hard to solve exactly-it has been shown to belong to a certain class of notoriously hard problems, the so called NP-hard problems. Despite huge efforts, there is no currently known efficient algorithm that solves any of the NP-hard problems and it is widely believed that no such algorithm exists. However, it is always possible to find an approximation to the optimum tour by solving a much easier problem, the so called Minimum Spanning Tree problem. This is an example of a general paradigm in the field of approximation algorithms for optimization problems: Instead of solving a very hard problem we solve an easy one and then convert the optimal solution to the easy problem into an approximately optimal solution to the hard one. Obviously, it is important to be careful when converting the optimal solution to the easy problem into an approximately optimal solution to the hard one. In many applications, the analysis of the algorithm is greatly simplified by the use of random selections. Typically, we then use information obtained from the solution to the easy problem to bias our selection of a solution to the hard one.

Place, publisher, year, edition, pages
DORDRECHT: SPRINGER , 2004. Vol. 23, 77-93 p.
Series
Trends In Logic - Studia Logica Library, ISSN 1572-6126 ; 23
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-44675ISI: 000229305100007ISBN: 1-4020-2775-3 (print)OAI: oai:DiVA.org:kth-44675DiVA: diva2:452110
Conference
Conference on Foundations of the Formal Sciences III Location: Vienna, AUSTRIA Date: SEP 21-24, 2001
Note
QC 20111028Available from: 2011-10-28 Created: 2011-10-25 Last updated: 2011-10-28Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Engebretsen, Lars
By organisation
Numerical Analysis and Computer Science, NADA
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 28 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf