TY - GEN

T1 - Min sum edge coloring in multigraphs via configuration LP

AU - Halldórsson, Magnús M.

AU - Kortsarz, Guy

AU - Sviridenko, Maxim

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

KW - Approximation algorithms

KW - Configuration LP

KW - Edge scheduling

UR - http://www.scopus.com/inward/record.url?scp=45749094207&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=45749094207&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-68891-4_25

DO - 10.1007/978-3-540-68891-4_25

M3 - Conference contribution

AN - SCOPUS:45749094207

SN - 3540688862

SN - 9783540688860

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 359

EP - 373

BT - Integer Programming and Combinatorial Optimization - 13th International Conference, IPCO 2008, Proceedings

T2 - 13th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2008

Y2 - 26 May 2008 through 28 May 2008

ER -