The capacitated max k-cut problem

1. Ageev, A.A., Sviridenko, M.I.: An approximation algorithm for hypergraph max k-cut with given sizes of parts. Lecture Notes in Computer Science (Proceedings of ESA ’00), vol. 1879, pp. 32–41 (2000)

2. Ageev A., Hassin R. and Sviridenko M. (2001). A 0.5-approximation algorithm for max dicut with given sizes of parts. SIAM J. Discret. Math. 14(2): 246–255

   Article  MATH  MathSciNet  Google Scholar 

3. Andersson, G.: An approximation algorithm for max p-section. Lecture Notes in Computer Science (Proceedings of STACS’99), vol. 1563, pp. 237–247 (1999)

4. Aslidis A. (1990). Minimizing of overstowage in container ship operations. Oper. Res. 90: 457–471

   Google Scholar 

5. Avriel M. and Penn M. (1993). Exact and approximate solutions of the container ship stowage problem. Comput. Ind. Eng. 25: 271–274

   Article  Google Scholar 

6. Avriel M., Penn M., Shpirer N. and Witteboon S. (1997). Stowage planning for container ships to reduce the number of shifts. Ann. Oper. Res. 76: 55–71

   Article  Google Scholar 

7. Bollapragada S. and Garbiras M. (2004). Scheduling commercials on broadcast television. Oper. Res. 52(3): 337–345

   Article  Google Scholar 

8. de Klerk E., Pasechnik D.V. and Warners J.P. (2004). On approximate graph colouring and MAX k-CUT algorithms based on the θ-function. J. Comb. Optim. 8(3): 267–294

   Article  MATH  MathSciNet  Google Scholar 

9. Feige U. and Langberg M. (2001). Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithms 41: 174–211

   Article  MATH  MathSciNet  Google Scholar 

10. Frieze A. and Jerrum M. (1997). Improved approximation algorithms for max k-cut and max bisection. Algorithmica 18(1): 67–81

    Article  MATH  MathSciNet  Google Scholar 

11. Gaur, D., Krishnamurti, R.: The capacitated max k-cut problem. In: Proceedings of the International Conference on Computational Science and its Applications (2005), LNCS 3483, pp. 670–679

12. Goemans M.X. and Williamson D.P. (1995). Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. Assoc. Comput. Mach. 42: 1115–1145

    MATH  MathSciNet  Google Scholar 

13. Goemans M.X. and Williamson D.P. (2004). Approximation algorithms for MAX 3-CUT and other problems via complex semidefinite programming. J. Comput. Syst. Sci. 68(2): 442–470

    Article  MATH  MathSciNet  Google Scholar 

14. Johnson D.S., Papadimitriou C.H. and Yannakakis M. (1988). How easy is local search?. J. Comput. Syst. Sci. 37: 79–100

    Article  MATH  MathSciNet  Google Scholar 

15. Karloff, H.J.: Fast parallel algorithms for graph-theoretic problems: matching, coloring and partitioning. Ph.D. Thesis, UC Berkeley (1985)

16. Kann V., Khanna S., Lagergren J. and Panconesi A. (1997). On the hardness of approximating max k-cut and its dual. Chicago J. Theor. Comput. Sci. 2: 1–18

    MathSciNet  Google Scholar 

17. Orlin J.B., Punnen A.P. and Schulz A.S. (2004). Approximate local search in combinatorial optimization. SIAM J. Comput. 33(5): 1201–1214

    Article  MATH  MathSciNet  Google Scholar 

18. Papadimitriou C.H. and Steiglitz K. (1982). Combinatorial optimization: algorithms and complexity. Prentice-Hall, Englewood Cliffs

    MATH  Google Scholar 

19. Ye Y. (2001). A .699-approximation algorithm for max-bisection. Math. Program. (A) 90: 101–111

    Article  MATH  Google Scholar 

Download references