Introduction

Ding-Zhu Du (dzdu@utdallas.edu), Ker-I Ko (keriko@cs.sunysb.edu) and Xiaodong Hu (xdhu@amss.ac.cn)
Additional contact information
Ding-Zhu Du: University of Texas at Dallas
Ker-I Ko: State University of New York at Stony Brook
Xiaodong Hu: Academy of Mathematics and Systems Science Chinese Academy of Sciences

Chapter 1 in Design and Analysis of Approximation Algorithms, 2012, pp 1-33 from Springer

Abstract: Abstract When exact solutions are hard to compute, approximation algorithms can help. In this chapter, we introduce the basic notions of approximation algorithms.We study a simple optimization problem to demonstrate the tradeoff between the time complexity and performance ratio of its approximation algorithms. We also present a brief introduction to the general theory of computational complexity and show how to apply this theory to classify optimization problems according to their approximability.

Keywords: Approximation Algorithm; Minimum Span Tree; Turing Machine; Travel Salesman Problem; Problem Knapsack (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-1-4614-1701-9_1

Ordering information: This item can be ordered from
http://www.springer.com/9781461417019

DOI: 10.1007/978-1-4614-1701-9_1

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla (sonal.shukla@springer.com) and Springer Nature Abstracting and Indexing (indexing@springernature.com).