## Novel Approaches to Hard Discrete OptimizationDuring the last decade, many novel approaches have been considered for dealing with computationally difficult discrete optimization problems. Such approaches include interior point methods, semidefinite programming techniques, and global optimization. More efficient computational algorithms have been developed and larger problem instances of hard discrete problems have been solved. This progress is due in part to these novel approaches, but also to new computing facilities and massive parallelism. This volume contains the papers presented at the workshop on ''Novel Approaches to Hard Discrete Optimization''. The articles cover a spectrum of issues regarding computationally hard discrete problems. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Modeling and Optimi2ation in Massive Graphs | 17 |

A Tale on Guillotine Cut | 41 |

Wavelength Assigmnent Algorithms in Multifiber Networks | 55 |

Indivisibility and Divisibility Polytopes | 71 |

The Dual Active Set Algorithm and the Iterative Solution | 97 |

Positive Eigenvalues of Generali2ed Words | 111 |

SDP Versus LP Relaxations for Polynomial Programming | 143 |

A Convex Feasibility Problem Defined by a Nonlinear Separation Oracle | 165 |

### Common terms and phrases

approximation algorithms Arora clippable clipped cube clipping inequalities clique coefficient columns Computer Science consider constraints convergence convex CPLEX defined denote edge eigenvalue Euclidean external memory algorithms extreme points facet feasible solution finite g-poly g-word giant connected component guillotine cut Hence heuristic integer Internet Lemma linear programming lower bound LP relaxation m-guillotine massive graphs Mathematics Mathematics Subject Classification matrix max cut minimi2ation networks nodes nonzero number of fibers number of wavelengths objective function objective value obtain optimal solution optimi2ation problems permutation polynomial polynomial-time approximation scheme polytopes portal power-law primal Proof Proposition Quadratic Assignment Problem random graphs rate of connections rectangular partition rectilinear Steiner RSMT satisfies SDP relaxations Section segments semi-infinite Semidefinite Programming sequence SIAM simple bound inequalities solve spectral bundle Steiner forest Steiner minimum tree subset symmetric Theorem 2.1 uniform random graphs variables vector Web graph