Min sum edge coloring in multigraphs via configuration LP

Magnús M. Halldórsson, Guy Kortsarz, Maxim Sviridenko

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


We consider the scheduling of biprocessor jobs under sum objective (BPSMS). Given a collection of unit-length jobs where each job requires the use of two processors, find a schedule such that no two jobs involving the same processor run concurrently. The objective is to minimize the sum of the completion times of the jobs. Equivalently, we would like to find a sum edge coloring of the given multigraphs, i.e. a partition of its edge set into matchings M 1,...,M t minimizing . This problem is APX-hard even in the case of bipartite graphs [M04]. This special case is closely related to the classic open shop scheduling problem. We give a 1.829-approximation algorithm for BPSMS that combines a configuration LP with greedy methods improving the previously best known ratio of 2 [BBH+98]. The algorithm uses the fractions derived from the configuration LP and a non-standard randomized rounding. We also give a purely combinatorial and practical algorithm for the case of simple graphs, with a 1.8861-approximation ratio.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 13th International Conference, IPCO 2008, Proceedings
Number of pages15
StatePublished - 2008
Event13th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2008 - Bertinoro, Italy
Duration: May 26 2008May 28 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5035 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other13th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2008

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


  • Approximation algorithms
  • Configuration LP
  • Edge scheduling


Dive into the research topics of 'Min sum edge coloring in multigraphs via configuration LP'. Together they form a unique fingerprint.

Cite this