Description This course deals with the design and analysis of algorithms for combinatorial optimization problems such as graph problems (matchings, network design, covering problems), scheduling and packing problems. These problems are typically computationally intractable or, in other words, NP -hard. In this course, we design and analyze polynomial-time algorithms for NP -hard combinatorial optimization problems which can provide strong mathematical guarantees on the worst-case performance. An approximation algorithm is a polynomial-time algorithm that always finds a feasible solution whose value is provably close to the optimum solution value. More precisely, the value of the computed solution must be within a factor α of the optimum. Under the common assumption that P (cid:54) = NP , approximation algorithms are, in some sense, the best algorithms with polynomial running time one can hope to design. Moreover, the performance guarantee α of an algorithm serves as a natural metric to compare the hardness of different problems.
Approximation Algorithms
Published 2021 in International Symposium on Parallel Architectures, Algorithms and Networks
ABSTRACT
PUBLICATION RECORD
- Publication year
2021
- Venue
International Symposium on Parallel Architectures, Algorithms and Networks
- Publication date
2021-08-19
- Fields of study
Mathematics, Computer Science
- Identifiers
- External record
- Source metadata
Semantic Scholar
CITATION MAP
EXTRACTION MAP
CLAIMS
- No claims are published for this paper.
CONCEPTS
- No concepts are published for this paper.
REFERENCES
Showing 1-97 of 97 references · Page 1 of 1