Fast approximation algorithms for combinatorial problems
Event details
| Date | 28.08.2019 |
| Hour | 09:00 › 11:00 |
| Speaker | Etienne Bamas |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Michael Kapralov
Thesis advisor: Prof. Ola Svensson
Co-examiner: Prof. Friedrich Eisenbrand
Abstract
In combinatorial optimization, one often seeks for faster algorithms while allowing a drop in the quality of the solution obtained. Our goal in this research proposal will be to explain how to design fast algorithms for three different problems while keeping control of the quality of the solution produced. Our three problems are computing edit distance between two strings of characters, computing a maximum weight independent set of rectangles in a plane, and finally, the symmetric version of the path Travelling Salesman Problem. For the first problem, we present a constant factor approximation running in subquadratic time, for the second problem we present a quasipolynomial time approximation scheme, and for the last problem we present a 3/2-approximation running in polynomial time.
Background papers
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time, by Chakraborty, D, et al.
Approximation Schemes for Maximum Weight Independent Set of Rectangles, by Adamaszek, A., Wiese, A.
A 1.5-Approximation for Path TSP, by Zenklusen, R.
Exam president: Prof. Michael Kapralov
Thesis advisor: Prof. Ola Svensson
Co-examiner: Prof. Friedrich Eisenbrand
Abstract
In combinatorial optimization, one often seeks for faster algorithms while allowing a drop in the quality of the solution obtained. Our goal in this research proposal will be to explain how to design fast algorithms for three different problems while keeping control of the quality of the solution produced. Our three problems are computing edit distance between two strings of characters, computing a maximum weight independent set of rectangles in a plane, and finally, the symmetric version of the path Travelling Salesman Problem. For the first problem, we present a constant factor approximation running in subquadratic time, for the second problem we present a quasipolynomial time approximation scheme, and for the last problem we present a 3/2-approximation running in polynomial time.
Background papers
Approximating Edit Distance Within Constant Factor in Truly Sub-Quadratic Time, by Chakraborty, D, et al.
Approximation Schemes for Maximum Weight Independent Set of Rectangles, by Adamaszek, A., Wiese, A.
A 1.5-Approximation for Path TSP, by Zenklusen, R.
Practical information
- General public
- Free