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
U2 - 10.1007/978-3-540-68891-4_25
DO - 10.1007/978-3-540-68891-4_25
M3 - ???researchoutput.researchoutputtypes.contributiontobookanthology.conference???
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 -