简介

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.