Graphs and Matroids

Hyperbolic Polynomials Approach to Van der Waerden/Schrijver-Valiant like Conjectures :\

  • Leonid Gurvits
    • Categories Approximation Algorithms, Combinatorial Optimization, Graphs and Matroids Tags , , ,

    The paper describes various combinatorial and algorithmic applications of hyperbolic (multivariate) polynomials . Section 2.2 introduces a new class of polynomials , which include as hyperbolic polynomials as well volume polynomials $Vol(x_1C_1+…+x_nC_n)$ , where $C_i$ are convex compact subsets of $R^n$. This extension leads to randomized poly-time algorithm to approximate $M(C_1,…,C_n)$ (the mixed volume) within … Read more

    Set covering and packing formulations of graph coloring: algorithms and first polyhedral results

  • Pierre Hansen
  • Martine Labbé
  • David Schindl
    • Categories Branch and Cut Algorithms, Graphs and Matroids Tags , , ,

    We consider two (0,1)-linear programming formulations of the graph (vertex-)coloring problem, in which variables are associated to stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in … Read more

    Comparing Imperfection Ratio and Imperfection Index for Graph Classes

  • Arie M.C.A. Koster
  • Annegret K. Wagler
    • Categories Graphs and Matroids, Polyhedra Tags , ,

    Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It … Read more

    A novel integer programming formulation for the K-SONET ring assignment problem

  • Elder M. Macambira
  • Claudio N. Meneses
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories 0-1 Programming, Graphs and Matroids, Telecommunications Tags , , ,

    We consider the problem of interconnecting a set of customer sites using SONET rings of equal capacity, which can be defined as follows: Given an undirected graph G=(V,E) with nonnegative edge weight d(u,v), (u,v) in E, and two integers K and B, find a partition of the nodes of G into K subsets so that … Read more

    Combinatorial relaxations of the k-traveling salesman problem

  • Andrei Horbach
    • Categories Combinatorial Optimization, Graphs and Matroids Tags , , , ,

    The k-traveling salesman problem, or k-TSP is: given a graph with edge weights and an integer k, find a simple cycle of minimum weight visiting exactly k nodes. To obtain lower bounds for the traveling salesman problem the 2-matching relaxation and the 1-tree relaxation can be used. We generalize these two relaxations for the k-TSP. … Read more

    Embedded in the Shadow of the Separator

  • Frank Göring
  • Christoph Helmberg
  • Markus Wappler
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , ,

    We study the problem of maximizing the second smallest eigenvalue of the Laplace matrix of a graph over all nonnegative edge weightings with bounded total weight. The optimal value is the \emph{absolute algebraic connectivity} introduced by Fiedler, who proved tight connections of this value to the connectivity of the graph. Using semidefinite programming techniques and … Read more

    Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Graphs and Matroids, Semi-definite Programming Tags , ,

    Lov\’ asz and Schrijver [1991] have constructed semidefinite relaxations for the stable set polytope of a graph $G=(V,E)$ by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most $\alpha(G)$ steps, where $\alpha(G)$ is the stability number of $G$. Two other hierarchies of semidefinite bounds for the stability number have … Read more

    A semidefinite programming based heuristic for graph coloring

  • Igor Dukanovic
  • Franz Rendl
    • Categories Graphs and Matroids Tags ,

    The Lovasz theta function is a well-known polynomial lower bound on the chromatic number. . Any near optimal solution of its semidefinite programming formulation carries valuable information on how to color the graph. A self-contained presentation of the role of this formulation in obtaining heuristics for the graph coloring problem is presented. CitationSubmitted to Discrete … Read more

    Wavelength Assignment in Multi-Fiber WDM Networks by Generalized Edge Coloring

  • Arie M.C.A. Koster
    • Categories Graphs and Matroids, Network Optimization, Telecommunications Tags , , , ,

    In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results … Read more

    Reduction of symmetric semidefinite programs using the regular *-representation

  • Etienne de Klerk
  • Dmitrii V. Pasechnik
  • Alexander Schrijver
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , ,

    We consider semidefinite programming problems on which a permutation group is acting. We describe a general technique to reduce the size of such problems, exploiting the symmetry. The technique is based on a low-order matrix *-representation of the commutant (centralizer ring) of the matrix algebra generated by the permutation matrices. We apply it to extending … Read more