Faculty Egon Balas, Thomas Lord University Professor of Operations Research
D.Sc.Ec., University of Brussels; D.U., (Math) University of Paris
E-mail: eb17@andrew.cmu.edu
Office: GSIA 232B
Phone: 412-268-2285

Research:

My research has theoretical and algorithmic aspects. The theory revolves mainly around polyhedral combinatorics, or attempts at describing various combinatorial structures by systems of linear inequalities. Recent examples are the polyhedral characterization of the convex hull of incidence vectors of perfectly matchable subgraphs of a graph, the identification of new families of facets of the asymmetric traveling salesman polytope, the three-index assignment polytope and the job-shop-scheduling polyhedron.

The algorythmic line of my research involves the characterization of classes of graphs for which the maximum-weight clique problem (NP-complete in general) is polynomially solvable. Several such classes have been characterized via the concept of a polynomial-sized clique basis, and the results have led to improved algorithms for the maximum-weight clique problem on arbitrary graphs.

Other algorithmic results include the efficient solution or approximation methods for the 0-1 knapsack problem, the asymmetric traveling salesman and the prize-collecting traveling salesman problems, set covering, traffic assignment in communication satellites, and the minimum makespan problem of job shop scheduling.

Selected Publications:

• Balas, E., Fischetti, M. and Pulleyblank, W. R. (1995), "The Precedence-Constrained Asymmetric Traveling Salesman Polytope," Mathematical Programming 68:241–265.
• Balas, E. (1995), "The Prize Collecting Traveling Salesman Problem: II. Polyhedral Results," Networks 25:199–216.
• Balas, E. (1989), "The Prize Collecting Traveling Salesman Problem," Networks 19:621–636.
• Balas, E. and Fischetti, M. (1993), "A Lifting Procedure for the Asymmetric Traveling Salesman Polytope and a Large New Class of Facets," Mathematical Programming 58: 325–352.
• Balas, E., Ceria, S. and Cornuejols, G. (1993), "A Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs," Mathematical Programming, 58: 295–324.
• Balas, E., and Xue, J. (1991), "Minimum Weighted Coloring of Triangulated Graphs, with Application to Weighted Vertex Packing in Arbitrary Graphs," SIAM Journal on Computing 20: 209–222.
• Balas, E. and Pulleyblank, W. R. (1988), "The Perfectly Matchable Subgraph Polytope of an Arbitrary Graph," Combinatorica 1988.
• Balas, E. (1989), "The Asymmetric Assignment Problem and Some New Facets of the Traveling Salesman Polytope on a Directed Graph," SIAM Journal on Discrete Mathematics, November 1989.