<--- Back to Details
| First Page | Document Content | |
|---|---|---|
 Date: 2009-02-06 16:43:24Operations research NP-complete problems Combinatorial optimization Dynamic programming Knapsack problem Bin packing problem Polynomial-time approximation scheme Approximation algorithm Linear programming relaxation Theoretical computer science Computational complexity theory Applied mathematics |
Add to Reading List |
CS 598CSC: Approximation Algorithms Instructor: Chandra Chekuri | The G¨odel Prize 2010 Laudatio for S. Arora and J.S.B. Mitchell The G¨odel Prize 2010 is awarded to Sanjeev Arora and Joseph S.B. Mitchell for their concurrent discovery of a polynomial-time approximation scheme (PTAS)DocID: 1uxpN - View Document |
| A Polynomial-Time Approximation Scheme for Maximum Quartet CompatibilityDocID: 1r43R - View Document |
| Truthful Approximation Schemes for Single-Parameter Agents∗ Peerapong Dhangwatnotai† Shahar Dobzinski‡ Shaddin Dughmi§DocID: 1qQMD - View Document |
| A PTAS for the Highway Problem Fabrizio Grandoni & Thomas Rothvo Institute of Mathemati s EPFL, Lausanne The Highway ProblemDocID: 1qocT - View Document |
| Bin Pa king via Dis repan y of Permutations F. Eisenbrand, D. Palv olgyi & T. Rothvo Cargese Workshop 2010DocID: 1qlBy - View Document |