**Fields Institute Monographs**

Volume: 27;
2010;
219 pp;
Hardcover

MSC: Primary 90; 15; 52; 65; 05; 68;

Print ISBN: 978-0-8218-3352-0

Product Code: FIM/27

List Price: $81.00

Individual Member Price: $64.80

**Electronic ISBN: 978-1-4704-1790-1
Product Code: FIM/27.E**

List Price: $81.00

Individual Member Price: $64.80

#### You may also like

#### Supplemental Materials

# Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization

Share this page
*Levent Tunçel*

A co-publication of the AMS and Fields Institute

Since the early 1960s, polyhedral methods have
played a central role in both the theory and practice of combinatorial
optimization. Since the early 1990s, a new technique, semidefinite
programming, has been increasingly applied to some combinatorial
optimization problems. The semidefinite programming problem is the
problem of optimizing a linear function of matrix variables, subject
to finitely many linear inequalities and the positive semidefiniteness
condition on some of the matrix variables. On certain problems, such
as maximum cut, maximum satisfiability, maximum stable set and
geometric representations of graphs, semidefinite programming
techniques yield important new results. This monograph provides the
necessary background to work with semidefinite optimization
techniques, usually by drawing parallels to the development of
polyhedral techniques and with a special focus on combinatorial
optimization, graph theory and lift-and-project methods. It allows the
reader to rigorously develop the necessary knowledge, tools and skills
to work in the area that is at the intersection of combinatorial
optimization and semidefinite optimization.

A solid background in mathematics at the undergraduate level and
some exposure to linear optimization are required. Some familiarity
with computational complexity theory and the analysis of algorithms
would be helpful. Readers with these prerequisites will appreciate the
important open problems and exciting new directions as well as new
connections to other areas in mathematical sciences that the book
provides.

Titles in this series are co-published with The Fields Institute for Research in Mathematical Sciences (Toronto, Ontario, Canada).

#### Table of Contents

# Table of Contents

## Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization

- Cover Cover11
- Title page 44
- Contents 66
- Preface 1010
- Introduction 1212
- Duality theory 3838
- Ellipsoid method 6464
- Primal-dual interior-point methods 7474
- Approximation algorithms based on SDP 9494
- Geometric representations of graphs 116116
- Lift-and-project procedures for combinatorial optimization problems 140140
- Lift-and-project ranks for combinatorial optimzation 154154
- Successive convex relaxation methods 176176
- Connections to other areas of mathematics 188188
- An application to discrepancy theory 194194
- SDP representability 200200
- Bibliography 214214
- Index 228228
- Back Cover Back Cover1233

#### Readership

Graduate students and research mathematicians interested in semidefinite programming, combinatorial optimization, lift-and-project methods, convex relaxation methods.