On a local search algorithm for the capacitated max-k-cut problem
Keywords:
Approximation ratio, local search, max- -cut problemAbstract
The local search algorithm for the capacitated max-k -cut problem proposed by Gaur et al. (2008) is not guaranteed to terminate. In this note, we modify the iterative step of their algorithm to make it terminate in a finite number of steps. The modified algorithm is pseudo-polynomial, and in a special case it is strongly polynomial. Moreover, we analyze the worst case bound of the modified algorithm and give some extensions.References
Ageev, A. A., Hassin, R. Sviridenko, M. I. 2001. A 0.5-approximation algorithm for MAX DICUT with given sizes of parts. SIAM Journal on Discrete Mathematics 14(2): 246-255.
Andersson, G. 1999. An approximation algorithm for max p-Section. Lecture Notes in Computer Science 1563: 237-247, Springer.
Angel, E. 2006. A survey of approximation results for local search algorithms. Lecture Notes in Computer Science 3484: 30-73, Springer.
Avriel, M., Penn, M., Shpirer, N. Witteboon, S. 1998. Stowage planning for container ships to reduce the number of shifts. Annals of Operations Research 76(0): 55-71.
Bollapragada, S. Garbiras, M. 2004. Scheduling commercials on broadcast television. Operations Research 52(3): 337-345.
Brunsch, T., Roglin, H., Rutten, C. Vredeveld, T. 2013. Smoothed performance guarantees for local search. Mathematical Programming, accepted for publication, online at:
http://link.springer.com/article/10.1007 %2Fs10107-013-0683-7#page-1.
Feige, U. Langberg, M. 2001. Approximation algorithms for maximization problems arising in graph partitioning. Journal of Algorithms 41(2): 174-211.
Frieze, A. Jerrum, M. 1997. Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18(1): 67-81.
Gaur, D. R., Krishnamurti, R. Kohli, R. 2008. The capacitated max- -cut problem. Mathematical Programming 115(1): 65-72.
Gaur, D. R., Krishnamurti, R. Kohli, R. 2011. Erratum to the capacitated max k-cut problem. Mathematical Programming 126(1): 191-191.
Gendreau, M. Potvin, J.-Y. 2005. Metaheuristics in combinatorial optimization. Annals of Operations Research 140(1): 189-213.
Hajirasouliha, I., Hormozdiari, F., Sahinalp, S. C. Birol, I. 2008. Optimal pooling for genome re-sequencing with ultra-high-throughput short-read technologies. Bioinformatics 24: i32-i40.
Johnson, D. S., Papadimitriou, C. H. Yannakakis, M. 1988. How easy is local search? Journal of Computer and System Sciences 37(1): 79-100.
Kann, V., Khanna, S., Lagergren, J. Panconesi, A. 1997. On the hardness of approximating MAX k-CUT and its dual. Chicago Journal of Theoretical Computer Science 2: 1-18.
Orlin, J. B., Punnen, A. P. Schulz, A. S. 2004. Approximate local search in combinatorial optimization. SIAM Journal on Computing 33(5): 1201-1214.
Ye, Y. 2001. A .699-approximation algorithm for Max-Bisection. Mathematical Programming 90(1): 101-111.
