Novel Approaches to Hard Discrete OptimizationPanos M. Pardalos, Henry Wolkowicz American Mathematical Soc. - 181 sivua During 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. |
Sisältö
Modeling and Optimization in Massive Graphs | 17 |
A Tale on Guillotine Cut | 41 |
Wavelength Assignment Algorithms in Multifiber Networks | 55 |
Indivisibility and Divisibility Polytopes | 71 |
The Dual Active Set Algorithm and the Iterative Solution | 97 |
Positive Eigenvalues of Generalized Words | 111 |
SDP Versus LP Relaxations for Polynomial Programming | 143 |
A Convex Feasibility Problem Defined by a Nonlinear Separation Oracle | 165 |
Yleiset termit ja lausekkeet
approximation algorithms clippable clipped cube clipping inequalities clique coefficient combinatorial optimization Computer Science consider constraints convergence convex CPLEX DASA denote edge eigenvalue external memory algorithms extreme points finite g-word giant connected component guillotine cut Hence heuristic indivisibility polytopes integer Internet Lemma linear programming lower bound LP-relaxations m-guillotine massive graphs Mathematics Mathematics Subject Classification matrix max cut minimizer networks nodes nonzero number of fibers number of wavelengths objective function objective value obtain optimal solution optimization 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 S₁ satisfies SDP relaxations Section segments semi-infinite Semidefinite Programming sequence SIAM simple bound inequalities solve spectral bundle Steiner minimum tree subset success rate symmetric Theorem 2.1 uniform random graphs variables vector