Algorithms for Combinatorial Optimization
Topic status: Active
Research Areas
| Combinatorial Optimization |
People
| Glencora Borradaile |
| Philip Klein |
| Claire Mathieu |
| Meinolf Sellmann |
Publications
Aron, I., Leventhal, D., and Sellmann, M. A Totally Unimodular Description of the Consistent Value Polytope for Binary CSPs. In Proceedings of the Third International Conference on Integration of AI and OR Techniques (CP-AI-OR) (2006), Springer Verlag, pp. 16-28. [ pdf ]
Borradaile, G., and Klein, P. N. An O(n log n) algorithm for maximum st-flow in a directed planar graph. In Symposium on Discrete Algorithms (2006), pp. 524-533. [ 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.
Gellermann, T., Sellmann, M., and Wright, R. Shorter Path Constraints for the Resource Constrained Shortest Path Problem. In Proceedings of the Second International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization (CPAIOR) (2005), Springer, pp. 201-216. [ postscript | 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 ]
Gomes, C., Sellmann, M., van Es, C., and van Es, H. The Challenge of Generating Spatially Balanced Scientific Experiment Designs. In Proceedings of the First International Conference on the Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR) (2004), Springer, pp. 387-394. [ postscript | 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 ]
Sellmann, M. Theoretical Foundations of CP-based Largrangian Relaxation. In Proceedings of the Tenth International Conference on the Principles and Practice of Constraint Programming (CP) (2004), Springer, pp. 634-647. [ postscript | 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. Cost-Based Filtering for Shorter Path Constraints. In Proceedings of the Ninth International Conference on the Principles and Practices of Contraint Programming (CP) (2003), Springer, pp. 694-708. [ postscript | pdf ]
Sellmann, M., and Fahle, T. Constraint Programming Based Lagrangian Relaxation for the Automatic Recording Problem. Annals of Operations Research (AOR) 118 (2003), 17-33. [ 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 ]
Fahle, T., and Sellmann, M. Cost-Based Filtering for the Constrained Knapsack Problem. Annals of Operations Research (AOR) 115 (2002), 73-93. [ postscript | pdf ]
Fahle, T., Junker, U., Karisch, S. E., Kohl, N., Sellmann, M., and Vaaben, B. Constraint Programming Based Column Generation for Crew Assignment. Journal of Heuristics (JOH), Kluwer Academic Publishers 8, 1 (2002), 59-81. [ postscript | pdf ]
Sellmann, M. An Arc-Consistency Algorithm for the Minimum Weight All Different Constraint. In Proceedings of the Eighth International Conference on the Principles and Practice of Constraint Programming (CP) (2002), Springer. [ postscript | pdf ]
Sellmann, M., Zervoudakis, K., Stamatopoulos, P., and Fahle, T. Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search. Annals of Operations Research (AOR) 115 (2002), 207-225. [ postscript | pdf ]
Sellmann, M., Kliewer, G., and Koberstein, A. Lagrangian Cardinality Cuts and Variable Fixing for Capacitated Network Design. In Proceedings of the Tenth Annual European Symposium on Algorithms (ESA) (2002), Springer, pp. 845-858. [ postscript | pdf ]
Sellmann, M. Reduction Techniques in Constraint Programming and Combinatorial Optimization. PhD thesis, University of Paderborn, 2002.
Sellmann, M., and Fahle, T. Coupling Variable Fixing Algorithms for the Automatic Recording Problem. In Proceedings of the Ninth Annual European Symposium on Algorithms (ESA) (2001), Springer, pp. 134-145. [ postscript ]
Klein, P. N. Finding the closest lattice vector when it's unusually close. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 937-941. [ pdf ]
Junker, U., Karisch, S. E., Kohl, N., Vaaben, B., Fahle, T., and Sellmann, M. A Framework for Constraint Programming Based Column Generation. In Proceedings of the Fifth International Conference on the Principles and Practice of Constraint Programming (CP) (1999), Springer, pp. 261-274. [ 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. Computing the edit-distance between unrooted ordered trees. In Proceedings of the European Symposium on Algorithms (1998), pp. 91-102. [ 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 ]
Henzinger, M. R., Klein, P. N., Rao, S., and Subramanian, S. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 1 (1997), 3-23. [ 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 Subramanian, S. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms 25 (1997), 205-220. [ 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 ]
Klein, P. N. Efficient parallel algorithms for chordal graphs. SIAM Journal on Computing 25, 4 (1996), 797-827. [ 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 ]
Karger, D. R., Klein, P. N., and Tarjan, R. E. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM 42 (1995), 321-328. [ 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., Cole, R., and Tarjan, R. E. A linear-work parallel algorithm for finding a minimum spanning tree. In Proceedings of the Sixth ACM Symposium on Parallel Algorithms and Architectures (1994), pp. 11-15. [ pdf ]
Khuller, S., Naor, J., and Klein, P. The lattice structure of flow in planar graphs. SIAM Journal on Discrete Mathematics 6, 3 (1993), 477-490. [ 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 |