Document Open Access Logo

On Weighted Bipartite Edge Coloring

Authors Arindam Khan, Mohit Singh

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2015.136.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Author Details

Arindam Khan
Mohit Singh

Cite AsGet BibTex

Arindam Khan and Mohit Singh. On Weighted Bipartite Edge Coloring. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 136-150, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.FSTTCS.2015.136

Abstract

We study weighted bipartite edge coloring problem, which is a generalization of two classical problems: bin packing and edge coloring. This problem has been inspired from the study of Clos networks in multirate switching environment in communication networks. In weighted bipartite edge coloring problem, we are given an edge-weighted bipartite multi-graph G=(V,E) with weights w:E\rightarrow [0,1]. The goal is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring of the weighted graph is called a proper weighted coloring if the sum of the weights of the edges incident to a vertex of any color is at most one. Chung and Ross conjectured 2m-1 colors are sufficient for a proper weighted coloring, where m denotes the minimum number of unit sized bins needed to pack the weights of all edges incident at any vertex. We give an algorithm that returns a coloring with at most \lceil 2.2223m \rceil colors improving on the previous result of \frac{9m}{4} by Feige and Singh. Our algorithm is purely combinatorial and combines the König's theorem for edge coloring bipartite graphs and first-fit decreasing heuristic for bin packing. However, our analysis uses configuration linear program for the bin packing problem to give the improved result.
Keywords
  • Edge coloring
  • Bin packing
  • Clos networks
  • Approximation algorithms
  • Graph algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. John Beetem, Monty Denneau, and Don Weingarten. The gf11 supercomputer. In International Symposium on Computer architecture, pages 108-115, 1985. Google Scholar
  2. Shun-Ping Chung and Keith W. Ross. On nonblocking multirate interconnection networks. SIAM Journal on Computing, 20(4):726-736, 1991. Google Scholar
  3. C. Clos. A study of nonblocking switching networks. Bell System Technical Journal, 32(2):406-424, 1953. Google Scholar
  4. Edward G. Coffman Jr, János Csirik, Gábor Galambos, Silvano Martello, and Daniele Vigo. Bin packing approximation algorithms: survey and classification. In Handbook of Combinatorial Optimization, pages 455-531. Springer, 2013. Google Scholar
  5. J. Correa and M. X. Goemans. Improved bounds on nonblocking 3-stage clos networks. SIAM Journal of Computing, 37:870-894, 2007. Google Scholar
  6. D. Z. Du, B. Gao, F. K. Hwang, and J. H. Kim. On multirate rearrangeable clos networks. SIAM Journal of Computing, 28(2):463-470, 1999. Google Scholar
  7. Uriel Feige and Mohit Singh. Edge coloring and decompositions of weighted graphs. In ESA, pages 405-416, 2008. Google Scholar
  8. Michael R. Garey, Ronald L. Graham, and Jeffrey D. Ullman. Worst-case analysis of memory allocation algorithms. In STOC, pages 143-150. ACM, 1972. Google Scholar
  9. Rebecca Hoberg and Thomas Rothvoß. A logarithmic additive integrality gap for bin packing. CoRR, abs/1503.08796, 2015. Google Scholar
  10. Ian Holyer. The NP-completeness of edge-coloring. SIAM Journal on Computing, 10(4):718-720, 1981. Google Scholar
  11. A. Itoh, W. Takahashi, H. Nagano, M. Kurisaka, and S. Iwasaki. Practical implementation and packaging technologies for a large-scale atm switching system. Journal of Selected Areas in Communications, 9:1280-1288, 1991. Google Scholar
  12. Narendra Karmarkar and Richard M Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In FOCS, pages 312-320. IEEE, 1982. Google Scholar
  13. Arindam Khan. Approximation Algorithms for Multidimensional Bin Packing. PhD thesis, Georgia Institute of Technology, Atlanta, 2015. Google Scholar
  14. D. König. Graphok és alkalmazásuk a determinánsok és a halmazok elméletére. Mathematikai és Természettudományi Ertesito, 34:104-119, 1916. Google Scholar
  15. Riccardo Melen and Jonathan S. Turner. Nonblocking multirate distribution networks. IEEE Transactions on Communications, 41(2):362-369, 1993. Google Scholar
  16. Hung Q. Ngo and Van H. Vu. Multirate rearrangeable clos networks and a generalized edge-coloring problem on bipartite graphs. SIAM J. Comput., 32(4):1040-1049, 2003. Google Scholar
  17. Thomas Rothvoß. Approximating bin packing within o(log opt * log log opt) bins. In FOCS, pages 20-29, 2013. Google Scholar
  18. Claude E. Shannon. A theorem on coloring the lines of a network. Journal of Mathematics and Physics, 28(2):148-151, 1949. Google Scholar
  19. T. D. Slepian. Two theorems on a particular crossbar switching. unpublished manuscript, 1958. Google Scholar
  20. Michael Stiebitz, Diego Scheide, Bjarne Toft, and Lene M. Favrholdt. Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture, volume 75. John Wiley & Sons, 2012. Google Scholar
  21. Peter Guthrie Tait. Remarks on the colouring of maps. Proc. Roy. Soc. Edinburgh, 10(729):501-503, 1880. Google Scholar
  22. V. G. Vizing. On an estimate of the chromatic class of a p-graph (in russian). Diskret. Analiz, 3:23-30, 1964. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact