Approximation Algorithms
When solving a problem to optimality seems out of reach, designing an approximation algorithm with provable guarantees on the relative error is a great alternative. This is currently a central area of Algorithms.
Topic status: Active
Publications
Borradaile, G., Kenyon-Mathieu, C., and Klein, P. A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs. In ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Jan 2007), ACM-SIAM.
de la Vega, W. F., and Kenyon-Mathieu, C. Linear Programming Relaxations of Maxcut. ACM-SIAM, ACM-SIAM Symposium on Discrete Algorithms.
Bansal, N., Correa, J. R., Kenyon, C., and Sviridenko, M. Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes. Mathematics of Operations Research 31, 1 (Feb 2006), 31-49.
Das, A., and Kenyon, C. On hierarchical diameter-clustering, and the supplier problems. In Fourth Workshop on Approximation and Online Algorithms (Zurich, Sep 2006), Springer Verlag, Lecture Notes in Computer Science. [ pdf ]
Kenyon, C., and Sellmann, M. Uncertainty/Time Trade-Offs for Linear and Integer Programming. In Proceedings of the Third International Conference on Integration of AI and OR Techniques (CP-AI-OR) (2006), Springer Verlag, pp. 126-138.
Klein, P. N. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the Thirty-Eighth ACM Symposium on Theory of Computing (2006), pp. 524-533. [ pdf ]
Klein, P. N. A linear-time approximation scheme for TSP for planar weighted graphs. In Proceedings of the Forty-Sixth IEEE Symposium on Foundations of Computer Science (2005), pp. 647-656. [ pdf ]
Sellmann, M. Approximated Consistency for the Automatic Recording Constraint. In Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming (CP) (2005), Springer, pp. 822-826. [ postscript | pdf ]
Kenyon, C., Rabani, Y., and Sinclair, A. Low Distortion Maps Between Point Sets. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing (STOC) (May 2004), pp. 272-280. [ pdf ]
Correa, J., and Kenyon, C. Asymptotic Approximation Schemes for Two-Dimensional Packing. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2004), pp. 186-195. [ pdf ]
Klein, P. N., Krishnan, R., Raghavachari, B., and Ravi, R. Approximation algorithms for finding low-degree subgraphs. Networks 44 (2004), 203-215. [ pdf ]
Sellmann, M. The Practice of Approximated Consistency for Knapsack Constraints. In Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI) (2004), AAAI Press, pp. 179-184. [ postscript | pdf ]
Buchsbaum, A. L., Karloff, H., Kenyon, C., Reingold, N., and Thorup, M. OPT versus LOAD in Dynamic Storage Allocation. SIAM Journal on Computing 33, 3 (2003), 632-646. [ pdf ]
Sellmann, M. Approximated Consistency for Knapsack Constraints. In Proceedings of the Ninth International Conference on the Principles and Practices of Contraint Programming (CP) (2003), Springer, pp. 679-693. [ postscript | pdf ]
Sellmann, M., Sensen, N., and Timajev, L. Multicommodity Flow Approximation Used for Exact Graph Partitioning. In Proceedings of the Eleventh Annual European Symposium on Algorithms (ESA) (2003), Springer, pp. 752-764. [ postscript | pdf ]
Golin, M. J., Kenyon, C., and Young, N. E. Huffman Coding with Unequal Letter Costs. In Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing (STOC) (2002), pp. 785-791. [ pdf ]
Kenyon, C., Schabanel, N., and Young, N. Polynomial-time Approximation Scheme for Data Broadcast. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC) (May 2000), pp. 659-666. [ pdf ]
Karger, D. R., Klein, P. N., Stein, C., Thorup, M., and Young, N. E. Rounding algorithms for a geometric embedding relaxation of minimum multiway cut. In Proceedings of the ACM Symposium on Theory of Computing (1999), pp. 668-678. [ pdf ]
Klein, P. N., and Young, N. E. On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms. In Proceedings of the Integer Programming and Combinatorial Optimization (1999), pp. 320-327. [ pdf ]
Arora, S., Grigni, M., Karger, D. R., Klein, P. N., and Woloszyn, A. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the Symposium on Discrete Algorithms (1998), pp. 33-41. [ pdf ]
Klein, P. N., and Lu, H.-I. Space-efficient approximation algorithms for MAXCUT and COLORING semidefinite programs. In Proceedings of the Ninth International Symposium on Algorithms and Computation (1998), pp. 387-396. [ pdf ]
Klein, P. N., Plotkin, S. A., Rao, S., and Tardos, E. Approximation Algorithms for Steiner and Directed Multicuts. Journal of Algorithms 22 (1997), 241-269. [ pdf ]
Klein, P. N., and Lu, H.-I. Efficient approximation algorithms for semidefinite programs arising from MAX-CUT and COLORING. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (1996), pp. 338-347. [ pdf ]
Agrawal, A., Klein, P. N., and Ravi, R. When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks. SIAM Journal on Computing 24 (1995), 440-456. [ pdf ]
Klein, P. N., Rao, S., Agrawal, A., and Ravi, R. An approximate max-flow min-cut relation for multicommodity flow, with applications. Combinatorica 15 (1995), 187-202.
Klein, P. N., and Ravi, R. A nearly best-possible approximation algorithm for node-weighted Steiner trees. Journal of Algorithms 19, 1 (1995), 104-115. [ pdf ]
Klein, P. N. A data structure for bicategories, with application to speeding up an approximation algorithm. Information Processing Letters 52, 6 (1994), 303-307. [ pdf ]
Klein, P. N., Plotkin, S., Stein, C., and Tardos, E. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing 23 (1994), 466-487. [ pdf ]
Klein, P. N., Plotkin, S. A., and Rao, S. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the ACM Symposium on Theory of Computing (1993), pp. 682-690. [ pdf ]
Klein, P. N., and Stein, C. A parallel algorithm for approximating the minimum cycle cover. Algorithmica 9 (1993), 23-31. [ pdf ]
Klein, P. N., and Ravi, R. When cycles collapse: A general approximation technique for constraind two-connectivity problems. In Proceedings of the Third Conference on Integer Programming & Combinatorial Optimization (IPCO) (1993), G. Rinaldi and L. Wolsey, Eds., pp. 39-55.
Agrawal, A., Klein, P. N., and Ravi, R. Ordering problems approximated: register sufficiency, single-processor scheduling and interval graph completion. In Proceedings of the Eighteenth International Conference on Automata, Languages, and Programming (1991), pp. 751-762. [ pdf ]
| Page Owner: Webmaster | Last Modified: Mon Oct 23 15:23:37 2006 |