Improved approximation algorithms for MAXk-CUT and MAX BISECTION

1. F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimisation,SIAM Journal on Optimization 5 (1995), 13–51.

   Article  MathSciNet  MATH  Google Scholar 

2. S. Arora, D. Karger, and M. Karpinski, Polynomial time approximation schemes for dense instances of NP-hard problem,Proceedings of the 27th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1995, pp. 284–293.

   Google Scholar 

3. S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, Proof verification and hardness of approximation problems,Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, New York, 1992, pp. 14–23.

   Google Scholar 

4. E. Bofinger and V. J. Bofinger, The correlation of maxima in samples drawn from a bivariate normal distribution,The Australian Journal of Statistics 7 (1965), 57–61.

   MathSciNet  MATH  Google Scholar 

5. H. A. David,Order Statistics, Wiley, New York, 1980.

   Google Scholar 

6. W. F. de la Vega, MAXCUT has a randomized approximation scheme in dense graphs,Random Structures and Algorithms 8 (1996), 187–198.

   Article  MathSciNet  MATH  Google Scholar 

7. J. Galambos,The Asymptotic Theory of Extreme Order Statistics, Wiley, New York, 1978.

   MATH  Google Scholar 

8. M. X. Goemans and D. P. Williamson, 878-Approximation algorithms for MAXCUT and MAX2SAT,Proceedings of the 26th Annual ACM Symposium on Theory of Computing, ACM Press, 1994, New York, pp. 422–431.

   Google Scholar 

9. V. Kann, S. Khanna, J. Lagergren, and A. Panconesi, On the hardness of approximating MAX k-CUT and its dual, Technical Report TRITA-NA-9505, Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1995.

   Google Scholar 

10. D. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming,Proceedings of the 35th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, New York, 1994, pp. 2–13.

    Google Scholar 

11. C. H. Papadimitriou and M. Yannakakis, Optimization, approximation and complexity classes,Journal of Computer and System Sciences 43 (1991), 425–440.

    Article  MathSciNet  MATH  Google Scholar 

12. G. Sansone,Orthogonal Functions (translated from the Italian by A. H. Diamond), Interscience, New York, 1959.

    MATH  Google Scholar 

13. E. C. Titchmarsh,The Theory of Functions (second edition), Oxford University Press, Oxford, 1939.

    MATH  Google Scholar 

14. G. N. Watson, Notes on generating functions of polynomials: Hermite polynomials,Journal of the London Mathematical Society 8 (1933), 194–199.

    MATH  Google Scholar 

15. D. J. A. Welsh,Complexity: Knots, Colourings and Counting, London Mathematical Society Lecture Notes, volume 186, Cambridge University Press, Cambridge, 1993.

    MATH  Google Scholar 

16. L. A. Wolsey, Heuristic analysis, linear programming and branch and bound, inCombinatorial Optimization II, Mathematical Programming Study, volume 13, North-Holland, Amsterdam, 1980, pp. 121–134.

    Google Scholar 

Download references