Magnús M. Halldórsson
Guy Kortsarz
Skip Abstract Section
Abstract
We consider the scheduling of biprocessor jobs under sum objective (BPSMSM). 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 a given multigraph, that is, a partition of its edge set into matchings M1,…,Mt minimizing Σi=1ti|Mi|.
This problem is APX-hard, even in the case of bipartite graphs [Marx 2009]. This special case is closely related to the classic open shop scheduling problem. We give a 1.8298-approximation algorithm for BPSMSM improving the previously best ratio known of 2 [Bar-Noy et al. 1998]. The algorithm combines a configuration LP with greedy methods, using nonstandard randomized rounding on the LP fractions. We also give an efficient combinatorial 1.8886-approximation algorithm for the case of simple graphs, which gives an improved 1.79568 + O(log d¯/d¯)-approximation in graphs of large average degree d¯.
- Afrati, F. N., Bampis, E., Fishkin, A. V., Jansen, K., and Kenyon, C. 2000. Scheduling to minimize the average completion time of dedicated tasks. In Proceedings of the 20th Conference on Foundations of Software Technology and Theoretical Computer Science (FST TCS00). S. Kapoor and S. Prasad Eds., Lecture Notes in Computer Science, vol. 1974. Springer, 454--464. Google Scholar
Digital Library
- Bansal, N. and Sviridenko, M. 2006. The Santa Claus problem. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing. 31--40. Google ScholarDigital Library
- Bar-Noy, A., Bellare, M., Halldórsson, M. M., Shachnai, H., and Tamir, T. 1998. On chromatic sums and distributed resource allocation. Inf. Comput. 140, 2, 183--202. Google ScholarDigital Library
- Bar-Noy, A. and Kortsarz, G. 1998. Minimum color sum of bipartite graphs. J. Algor. 28, 2, 339--365. Google ScholarDigital Library
- Charikar, M., Chekuri, C., Goel, A., Guha, S., and Plotkin, S. A. 1998. Approximating a finite metric by a small number of tree metrics. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 379--388. Google ScholarDigital Library
- Chekuri, C. and Khanna, S. 2004. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. Chapman & Hall/CRC, Chapter 11. Google ScholarDigital Library
- Chudak, F. A. and Shmoys, D. B. 2003. Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1, 1--25. Google ScholarDigital Library
- Chuzhoy, J., Ostrovsky, R., and Rabani, Y. 2006. Approximation algorithms for the job interval selection problem and related scheduling problems. Math. Oper. Res. 31, 4, 730--738. Google ScholarDigital Library
- Coffman, Jr, E. G., Garey, M. R., Johnson, D. S., and LaPaugh, A. S. 1985. Scheduling file transfers. SIAM J. Comput. 14, 3, 744--780.Google ScholarCross Ref
- Cook, W., Cunningham, W., Pulleyblank, W., and Schrijver., A. 1998. Combinatorial Optimization. John Wiley and Sons. Google ScholarDigital Library
- Dobson, G. and Karmarkar, U. S. 1989. Simultaneous resource scheduling to minimize weighted flow times. Open. Res. 37, 4, pp. 592--600.Google ScholarDigital Library
- Epstein, L., Halldórsson, M. M., Levin, A., and Shachnai, H. 2008. Weighted sum coloring in batch scheduling of conflicting jobs. Algorithmica 55, 4, 643--665. Google ScholarDigital Library
- Fishkin, A. V., Jansen, K., and Porkolab, L. 2001. On minimizing average weighted completion time of multiprocessor tasks with release dates. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming (ICALP01). F. Orejas, P. G. Spirakis, and J. van Leeuwen, Eds., Lecture Notes in Computer Science, vol. 2076. Springer, 875--886. Google ScholarDigital Library
- Gandhi, R., Halldórsson, M. M., Kortsarz, G., and Shachnai, H. 2008. Approximating non-preemptive open-shop scheduling and related problems. ACM Trans. Algor. 4, 1.Google ScholarDigital Library
- Gandhi, R. and Mestre, J. 2009. Combinatorial algorithms for data migration to minimize average completion time. Algorithmica 54, 1, 54--71. Google ScholarDigital Library
- Gehringer, E. F., Siewiorek, D., and Segall, Z. 1986. Parallel Processing: The Cm* Experience. Digital Press, Newton, MA. Google ScholarDigital Library
- Giaro, K., Kubale, M., Malafiejski, M., and Piwakowski, K. 2002. Dedicated scheduling of biprocessor tasks to minimize mean flow time. In Proceedings of the 4th International Conference on Parallel Processing and Applied Mathematics (PPAM01). Revised Papers. R. Wyrzykowski, J. Dongarra, M. Paprzycki, and J. Wasniewski, Eds., Lecture Notes in Computer Science, vol. 2328. Springer, 87--96. Google ScholarDigital Library
- Hall, L. A., Schulz, A. S., Shmoys, D. B., and Wein, J. 1997. Scheduling to minimize average completion time: Off-Line and on-line approximation algorithms. Math. Oper. Res. 22, 513--544. Google ScholarDigital Library
- Halldórsson, M. M. and Kortsarz, G. 2002. Tools for multicoloring with applications to planar graphs and partial k-trees. J. Algor. 42, 2, 334--366.Google ScholarDigital Library
- Halldórsson, M. M., Kortsarz, G., and Shachnai, H. 2003. Sum coloring interval and k-claw free graphs with application to scheduling dependent jobs. Algorithmica 37, 187--209.Google ScholarDigital Library
- Hardy, G. H., Littlewood, J., and Pólya, G. 1952. Inequalities, 2nd Ed. Cambridge University Press.Google Scholar
- Jain, K. 2001. A factor 2 approximation algorithm for the generalized steiner network problem. Combinatorica 21, 1, 39--60.Google ScholarCross Ref
- Khachiyan, L. 1980. Polynomial-Time algorithm for linear programming. USSR Comput. Math. Math. Phys. 20, 53--72.Google ScholarCross Ref
- Kim, Y. A. 2005. Data migration to minimize the total completion time. J. Algor. 55, 1, 42--57. Google ScholarDigital Library
- Krawczyk, H. and Kubale, M. 1985. An approximation algorithm for diagnostic test scheduling in multicomputer systems. IEEE Trans. Comput. 34, 9, 869--872. Google ScholarDigital Library
- Kubale, M. 1996. Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors. Euro. J. Oper. Res. 94, 2, 242--251.Google ScholarCross Ref
- Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., and Shmoys, D. B. 1993. Logistics of Production and Inventory. Handbooks in Operations Research and Management Science, vol. 4. North-Holland, 445--522.Google Scholar
- Malafiejski, M., Giaro, K., Janczewski, R., and Kubale, M. 2004. Sum coloring of bipartite graphs with bounded degree. Algorithmica 40, 4, 235--244. Google ScholarDigital Library
- Marx, D. 2004. Minimum sum multicoloring on the edges of planar graphs and partial k-trees. In Proceedings of the 2nd International Workshop on Approximation and Online Algorithms (WAOA04). G. Persiano and R. Solis-Oba Eds., Lecture Notes in Computer Science, vol. 3351. Springer, 9--22. Google ScholarDigital Library
- Marx, D. 2005. A short proof of the np-completeness of minimum sum interval coloring. Oper. Res. Lett. 33, 4, 382--384. Google ScholarDigital Library
- Marx, D. 2006. Minimum sum multicoloring on the edges of trees. Theor. Comput. Sci. 361, 2-3, 133--149. Google ScholarDigital Library
- Marx, D. 2009. Complexity results for minimum sum edge coloring. Discr. Appl. Math. 157, 5, 1034--1045. Google ScholarDigital Library
- Mestre, J. 2008. Adaptive local ratio. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA08). S.-H. Teng, Ed., SIAM, 152--160. Google ScholarDigital Library
- Nutov, Z., Beniaminy, I., and Yuster, R. 2006. A (1−1/e)-approximation algorithm for the generalized assignment problem. Oper. Res. Lett. 34, 3, 283--288. Google ScholarDigital Library
- Queyranne, M. and Sviridenko, M. 2002a. A (2+epsilon)-approximation algorithm for the generalized preemptive open shop problem with minsum objective. J. Algor. 45, 2, 202--212. Google ScholarDigital Library
- Queyranne, M. and Sviridenko, M. 2002b. Approximation algorithms for shop scheduling problems with minsum objective. J. Schedul. 5, 4, 287--305.Google ScholarCross Ref
- Schulz, A. S. and Skutella, M. 2002. Scheduling unrelated machines by randomized rounding. SIAM J. Discr. Math. 15, 4, 450--469. Google ScholarDigital Library
- Sviridenko, M. 2002. An improved approximation algorithm for the metric uncapacitated facility location problem. In Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization (IPCO02). 240--257. Google ScholarDigital Library
- Vizing, V. G. 1964. On an estimate of the chromatic class of a p-graph. Diskret. Analiz no. 3, 25--30.Google Scholar
Index Terms
- Sum edge coloring of multigraphs via configuration LP
Recommendations
Min sum edge coloring in multigraphs via configuration LP
IPCO'08: Proceedings of the 13th international conference on Integer programming and combinatorial optimizationWe 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. ...
Edge-coloring almost bipartite multigraphs
Bipartite multigraphs have chromatic index equal to the largest degree d. We consider multigraphs obtained by inserting k vertices in edges of a connected bipartite multigraph, and show that the chromatic index may increase to at most d+1. We further ...
The neighbour sum distinguishing relaxed edge colouring
Highlights- We introduce a neighbour sum distinguishing d-relaxed edge colouring which generalizes two well-known versions of edge colouring. Our aim is to propose a ...
AbstractA k-edge colouring (not necessarily proper) of a graph with colours in { 1 , 2 , … , k } is neighbour sum distinguishing if, for any two adjacent vertices, the sums of the colours of the edges incident with each of them are distinct. ...
Comments