BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Fast approximation algorithms for combinatorial problems
DTSTART:20190828T090000
DTEND:20190828T110000
DTSTAMP:20260407T051016Z
UID:0078fcba0c20ea5be7fb5d55d4fb9f761529910aa919b3bfef7c1b86
CATEGORIES:Conferences - Seminars
DESCRIPTION:Etienne Bamas\nEDIC candidacy exam\nExam president: Prof. Mich
 ael Kapralov\nThesis advisor: Prof. Ola Svensson\nCo-examiner: Prof. Fried
 rich Eisenbrand\n\nAbstract\nIn combinatorial optimization\, one often see
 ks for faster algorithms while allowing a drop in the quality of the solut
 ion 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 wei
 ght independent set of rectangles in a plane\, and finally\, the symmetri
 c 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 s
 cheme\, and for the last problem we present a 3/2-approximation running in
  polynomial time.\n\nBackground papers\nApproximating Edit Distance Within
  Constant Factor in Truly Sub-Quadratic Time\, by Chakraborty\, D\, et al.
 \nApproximation Schemes for Maximum Weight Independent Set of Rectangles\,
  by Adamaszek\, A.\, Wiese\, A.\nA 1.5-Approximation for Path TSP\, by Zen
 klusen\, R.\n\n 
LOCATION:INF 213 https://plan.epfl.ch/?room==INF%20213
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR