Fields Institute Communications 1998; 250 pp; hardcover Volume: 18 ISBN10: 0821808257 ISBN13: 9780821808252 List Price: US$84 Member Price: US$67.20 Order Code: FIC/18
 This volume contains refereed papers presented at the workshop on "Semidefinite Programming and InteriorPoint Approaches for Combinatorial Optimization Problems" held at The Fields Institute in May 1996. Semidefinite programming (SDP) is a generalization of linear programming (LP) in that the nonnegativity constraints on the variables are replaced by a positive semidefinite constraint on matrix variables. Many of the elegant theoretical properties and powerful solution techniques follow through from LP to SDP. In particular, the primaldual interiorpoint methods, which are currently so successful for LP, can be used to efficiently solve SDP problems. In addition to the interesting theoretical and algorithmic questions, SDP has found many important applications in combinatorial optimization, control theory and other areas of mathematical programming. SDP is currently a very hot area of research. The papers in this volume cover a wide spectrum of recent developments in SDP. The volume would be suitable as a textbook for advanced courses in optimization. Titles in this series are copublished with the Fields Institute for Research in Mathematical Sciences (Toronto, Ontario, Canada). Readership Graduate students and researchers in mathematics, computer science, engineering and operations. Table of Contents Theory  A. Shapiro  Optimality conditions and sensitivity analysis of coneconstrained and semidefinite programs
 L. Porkolab and L. Khachiyan  Testing the feasibility of semidefinite programs
 M. V. Ramana  Polyhedra, spectrahedra, and semidefinite programming
 L. Faybusovich  Infinitedimensional semidefinite programming: Regularized determinants and selfconcordant barriers
Applications  M. Laurent  A tour d'horizon on positive semidefinite and Euclidean distance matrix completion problems
 S. E. Karisch and F. Rendl  Semidefinite programming and graph equipartition
 C. R. Johnson, B. K. Kroschel, and M. Lundquist  The totally nonnegative completion problem
 J. Gu  The multiSAT algorithm
 M. R. EmamyK.  How efficiently can we maximize threshold pseudoBoolean functions?
 G. Xue, D.Z. Du, and F. K. Hwang  Faster algorithm for shortest network under given topology
 A. Mockus, J. Mockus, and L. Mockus  Bayesian heuristic approach (BHA) and applications to discrete optimization
 B. Mirkin  Approximation clustering: A mine of semidefinite programming problems
Algorithms  K. M. Anstreicher and M. Fampa  A longstep path following algorithm for semidefinite programming problems
 C. Helmberg and R. Weismantel  Cutting plane algorithms for semidefinite relaxations
 E. De Klerk, C. Roos, and T. Terlaky  Infeasiblestart semidefinite programming algorithms via selfdual embeddings
 S. Lucidi and L. Palagi  Solution of the trust region problem via a smooth unconstrained reformulation
