Approximating chromatic sum coloring of bipartite graphs in expected polynomial time
https://doi.org/10.15514/ISPRAS-2015-27(5)-11
Abstract
It is known that if P≠NP the sum coloring problem cannot be approximated within for some constant . We propose for arbitrary small an approximation scheme for this problem that works in expected polynomial time.
About the Authors
A. S. Asratian
Linkopings Universitet, Department of Mathematics
Sweden
Sweden
N. N. Kuzyurin
ISP RAS
Russian Federation
Russian Federation
References
1. B. Bollobas, Random graphs, second ed., Cambridge Univ. Press, Cambridge, 2001.
2. B. Bollobas, The chromatic number of random graphs, Combinatorica, 1988, v. 8, c. 49-55.
3. A. Frieze,C. McDiarmid, Algorithmic theory of random graphs, Random Structures and Algorithms, Jan.-March 1997, v. 10, n. 1-2, c. 5-42.
4. L. Kucera, The greedy coloring is a bad probabilistic algorithm, J. of Algorithms, Dec. 1991, v. 12, n. 4, c. 674-684.
5. R. Motwani and P. Raghavan, Randomized algorithms, Cambridge Univ. Press, 1995.
6. E. Kubicka, A.J. Schwenk, An introduction to chromatic sums, Proc. of ACM Computer Science Conference, 1989, c. 39-45.
7. A. Bar-Noy, G. Kortsarz, Minimum color sum of bipartite graphs, J. of Algorithms, 1998, v. 28, c. 339-365.
8. K. Giaro, R. Janczewski, M. Kubale, M. Malafiejski, A 27/26-approximation algorithm for the chromatic sum coloring of bipartite graphs, Proc. APPROX 2002, LNCS v. 2462, c. 135-145.
9. M. Krivelevich , V.H. Vu, Approximating the independence number and the chromatic number in expected polynomial time, J. Combin. Optimization, 2002, v. 6, c. 143-155.
Review
For citations:
Asratian A.S., Kuzyurin N.N. Approximating chromatic sum coloring of bipartite graphs in expected polynomial time. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(5):191-198. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(5)-11
Email this article 