Department of Mathematical Sciences
Events
People
Colloquia and Seminars
Conferences
Centers
Positions
Areas of Research
About the Department
Alumni 
Faculty
Egon Balas, Thomas Lord University Professor of Operations Research D.Sc.Ec., University of Brussels; D.U., (Math) University of Paris Email: eb17@andrew.cmu.edu Office: GSIA 232B Phone: 4122682285 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 threeindex assignment polytope and the jobshopscheduling polyhedron. The algorythmic line of my research involves the characterization of classes of graphs for which the maximumweight clique problem (NPcomplete in general) is polynomially solvable. Several such classes have been characterized via the concept of a polynomialsized clique basis, and the results have led to improved algorithms for the maximumweight clique problem on arbitrary graphs. Other algorithmic results include the efficient solution or approximation methods for the 01 knapsack problem, the asymmetric traveling salesman and the prizecollecting traveling salesman problems, set covering, traffic assignment in communication satellites, and the minimum makespan problem of job shop scheduling.Selected Publications:
