Combinatorial Optimization

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

    Solving a combinatorial problem using a local optimization in ant based system

  • D. Dumitrescu
  • C-M. Pintea
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    Local optimizations introduced to obtain improved tours for Traveling Salesman Problem have a great impact on the final solution. That is way we introduce a new ant system algorithm with a new local updating pheromone rule, and the tours are improved using k-opt techniques. The tests use different parameters, in order to obtain solutions close … Read more

    Approximating the Chromatic Number of a Graph by Semidefinite Programming

  • N. Gvozdenovic
  • Monique Laurent
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

    We investigate hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. We introduce an operator $\Psi$ mapping any graph parameter $\beta(G)$, nested between the stability number $\alpha(G)$ and $\chi(\bar G)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\omega(G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if $\beta(G)$ is. As an … Read more

    Alternative Formulation for the p-median Problem

  • Sourour Elloumi
    • Categories Combinatorial Optimization, Facility Planning and Design Tags , , ,

    Given a set of clients and a set of potential sites for facilities, several location problems consist of opening a set of sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated facility location problem. We propose a new formulation of this problem … 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

    On Ants, Bacteria and Dynamic Environments

  • Carlos Fernandes
  • Vitorino Ramos
  • Agostinho C. Rosa
    • Categories Global Optimization, Meta Heuristics, Robust Optimization Tags , , , ,

    Wasps, bees, ants and termites all make effective use of their environment and resources by displaying collective “swarm” intelligence. Termite colonies – for instance – build nests with a complexity far beyond the comprehension of the individual termite, while ant colonies dynamically allocate labor to various vital tasks such as foraging or defense without any … Read more

    MW: A Software Framework for Combinatorial Optimization on Computational Grids

  • Wasu Glankwamdee
  • Jeff Linderoth
    • Categories Combinatorial Optimization, Parallel Algorithms Tags , , ,

    Our goal in this paper is to demonstrate that branch-and-bound algorithms for combinatorial optimization can be effectively implemented on a relatively new type of multiprocessor platform known as a computational grid. We will argue that to easily and effectively harness the power of computational grids for branch-and-bound algorithms, the master-worker paradigm should be used to … Read more

    TTTPLOTS: A perl program to create time-to-target plots

  • Renata M. Aiex
  • Mauricio G.C. Resende
  • Celso C. Ribeiro
    • Categories Combinatorial Optimization, Optimization Software Benchmark Tags , ,

    This papers describes a perl language program to create time-to-target solution value plots for measured CPU times that are assumed to fit a shifted exponential distribution. This is often the case in local search based heuristics for combinatorial optimization, such as simulated annealing, genetic algorithms, iterated local search, tabu search, WalkSAT, and GRASP. Such plots … Read more