matching polytope

Temporal Bin Packing with Half-Capacity Jobs

  • Christopher Muir
  • Luke Marshall
  • Alejandro Toriello
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Scheduling Tags , , , ,

    Motivated by applications in cloud computing, we study a temporal bin packing problem with jobs that occupy half of a bin’s capacity. An instance is given by a set of jobs, each with a start and end time during which it must be processed, i.e., assigned to a bin. A bin can accommodate two jobs … Read more

    Clique Family Inequalities for the Stable Set Polytope of Quasi-Line Graphs

  • Gianpaolo Oriolo
    • Categories 0-1 Programming, Graphs and Matroids, Polyhedra Tags , , ,

    In one of fundamental work in combinatorial optimization Edmonds gave a complete linear description of the matching polytope. Matchings in a graph are equivalent to stable sets its line graph. Also the neighborhood of any vertex in a line graph partitions into two cliques: graphs with this latter property are called quasi-line graphs. Quasi-line graphs … Read more