Combinatorial Optimization

J. Gouveia and J. Pfeiffer.
"A Semidefinite Approach to the $K_i$ Cover Problem",
Preprint, Universidade de Coimbra, OCtober 2012.
opt-online
N. Arima, S. Kim and M. Kojima.
"Simplified Copositive and Lagrangian Relaxations for Linearly Constrained Quadratic Optimization Problems in Continuous and Binary Variables",
Research Report B-469, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152-8552, October 2012.
opt-online
Ch. Buchheim and E. Traversi.
"Separable non-convex underestimators for binary quadratic programming",
Preprint, TU Dortmund, October 2012.
opt-online
D. Wei.
"On two relaxations of quadratically-constrained cardinality minimization",
Preprint, Department of Electrical Engineering and Computer Science, University of Michigan, October 2012.
opt-online
F. Furini and E. Traversi.
"Hybrid LP/SDP Bounding Procedure",
Preprint, LIPN, Universite Paris 13, October 2012.
opt-online
N. Arima, S. Kim and M. Kojima.
"A Quadratically Constrained Quadratic Optimization Model for Completely Positive Cone Programming",
Research Report B-468, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152-8552, September 2012.
opt-online
E. de Klerk, M. Eisenberg-Nagy, R. Sotirov, and Uwe Truetsch.
"Symmetry in RLT cuts for the quadratic assignment and standard quadratic optimization problems",
Preprint, Tilburg University, The Netherlands, December 2011.
opt-online
M. Laurent and A. Varvitsiotis.
"The Gram dimension of a graph",
Centrum Wiskunde & Informatica (CWI), Amsterdam, December 2011.
opt-online
J. Gouveia, P. A. Parrilo, and R. R. Thomas.
"Lifts of Convex Sets and Cone Factorizations",
CMUC, Department of Mathematics, University of Coimbra, 3001-454 Coimbra, Portugal, November 2011.
opt-online
L. Orecchia, S. Sachdeva, and N. K. Vishnoi.
"Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator",
MIT, November 2011.
opt-online
E. de Klerk and D. V. Pasechnik.
"Improved lower bounds for the 2-page crossing numbers of K(m,n) and K(n) via semidefinite programming",
Preprint, Tilburg University, October 2011.
opt-online
T. Mizutani and M. Yamashita.
"Correlative Sparsity Structures and Semidefinite Relaxations for Concave Cost Transportation Problems with Change of Variables",
Department of Information Systems Creation, Kanagawa University, 3-27-1 Rokkakubashi, Kanagawa-ku, Yokohama, Kanagawa, Japan, October 2011.
opt-online
K. K. Sivaramakrishnan and J. E. Mitchell.
"Properties of a Cutting Plane Method for Semidefinite Programming",
Technical Report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, September 2011.
opt-online
R. Sotirov.
"A tractable semidefinite programming relaxation for the graph partition problem",
Technical Report, Department of Econometrics and OR, Tilburg University, August 2011.
opt-online
S. S. Dey, D. A. Moran R. and J. P. Vielma.
"Strong Dual for Conic Mixed-Integer Programs",
Technical Report, H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, July 2011.
opt-online
S. Burer and H. Dong.
"Representing quadratically constrained quadratic programs as generalized copositive programs",
Technical Report, Applied Mathematical and Computational Sciences, University of Iowa, July 2011.
opt-online
M. Laurent and A. Varvitsiotis.
"Computing the Grothendieck constant of some graph classes",
Preprint, CWI, Amsterdam, June 2011.
opt-online
M. Chimani and Ph. Hungerländer.
"Exact Approaches to Multi-level Vertical Orderings",
Technical Report TR-FSUJ-CS-AE-11-02, v.1, Algorithm Engineering Group, Computer Science, FSU Jena, June 2011.
opt-online
M. Chimani and Ph. Hungerländer.
"Multi-level Verticality Optimization: Concept, Strategies, and Drawing Scheme",
Technical Report TR-FSUJ-CS-AE-11-01, v.1, Algorithm Engineering Group, Computer Science, FSU Jena, June 2011.
opt-online
E. de Klerk, M. E.-Nagy and R. Sotirov .
"On semidefinite programming bounds for graph bandwidth",
Working paper, Tilburg University, The Netherlands, May 2011.
opt-online
Ph. Hungerländer and F. Rendl.
"A Computational Study for the Single-Row Facility Layout Problem",
Technical Report, Alpen-Adria-Universität Klagenfurt, May 2011.
opt-online
B. Ghaddar, J. C. Vera and M. F. Anjos.
"An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming",
To appear in Proceedings of IPCO XV (2011), March 2011.
opt-online
M. Armbruster, C. Helmberg, M. Fuegenschuh, A. Martin.
"LP and SDP Branch-and-Cut Algorithms for the Minimum Graph Bisection Problem: A Computational Comparison",
Preprint 2011-6, Technische Universität Chemnitz, Fakultät für Mathematik, March 2011 .
opt-online
M. Ujvari.
"Applications of the inverse theta number in stable set problems",
Operations Research Report 2011-01, Department of Operations Research, Eötvös Loránd University of Sciences, Budapest, Hungary, February 2011.
opt-online
J. Chen and S. Burer.
"Globally Solving Nonconvex Quadratic Programming Problems via Completely Positive Programming",
Argonne National Laboratory Mathematics and Computer Science Division Preprint ANL/MCS-P1837-0211, February 2011.
opt-online
A. Letchford and L. Galli.
"Reformulating mixed-integer quadratically constrained quadratic programs",
Working Paper, Department of Management Science, Lancaster University, United Kingdom, January 2011.
opt-online
M. Ujvari.
"Four new upper bounds for the stability number of a graph",
Department of Operations Research, Eötvös Loránd University of Sciences, Budapest, Hungary, December 2010.
opt-online
J. B. Lasserre.
"New approximations for the cone of copositive matrices and its dual",
LAAS-CNRS and Institute of Mathematics, University of Toulouse, December 2010.
opt-online
V. Chandrasekaran, P. A. Parrilo, and A. S. Willsky.
"Convex Graph Invariants",
LIDS technical report 2855, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, December 2010.
opt-online
G. Eichfelder and J. Povh.
"On reformulations of nonconvex quadratic programs over convex cones by set-semidefinite constraints",
Preprint No. 342, Institut fuer Angewandte Mathematik, Martensstr. 3, D-91058 Erlangen, ISSN 1435-5833, 2010.
opt-online
X. Wu, H. D. Mittelmann, X. Wang, and J. Wang.
"On Computation of Performance Bounds of Optimal Index Assignment",
Department of Electrical and Computer Engineering, McMaster University, Hamilton, Ontario, Canada, December 2010.
opt-online
J. Briet, F. M. de Oliveira Filho, and F. Vallentin.
"Grothendieck inequalities for semidefinite programs with rank constraint",
CWI, Amsterdam, November 2010.
opt-online
X. Zheng, X. Sun, and D. Li.
"Convex Relaxations and Mixed-Integer Quadratic Reformulations for Cardinality Constrained Quadratic Programs",
Department of Management Science, School of Management, Fudan University, November 2010.
opt-online
H. D. Sherali, E. Dalkiran, and L. Liberti.
"Reduced RLT Representations for Nonconvex Polynomial Programming Problems",
Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State Universit, November 2010.
opt-online
H. Dong.
"Symmetric tensor approximation hierarchies for the completely positive cone",
Working paper, Applied Mathematics and Computational Sciences Program, University of Iowa, November 2010.
opt-online
J. Gouveia and T. K. Pong.
"Comparing SOS and SDP relaxations of sensor network localization",
Technical Report, Department of Mathematics, University of Washington, October 2010 .
opt-online
M. K. Carli Silva and L. Tuncel.
"Min-Max Theorems Related to Geometric Representations of Graphs and their SDPs",
Research Report, Department of Mathematics, Universtiy of Waterloo, Canada, October 2010.
opt-online
F. Jarre.
"Burer's Key Assumption for Semidefinite and Doubly Nonnegative Relaxations",
Technical report, Mathematisches Institut, Heinrich-Heine-Universität Düsseldorf .
opt-online
S. Gualandi, F. Maffioli, and C. Magni.
"A Branch-and-Price Approach to the k-Clustering Minimum Biclique Completion Problem",
Politecnico di Milano, Dipartimento di Elettronica e Informazione, September 2010.
opt-online
C. Buchheim and A. Wiegele.
"Semidefinite Relaxations for Non-Convex Quadratic Mixed-Integer Programming",
Technical Report, Alpen-Adria-Universitaet Klagenfurt, September 2010.
opt-online
D. Ge and Y. Ye.
"On Doubly Positive Semidefinite Programming Relaxations",
Working Paper, Stanford University, August 2010 .
opt-online
P. Hungerländer and F. Rendl.
"Semidefinite Relaxations of Ordering Problems",
Preprint, Alpen-Adria-Universität Klagenfurt, August 2010.
opt-online
K. Anstreicher.
"On convex relaxations for quadratically constrained quadratic programming",
Department of Management Sciences, University of Iowa, July 2010.
opt-online
E. De Klerk, F. M. De Oliveira Filho and D. V. Pasechnik.
"Relaxations of combinatorial problems via association schemes",
Tilbunrg University, July 2010, draft version of a chapter for "Handbook on SDP II" (M. Anjos and J. Lasserre, eds.), Springer.
opt-online
R. Sotirov.
"Combinatorial Optimization",
CentER Discussion Paper Tilburg University, The Netherlands, July 2010.
opt-online
E. de Klerk, C. Dobre, D. V. Pasechnik and R. Sotriov.
"On semidefinite programming relaxations of maximum k-section",
Preprint, Tilburg University, The Netherlands, June, 2010 .
opt-online
D. C. Gijswijt, H. D. Mittelmann, and A. Schrijver.
"Semidefinite code bounds based on quadruple distances",
CWI, May 2010.
opt-online
M. Kocvara.
"Truss topology design with integer variables made easy",
Preprint 2010/09, School of MAthematics, University of Birmingham, UK, May 2010 .
opt-online
Y. Ding, D. Ge, and H. Wolkowicz.
"On Equivalence of Semidefinite Relaxations for Quadratic Matrix Programming",
Research Report CORR 2010-02, University of Waterloo, Canada, april/2010.
opt-online
H. Dong and K. M. Anstreicher.
"Separating Doubly Nonnegative and Completely Positive Matrices",
Working paper, Dept. of Management Sciences, University of Iowa, Iowa City IA, March 2010.
opt-online
M. Ujvari.
"Strengthening weak sandwich theorems in the presence of inconnectivity",
Department of Operations Research, Eötvös Loránd University of Sciences, ORR report 2010-1, January 2010.
opt-online
Mirjam Duer.
"Copositive Programming - a Survey",
Institute of Mathematics and Computing Science, University of Groningen, November 2009.
opt-online
J. Briet, F. M. de Oliveira Filho and F. Vallentin.
"The positive semidefinite Grothendieck problem with rank constraint",
CWI, Amsterdam, October 2009.
opt-online
B. Ghaddar, J. C. Vera, and M. F. Anjos.
"New Relaxations for Binary Quadratic Problems Using Second-Order Cone Programming",
University of Waterloo, October 2009.
opt-online
A. Letchford and M. Soerensen.
"Binary positive semidefinite matrices and associated integer polytopes",
Working paper, Department of Management Science, Lancaster University, United Kingdom, September 2009.
opt-online
E. de Klerk and R. Sotirov.
"Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry",
CentER Discussion Paper, Tilburg University, The Netherlands, September 2009.
opt-online
Karthik Natarajan, Chung-Piaw Teo, and Zhichao Zheng.
"Mixed zero-one linear programs under objective uncertainty: a completely positive representation",
Department of Management Sciences, City University of Hong Kong, August 2009.
opt-online
I. Bomze.
"Building a completely positive factorization",
Technical Report TR-ISDS 2009-06, Department of Statistics and Decision Support Systems, University of Vienna, Austria, August 2009.
opt-online
S. Burer and A. Saxena.
"Old Wine in a New Bottle: The MILP Road to MIQCP",
Manuscript, Dept. of Management Sciences, University of Iowa, July 2009.
opt-online
E. A. Yildirim.
"On the Accuracy of Uniform Polyhedral Approximations of the Copositive Cone",
Technical Report, Bilkent University, Department of Industrial Engineering, July2009.
opt-online
J. Gouveia, M. Laurent, P. A. Parrilo and R. Thomas.
"A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs",
Preprint, Department of Mathematics, University of Washington, Seattle, July 2009 .
opt-online
G. Iyengar, D. J. Phillips and C. Stein.
"Approximating semidefinite packing problems",
Department of IEOR, Columbia University, June 2009.
opt-online
F. Göring, C. Helmberg and S. Reiss.
"Graph Realizations Associated with Minimizing the Maximum Eigenvalue of the Laplacian",
Preprint 2009-10, Fakultät für Mathematik, Technische Universität Chemnitz, D-09107 Chemnitz, May 2009.
To appear in Mathematical Programming.
opt-online
J. E. Mitchell.
"Cutting Plane Methods and Subgradient Methods",
Math Sciences, RPI, Troy, NY, May 2009. .
opt-online
N. Krislock and H. Wolkowicz.
"Explicit Sensor Network Localization using Semidefinite Representations and Facial Reductions",
University of Waterloo, May 2009.
opt-online
D. Bienstock.
"Eigenvalue techniques for proving bounds for convex objective, nonconvex programs",
Columbia University, March 2009.
opt-online
M. F. Anjos and G. Yen.
"Provably Near-Optimal Solutions for Very Large Single-Row Facility Layout Problems",
To appear in Optimization Methods and Software (accepted March 2009).
opt-online
J. Peng, H. Mittelmann and X. Li.
"A New Relaxation Framework for Quadratic Assignment Problems based on Matrix Splitting",
University of Illinois at Urbana-Champaign, February 2009.
opt-online
H. D. Mittelmann and F. Vallentin.
"High accuracy semidefinite programming bounds for kissing numbers",
School of Mathematical and Statistical Sciences, Arizona State Universtiy, February 2009.
opt-online
F. Jarre.
"Relating max-cut problems and binary linear feasibility problems",
Preprint, Mathematisches Institut, Universität Düsseldorf, February 2009 .
opt-online
E. De Klerk, C. Dobre and D. V. Pasechnik.
"Numerical block diagonalization of matrix $*$-algebras with application to semidefinite programming",
Preprint, Department of Econometrics and OR, Tilburg University, The Netherlands, February 2009.
opt-online
P. Biswas.
"Semidefinite Programming Approaches to Distance Geometry Problems",
PhD. Thesis, Department of Electrical Engineering, Stanford University, November 2008.
opt-online
S. Burer.
"Optimizing a Polyhedral-Semidefinite Relaxation of Completely Positive Programs",
Technical report, Department of Management Sciences, University of Iowa, December 2008.
opt-online
J. Gouveia, P. A. Parrilo and R. R. Thomas.
"Theta Bodies for Polynomial Ideals",
Preprint, Department of Mathematics, University of Washington, November 2008, revised January 2009.
opt-online
A. Saxena, P. Bonami and J. Lee.
"Convex Relaxations of Non-Convex Mixed Integer Quadratically Constrained Programs: Projected Formulations",
IBM Research Report RC24695, IBM T.J. Watson Research Center, Yorktown Heights, November 2008 .
opt-online
F. Göring, C. Helmberg and M. Wappler.
"The Rotational Dimension of a Graph",
Preprint 2008-16, Fakultät für Mathematik, Technische Universität Chemnitz, Germany, October 2008; to appear in Journal of Graph Theory.
opt-online
S. Kim, M. Kojima, and H. Waki.
"Exploiting Sparsity in SDP Relaxation for Sensor Network Localization",
Research report B-447, Tokyo Institute of Technology, January, 2008.
opt-online
C. Bachoc, G. Nebe, F. M. de Oliveira Filho, F. Vallentin.
"Lower Bounds for Measurable Chromatic Numbers",
CWI, Amsterdam, 2008.
opt-online, arXiv:0801.1059v1
M. F. Anjos and A. Vannelli.
"Computing Globally Optimal Solutions for Single-Row Layout Problems Using Semidefinite Programming and Cutting Planes",
University of Waterloo, Ontario, Canada, 2008.
To appear in INFORMS Journal on Computing, 2008 .
opt-online
X. Sun, C. Liu, D. Li and J. Gao.
"On Duality Gap in Binary Quadratic Programming",
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, August 2008.
opt-online
E. De Klerk, D. V. Pasechnik, and R. Sotirov.
"On semidefinite programming relaxations of the traveling salesman problem",
CentER Discussion Paper #2007-101 Tilburg University, The Netherlands, December 2007.
opt-online
N. Gvozdenovic, M. Laurent and F. Vallentin.
"Block-diagonal semidefinite programming hierarchies for 0/1 programming",
CWI Amsterdam, Dec. 2007.
opt-online
C. Buchheim, A. Wiegele, and L. Zheng.
"Exact Algorithms for the Quadratic Linear Ordering Problem",
Technical report (zaik2007-560), Zentrum f. Angewandte Informatik Köln, Nov. 2007.
opt-online
A. Atamturk, V. Narayanan.
"Lifting for Conic Mixed-Integer Programming",
Technical Report, Industrial Engineering and Operations Research Department, University of California, Berkeley, 2008.
opt-online
S. Burer and J. Chen.
"Relaxing the Optimality Conditions of Box QP",
Manuscript, Department of Management Sciences, University of Iowa, Iowa City, IA 52240, USA, October 2007..
opt-online
C. Bachoc and F. Vallentin.
"Optimality and uniqueness of the (4,10,1/6) spherical code",
CWI, Amsterdam, 2007.
opt-online
L. Faybusovich.
"Jordan-algebraic aspects of optimization: randomization",
Preprint, Department of Mathematics, University of Notre Dame, 2007.
opt-online
B. Ghaddar, M. Anjos, and F. Liers.
"A Branch-and-Cut Algorithm based on Semidefinite Programming for the Minimum k-Partition Problem",
Technical Report, Department of Managament Science, University of Waterloo, 2007.
opt-online
Etienne De Klerk, Renata Sotirov.
"Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem",
CenTER discussion paper, Tilburg University, The Netherlands, June 2007.
opt-online
F. Vallentin.
"Symmetry in semidefinite programs",
CWI, Amsterdam, 2007.
opt-online
Kurt M. Anstreicher.
"Semidefinite Programming versus the Reformulation-Linearization Technique for Nonconvex Quadratically Constrained Quadratic Programming",
Dept. of Management Sciences, University of Iowa, May 2007.
opt-online
F. Rendl and G. Rinaldi and A. Wiegele.
"Solving Max-Cut to Optimality by Intersecting Semidefinite and Polyhedral Relaxations",
Technical Report, Alpen-Adria-Universit\"at Klagenfurt, May 2007.
opt-online
I. Bomze, F. Frommlet and M. Locatelli.
"Gap, cosum, and product properties of the Lov\'asz-Schrijver bound on the clique number",
Technical Report, ISDS, University of Vienna.
opt-online
N. Gvozdenovic and M. Laurent.
"Computing semidefinite programming programming lower bounds for the (fractional) chromatic number via block diagonalization",
Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, February 2007.
opt-online
N. Gvozdenovic and M. Laurent.
"The operator $\Psi$ for the Chromatic Number of a Graph",
Centrum voor Wiskunde en Informatica, Kruislaan 413, 1098 SJ Amsterdam, February 2007..
opt-online
K. Anstreicher and S. Burer.
"Computable representations for convex hulls of low-dimensional quadratic forms",
Working paper, Dept. of Management Sciences, University of Iowa, February 2007.
opt-online
J. Povh and F. Rendl.
"A Copositive Programming Approach to Graph Partitioning",
Siam J. Optim., Vol. 18, No. 1, pp. 223-241, 2007.
Siam J. Optim.
F. Vallentin.
"Optimal Embeddings of Distance Regular Graphs into Euclidean Spaces",
Technical Report, CWI, Amsterdam, December 2006.
opt-online
Y. Ding, N. Krislock, J. Qian and H. Wolkowicz.
"Sensor Network Localization, Euclidean Distance Matrix Completions, and Graph Realization",
CORR 2006-23, Department of Combinatorics and Optimization, University of Waterloo, December 2006.
opt-online
A. M.-C. So, Y. Ye, and J. Zhang.
"A Unified Theorem on {SDP} Rank Reduction",
Department of Management Science and Engineering, Stanford University, November 2006. Revised Nov.~2007
opt-online, revised paper on Ye's homepage
U. Miklos.
"New descriptions of the Lovasz number and a Brooks-type theorem",
ORR report 2006-2, Department of Operations Research, Eötvös Lorand University of Sciences, Hungary, 2006.
opt-online
Y. Ding and H. Wolkowicz.
"A Matrix-lifting Semidefinite Relaxation for the Quadratic Assignment Problem",
CORR 06-22, Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario, Canada, September, 2006.
opt-online
Christine Bachoc, Frank Vallentin.
"Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps",
CWI, Amsterdam, 2006.
opt-online
E. de Klerk, M. W. Newman, D. V. Pasechnik, and R. Sotirov.
"On the Lovasz theta-number of almost regular graphs with application to Erdös-Renyi graphs",
CentER Discussion Paper 2006-93, Tilburg University, The Netherlands, September 2006.
opt-online
J. Povh and F. Rendl.
"Copositive and Semidefinite Relaxations of the Quadratic Assignment Problem",
Klagenfurt University, July 2006.
opt-online
I. M. Bomze, F. Frommlet, M. Locatelli.
"The first cut is the cheapest: improving SDP bounds for the clique number via copositivity",
ISDS, University of Vienna, August 2006.
opt-online
C. Bachoc and F. Vallentin.
"New upper bounds for kissing numbers from semidefinite programming",
CWI, Amsterdam, August 2006.
opt-online
P. Biswas, T.-C. Liang, T.-C. Wang, and Y. Ye .
"Semidefinite Programming Based Algorithms for Sensor Network Localization",
Working Paper posted 9/10/03 and updated 10/3/05; extended abstract appeared in IPSN 2004, full paper to appear in ACM J on Transactions on Sensor Networks 2006..
opt-online
A. M.-C. So and Y. Ye.
"Theory of semidefinite programming for sensor network localization",
Mathematical Programming 109 (2-3), 367-384, 2007.
opt-online
K. Varadarajan, S. Venkatesh, Y. Ye, Z. Jiawei.
"Approximating the Radii of Point Sets",
Working Paper posted 5/4/05; conference versions appeared in FOCS'02 and APPROX'04; full paper to appear in SIAM Journal on Computing.
opt-online
N. Gvozdenovic and M. Laurent.
"Semidefinite Bounds for the Stability Number of a Graph via Sums of Squares of Polynomials",
CWI Amsterdam, June 2005; extended version of the paper in Michael Jünger, Volker Kaibel (Eds.): 11th International IPCO Conference, Berlin, Germany, Proceedings. Springer 2005, submitted to Mathematical Programming.
opt-online
S. Burer and D. Vandenbussche.
"Semidefinite-Based Branch-and-Bound for Nonconvex Quadratic Programming",
Mathematical Programming 113 (2), 259-282, 2008.
opt-online
Dion Gijswijt.
"Matrix Algebras and Semidefinite Programming Techniques for Codes",
PhD Thesis, University of Amsterdam, 2005.
arXiv
M. F. Anjos.
"An Explicit Semidefinite Characterization of Satisfiability for Tseitin Instances",
Working paper 2005-02, Department of Management Sciences, University of Waterloo, Canada.
opt-online
R. Shioda and L. Tuncel.
"Clustering via Minimum Volume Ellipsoids",
Research Report CORR 2005--12, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, May 2005.
opt-online
I. Dukanovic and F. Rendl.
"A semidefinite programming based heuristic for graph coloring",
Working paper. Universität Klagenfurt, Institut für Mathematik, Austria, April 2005.
opt-online
Javier Pena, J. Vera and L. Zuluaga.
"Computing the stability number of a graph via linear and semidefinite programming ",
Working Paper, Tepper School of Business, Carnegie Mellon, April 2005.
opt-online
Jiming Peng and Yu Wei.
"Approximating K-means-type clustering via semidefinite programming",
Technical Report, Advanced Optimization Lab, McMaster University, April 2005.
opt-online
E. De Klerk, D. V. Pasechnik and A. Schrijver.
"Reduction of symmetric semidefinite programs using the regular *-representation",
Preprint, CWI, Amsterdam, February 2005.
opt-online
M. F. Anjos, A. Kennings and A. Vannelli.
"A Semidefinite Optimization Approach for the Single-Row Layout Problem with Unequal Dimensions",
University of Waterloo, Ontario Canada, April 2004, revised March 2005. To appear in Discrete Optimization (Accepted March 2005).
opt-online
A. Suzuka.
"Semidefinite Programming Based Approaches to Home-away Assignment Problems in Sports Scheduling",
METR2005-07, Department of Mathematical Engineering and Information Physics, Faculty of Engineering, The University of Tokyo, 2005.
opt-online
I. Djukanovic and F. Rendl.
"Semidefinite programming relaxations for graph coloring and maximal clique problems",
Universität Klagenfurt, Institut für Mathematik, Universitätsstr. 65-67, 9020 Klagenfurt, Austria, March 2004.
opt-online
M. Laurent.
"Strengthened Semidefinite Bounds for Codes",
Preprint, CWI, Amsterdam, January 2005.
opt-online
S. Zhang and Y. Huang.
"Complex Quadratic Optimization and Semidefinite Programming",
Technical Report SEEM2004-3, Department of Systems Engineering & Engineering Management, The Chinese University of Hong Kong, August 2004.
opt-online
W.J. van Hoeve.
"Exploiting Semidefinite Relaxations in Constraint Programming",
Computers and Operations Research, 2004.
arxiv entry,
K. Krishnan and J. Mitchell.
"Semidefinite cut and price approaches for the maxcut problem",
AdvOL-Report No. 2004/3, Department of Computing & Software, McMaster University, Hamilton, Canada. May 2004, revised March 2005.
Also appears as Technical Report, Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York.
opt-online
K. Krishnan and T. Terlaky.
"Interior Point and Semidefinite Approaches in Combinatorial Optimization",
AdvOL-Report No. 2004/2, Dept. of Computing & Software, McMaster University, Hamilton, Canada, January 2004, revised April 2004.
To appear in the GERAD 25th anniversary volume on Graph Theory and Combinatorial Optimization, edited by D. Avis, A. Hertz, and O. Marcotte, Kluwer Academic Publishers, 2005.
opt-online
E. A. Yildirim and X. Fan.
"On Extracting Stable Sets from Lovasz's Theta Function",
Technical Report, Department of Applied Mathematics and Statistics, Stony Brook University, 2003.
opt-online
I. Fischer, G. Gruber, F. Rendl and R. Sotirov.
"The Bundle Method in Combinatorial Optimization",
Research Report, Univ. Klagenfurt, 2003.
opt-online
Franz Rendl and Renata Sotirov.
"Bounds for the Quadratic Assignment Problem Using the Bundle Method",
Report, University of Klagenfurt, Universitaetsstrasse 65-67, Austria, 2003.
opt-online
M. F. Anjos.
"Efficient Semidefinite Programming Relaxations for the Satisfiability Problem",
School of Mathematics, University of Southampton, June 2003, To appear in: Mathematical Methods of Operations Research.
opt-online
K. Anstreicher and S. Burer.
"D.C. Versus Copositive Bounds for Standard QP",
Dept. of Management Sciences, University of Iowa, May 2003.
opt-online
M. Laurent.
"Lower bound for the number of iterations in semidefinite relaxations for the cut polytope",
Preprint, CWI, Amsterdam, The Netherlands, July 2002.
ps-file (http),
M. F. Anjos.
"An Improved Semidefinite Programming Relaxation for the Satisfiability Problem",
Technical Report UW-E&CE#2002-09, Department of Electrical & Computer Engineering, University of Waterloo, Canada, June 2002.
opt-online,
J. B. Lasserre.
"An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs",
To appear in SIAM J. Optim. 12 (2002), pp. 756--769 (SIOPT-reference, preliminary version appeared in 8th IPCO Proc., LNCS 2081, Springer 2001, pp. 251-263.
opt-online,
C. Helmberg.
"A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations",
ZIB-Report 01-26, Konrad-Zuse-Zentrum Berlin, Takustrasse 7, D-14195 Berlin, Germany, October 2001.
abstract, ps and pdf-file
M. Laurent.
"Semidefinite relaxations for Max-Cut",
Preprint, CWI, Amsterdam, The Netherlands, October 2001.
optimization-online,
E. de Klerk and D.V. Pasechnik.
"Approximating the stability number of a graph via copositive programming",
Technical Report, Delft University of Technology, Faculty of Information Technology and Systems, Mekelweg 4, 2628 CD Delft, The Netherlands, 2001.
ps-file (http)
M. X. Goemans and D. P. Williamson.
"Approximation Algorithms for MAX-3-CUT and Other Problems Via Complex Semidefinite Programming",
Proceedings of 33rd STOC, Crete, 443--452, July 2001.
ps-file (http)
M.X. Goemans and F. Rendl.
"Semidefinite Programs and Association Schemes",
Computing, 63, 331--340, 1999.
ps-file (http)
M. Laurent.
"A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0-1 programming",
Report PNA-R0108, CWI, Amsterdam, The Netherlands, June 2001.
ps-file (http), opt-online,
G. Iyengar and M.T. Cezik.
"Cutting Planes for Mixed 0-1 Semidefinite Programs",
8th IPCO Proc., LNCS 2081, Springer 2001, pp. 251-263.
E. Halperin and U. Zwick.
"A Unified Framework for Obtaining Improved Approximation Algorithms for Maximum Graph Bisection Problems",
8th IPCO Proc., LNCS 2081, Springer 2001, pp. 210-225.
E. Halperin, R. Nathaniel, and U. Zwick.
"Coloring k-colorable graphs using smaller palettes"
Proc. of 12th SODA (2001), 319-326.
ps.gz-file (http), ps.gz-file (http, Journal submission)
N. Alon, B. Sudakov and U. Zwick.
"Constructing worst case instances for semidefinite programming based approximation algorithms",
Proc. of 12th SODA (2001), 92-100.
ps.gz-file (http), ps.gz-file (http, Journal submission)
Miguel F. Anjos and Henry Wolkowicz.
"Geometry of Semidefinite Max-Cut Relaxations via Ranks",
Research Report CORR 2001-39, Department of Combinatorics & Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada, June 2001.
opt-online
G. Gruber and F. Rendl.
"Computational experience with Stable Set Relaxations",
Research Report, Department of Mathematics, University of Klagenfurt, Austria, December 2000.
ps.gz-file (http)
M. Laurent.
"Tighter linear and semidefinite relaxations for max-cut based on the Lovász-Schrijver lift-and-project procedure",
Preprint, CWI, The Netherlands, 2000, to appear in SIAM J. Optim.
tex-file (http)
S. Burer, R. Monteiro, and Yin Zhang.
"Rank-Two Relaxation Heuristics for Max-Cut and Other Binary Quadratic Programs",
Technical Report TR00-33 Department of Computational and Applied Mathematics Rice University, Houston, Texas 77005, November 2000.
ps-file (http)
U. Feige and G. Schechtman.
"On the optimality of the random hyperplane rounding technique for MAX CUT",
Manuscript, Department of Computer Science and Applied Mathematics, the Weizmann Institute, Rehovot 76100, Israel, October 31, 2000.
ps-file (http)
E. de Klerk, D.V. Pasechnik, and J.P. Warners.
"On approximate graph colouring and MAX-k-CUT algorithms based on the theta-function"",
Delft University of Technology, Faculty of Information Technology and Systems, October 2000.
ps-file (http)
M. Laurent.
"Polynomial instances of the positive semidefinite and Euclidean distance matrix completion problems",
CWI, P.O. Box 94079, 1090 GB Amsterdam, The Netherlands, July 2000. To appear in SIAM Journal on Matrix Analysis and Applications.
contact monique@cwi.nl
M. Pinar.
"Augmented Lagrange Duality and Lovász' Theta",
Université Libre de Bruxelles, June 2000.
abstract and full text
E. de Klerk and H. van Maaren.
"On semidefinite programming relaxations of 2+p-SAT. ",
Delft University of Technology, Faculty of Information Technology and Systems, April 2000.
ps-file (http)
U. Zwick.
"Analyzing the MAX 2-SAT and MAX DI-CUT approximation algorithms of Feige and Goemans",
Manuscript, Dept. of Computer Science, Tel Aviv Univerusity, March 2000.
ps.gz-file (http)
M. F. Anjos and H. Wolkowicz.
"A Tight Semidefinite Relaxation of the Cut Polytope",
Research Report CORR 2000-19, Department of Combinatorics and Optimization, University of Waterloo, March 2000.
ps.gz-file (http)
Q. Han, Y. Ye, H. Zhang, and J. Zhang.
"On Approximation of Max-Vertex-Cover",
Working Paper, Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, IA 52242, USA, Feburary, 2000.
ps-file (ftp) or dvi-file (ftp)
Q. Han, Y. Ye and J. Zhang.
"Approximation of Dense-$k$-Subgraph",
Working Paper, Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, IA 52242, USA, February, 2000.
ps-file (ftp) or dvi-file (ftp)
Y. Ye and J. Zhang.
".519 Approximation of Dense-n/2-Subgraph",
Working Paper, Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, Iowa 52242, December 1999.
ps-file (ftp) or dvi-file (ftp)
Y. Ye and J. Zhang.
".602 Approximation of the Complement of Min-Bisection",
Working Paper, Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, Iowa 52242, November 1999.
ps-file (ftp) or dvi-file (ftp)
M. Anjos and H. Wolkowicz.
"A Strengthened SDP Relaxation via a Second Lifting for the MAX-CUT Problem",
Technical Report CORR-55, University of Waterloo, Department of Combinatorics and Optimization, Waterloo, Ontario N2L 3G1, Canada, October 1999.
ps.gz-file (http)
C.C. Choi and Y. Ye.
"Application of Semidefinite Programming to Circuit Partitioning",
Department of Management Sciences, The University of Iowa,Iowa City, Iowa 52242, October 1999.
ps-file (ftp) or dvi-file (ftp)
M. Kojima and L. Tuncel.
"On the Finite Convergence of Successive SDP Relaxation Methods",
Research Report B-354, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Meguro, Tokyo 152-8552, Japan, August 1999.
ps.Z-file (http) or ps-file (http)
E. Halperin and U. Zwick.
"Approximation algorithms for MAX 4-SAT and rounding procedures for semidefinite programs",
Proc. of 7th IPCO (1999), 202-217. ps.gz-file (http) ps.gz-file (http, Journal submission)
C. Lemarechal and F. Oustry.
"Semidefinite relaxations and Lagrangian duality with application to combinatorial optimization",
RR-3710, INRIA Rhone-Alpes, ZIRST - 655 avenue de l'Europe, F-38330 Montbonnot Saint-Martin, June 1999.
ps.gz-file (ftp)
J. E. Mitchell.
"Restarting after branching in the SDP approach to MAX-CUT and similar combinatorial optimization problems",
Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, June 1999.
ps-file (http)
K. M. Anstreicher and N. W. Brixius.
"A New Bound for the Quadratic Assignment Problem Based on Convex Quadratic Programming",
Dept. of Management Sciences, University of Iowa, May 1999.
ps-file (http)
E. de Klerk, H. van Maaren, and J.P. Warners.
"Relaxations of the Satisfiability Problem using Semidefinite programming",
CWI report SEN-R9903, CWI, Amsterdam, The Netherlands, April 1999.
ps-file (http)
Y. Ye.
"A .699-Approximation Algorithm for Max-Bisection",
Working Note, Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, Iowa 52242, March 1999.
ps-file (ftp) or dvi-file (ftp)
A. Takeda, Y. Dai, M. Fukuda, and M. Kojima.
"Towards the Implementation of Successive Convex Relaxation Method for Nonconvex Quadratic Optimization Problems",
Research Reports on Information Sciences, No. B-347, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, March 1999.
ps.gz-file (ftp)
K. Anstreicher.
"Eigenvalue bounds versus semidefinite relaxations for the quadratic assignment problem",
SIAM J. Optim., Vol. 11, Nr. 1, pp 254 265, presumably 2000.
ps-file (http)
S. Burer and R.D.C. Monteiro.
"A projected gradient algorithm for solving the {M}axcut {SDP} relaxation",
Optimization Methods and Software 15, 175--200,2001.
pdf-file (http)
D. Cvetkovic, M. Cangalovic, and V. Kovacevic-Vujcic.
"Semidefinite relaxations of traveling salesman problem",
Technical Report 902-98, Laboratory for Operations Research, Faculty of Organizational Sciences, University of Belgrade, November 1998.
Contact verakov@fon.fon.bg.ac.yu
Uri Zwick.
"Approximation algorithms for constraint satisfaction problems involving at most three variables per constraint",
Proc. of 9th SODA (2998), 201-210.
ps.gz-file (http)
M. Skutella.
"Semidefinite Relaxations for Parallel Machine Scheduling",
Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS'98), pp. 472-481, 1998.
ps-file (http)
M. Goemans.
"Semidefinite Programming and Combinatorial Optimization",
Documenta Mathematica, Extra Volume ICM 1998, III, 657-666.
ps.gz-file (http), dvi.gz-file (http), and abstract (html)
Masakazu Kojima and Levent Tuncel.
"Discretization and Localization in Successive Convex Relaxation Methods for Nonconvex Quadratic Optimization Problems",
Research Report B-341, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, July 1998.
ps.Z-file (ftp) or dvi.Z-file (ftp)
Kurt Anstreicher, Xin Chen, Henry Wolkowicz, and Ya-Xiang Yuan.
"Strong Duality for a Trust-Region Type Relaxation of the Quadratic Assignment Problem",
ps.gz-file (http)
K. M. Anstreicher and H. Wolkowicz.
"On Lagrangian Relaxation of Quadratic Matrix Constraints",
Research Report CORR 98-24, Department of Combinatorics and Optimization, University of Waterloo, May 1998.
ps.gz-file (http)
K. M. Anstreicher.
"On the Equivalence of Convex Programming Bounds for Boolean Quadratic Programming",
Dept. of Managment Science, University of Iowa, May 1998.
ps-file (ftp)
M. Laurent.
"On the order of a graph and its deficiency in chordality",
Report PNA-R9801, CWI, Amsterdam, February 1998.
ps.Z-file (ftp), and abstract (html)
S. Benson, Y. Ye, and X. Zhang.
"Mixed Linear and Semidefinite Programming for Combinatorial and Quadratic Optimization",
Optimization Methods and Software 11&12 (1999) 515-544.
ps-file (ftp)
H. Karloff and U. Zwick.
"A 7/8-Approximation Algorithm for MAX 3SAT?",
Proc. of 38th FOCS (1997), 406--415.
ps.gz-file (http)
C.-J. Lin and R. Saigal.
"On Solving Large-Scale Semidefinite Programming Problems -- A Case Study of Quadratic Assignment Problem",
Department of Industrial and Operations Engineering, University of Michigan, December 1997.
ps-file (http)
T. Stephen and L. Tuncel.
"On a representation of the matching polytope via semidefinite liftings",
Research Report 97-11, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, July 1997.
ps-file (http)
A.J. Quist, E. de Klerk, C. Roos, and T. Terlaky.
"Copositive Relaxation for General Quadratic Programming",
Optimization Group TU Delft, Faculty of Information Technology and Systems, Delft University of Technology, September 1997. To appear in Optimization Methods and Software.
ps-file (http)
S. Benson, Y. Ye, and X. Zhang. (Also listed in Interior Point Algorithms)
"Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization",
Working Paper, Department of Management Science, University of Iowa, IA, 52242, USA, September 1997.
ps-file (ftp) or dvi-file (ftp)
Y. Ye.
"Approximating quadratic optimization with linear and boolean constraints",
Working Paper, Department of Management Sciences, The University of Iowa, IA, USA, August, 1997.
(not available any more)
S. E. Karisch, F. Rendl, and J. Clausen.
"Solving graph bisection problems with semidefinite programming",
Technical Report DIKU-TR-97/9, Department of Computer Science, University of Copenhagen, July 1997.
ps.gz-file (http)
Yu. Nesterov.
"Semidefinite Relaxation and nonconvex quadratic optimization",
CORE Discussion Paper, May 1997, revised August 1997, to appear in Optimization Methods and Software.
Y. Ye.
"Approximating quadratic programming with quadratic constraints",
Math. Programming, 84:219-226(1999).
ps-file (ftp) or dvi-file (ftp)
Y. Ye.
"Approximating quadratic programming with bound constraints",
Working Paper, Department of Management Science, The University of Iowa, March 1997.
ps-file (ftp) or dvi-file (ftp)
Yu. Nesterov.
"Quality of semidefinite relaxation for nonconvex quadratic optimization",
CORE Discussion Paper 9719, March 1997.
M. X. Goemans.
"Semidefinite programming in combinatorial optimization",
Mathematical Programming 79 (1997) 143-161.
F. Rendl.
"Max-Cut Approximations in graphs with triangles",
Technical Report, Department of Mathematics, Graz University of Technology, February 1997.
C. Helmberg.
"Fixing Variables in Semidefinite Relaxations",
SIAM J. Matrix Anal. Appl. Vol. 21, No. 3, pp. 952-969.
ps.Z-file (ftp)
H. Wolkowicz and Q. Zhao.
"Semidefinite Programming Relaxations for the Graph Partitioning Problem",
Discrete Applied Mathematics 96-97 (1999) 461--479.
ps.gz-file (ftp)
Q. Zhao, S. E. Karisch, F. Rendl, and H. Wolkowicz.
"Semidefinite programming relaxations for the quadratic assignment poblem",
CORR Report 95/27, University of Waterloo, September, 1996.
ps.gz-file (ftp)
H. Chen and A. Frieze.
"Coloring Bipartite Hypergraphs",
IPCO V Proc., LNCS 1084, Springer 1996, pp. 345-358.
C. Helmberg, F. Rendl, and R. Weismantel.
"A Semidefinite Programming Approach to the Quadratic Knapsack Problem",
J. of Combinatorial Optimization 4 (2000) 197-215.
ps.Z-file (ftp), abstract.
(IPCO V version: LNCS 1084, Springer 1996, pp. 175-189)
P. Klein and Hsueh-I Lu.
"Efficient Approximation Algorithms for Semidefinite Programs Arising from MAXCUT and COLORING",
STOC'96, pp. 338-347.
ps-file (http)
H. Karloff.
"How good ist the Goemans-Williamson MAX-CUT algorithm?",
Stoc'96, pp. 427-434.
N. Alon and N. Kahale.
"Approximating the independence number via the theta-function",
Mathematical Programming 80 (1998) 253-264.
ps-file (http)
S. Karisch and F. Rendl.
"Semidefinite Programming and Graph Equipartition",
December 1995.
ps-file (http)
C. Helmberg and F. Rendl.
"Solving Quadratic (0,1)-Problems by Semidefinite Programs and Cutting Planes",
Mathetmatical Programming 82 (1998) 291-315.
ps.Z-file (ftp), abstract.
J. Kleinberg and M. X. Goemans.
"The Lovasz theta function and a semi-definite programming relaxation of vertex cover",
SIAM J. Discrete Math, 11, 196-204, 1998.
ps-file (http)
U. Feige and M. X. Goemans.
"Approximating the value of two prover proof systems, with applications to MAX 2SAT and MAX DICUT",
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, Tel Aviv, Israel, 182--189, 1995.
ps-file (ftp)
B. Chor and M. Sudan.
"A Geometric Approach to Betweenness",
SIAM Jour. Disc. Math. , Vol. 11, No. 4, October 1998, pp. 511 - 523.

preliminary version in ESA '95 Proc., LNCS 979, Springer 1995, pp. 227-237.
ps.gz-file (http)
A. Frieze and M. Jerrum.
"Improved approximation algorithms for MAX k-CUT and MAX BISECTION",
IPCO IV Proc., LNCS 920, Springer 1995, pp. 1-13.
ps.Z-file (http)
S. Mahajan and H. Ramesh.
"Derandomizing Semidefinite Programming Based Approximation Algorithms",
FOCS 95, pp. 162-169.
C. Helmberg, S. Poljak, F. Rendl, and H. Wolkowicz.
"Combining Semidefinite and Polyhedral Relaxations for Integer Programs",
IPCO IV Proc., LNCS 920, Springer 1995, pp. 124-134.
ps-file (http)
M. Laurent, S. Poljak, and F. Rendl.
"Connections between semidefinite relaxations of the max-cut and stable set Problems",
Mathematical Programming 77 (1997) 225-246.
ps.Z-file (http)
M. Laurent and S. Poljak.
"On the facial structure of the set of correlation matrices",
SIAM J. Matrix Anal. Appl., 17:530-547, 1996.
ps.Z-file (http)
D. Karger, R. Motwani, and M. Sudan.
"Approximate Graph Coloring by Semidefinite Programming",
FOCS 94, pp. 2-13.
ps.Z-file (ftp)
S. Poljak, F. Rendl, and H. Wolkowicz.
"A Recipe for Best Semidefinite Relaxation for (0,1)-Quadratic Programming",
CORR Report 94/7, University of Waterloo, October 1994.
dvi.gz-file (ftp)
M. X. Goemans and D. P. Williamson.
"Improved Approxiamtion Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming",
J. ACM, 42, pp. 1115-1145, 1995.
ps-file (ftp)
M. Szegedy.
"A note on the theta number of Lovasz and the generalized Delsarte bound",
FOCS 94, pp. 36-39.
N. Alon.
"Explicit Ramsey graphs and orthonormal labelings",
The Electronic Journal of Combinatorics 1 (1994), R12, 8pp.
html-reference or ps-file (http)
D. E. Knuth.
"The Sandwich Theorem",
The Electronic Journal of Combinatorics 1 (1994), #A1.
html-reference
S. Poljak and H. Wolkowicz.
"Convex Relaxations of (0,1)-Quadratic Porgramming",
Mathematics of Operations Research, Vol. 20, No. 3, pp. 550-561, August 1995.
F. Alizadeh. (also listed in Interior Point Algorithms)
"Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization",
SIAM J. Optim., Vol. 5, No. 1, pp. 13--51, 1995.
ps-file (http)
M. Laurent and S. Poljak.
"On a positive Semidefinite Relaxation of the Cut Polytope",
Linear Algebra and its Applications, 223/224:439-461, 1995.
S. Poljak, and F. Rendl.
"Nonpolyhedral Relaxations of Graph-Bisection Problems",
SIAM J. Optim., Vol. 5, No. 3, pp. 467--487, 1995.
S. Poljak, and F. Rendl.
"Solving the max-cut problem using eigenvalues",
Discrete Appl. Math. 62(1995) 249--278.
C. Delorme and S. Poljak.
"ombinatorial Properties and the complexity of a max-cut Approximation",
Report 91687-OR, LRI University Paris-Sud, F-91405 ORSAY Cedex, France, 1991.
C. Delorme and S. Poljak.
"Laplacian eigenvalues and the maximum cut problem",
Mathematical Programming 62, 557-547, 1993.
L. Lovasz and A. Schrijver.
"Cones of Matrices and Set-Functions and 0-1 Optimization",
SIAM J. Optimization, Vol. 1, No. 2, pp. 166-190, May 1991.
M. Grötschel, L. Lovasz, and A. Schrijver.
"Geometric Algorithms and Combinatorial Optimization",
Springer-Verlag, 1988.
N. Z. Shor.
"Quadratic Optimization Problems",
Soviet Journal of Computer and Systems Sciences 25, 1-11, 1987.
M. Grötschel, L. Lovasz, and A. Schrijver.
"Polynomial algorithms for perfect graphs",
Annals of Discrete Mathematics 21 (1984) 325-356.
L. Lovasz.
"On the Shannon Capacity of a Graph",
IEEE Transactions on Information Theory, Vol. IT-25, No. 1, January 1979.
W. E. Donath and A. J. Hoffman.
"Lower bounds for the partitioning of graphs",
IBM Journal of Research and Development, 17:420-425, 1973.

Last modified: Fri Sep 9 15:31:55 CEST 2011