Novel Approaches to Hard Discrete OptimizationPanos M. Pardalos, Henry Wolkowicz American Mathematical Soc. - 181 lappuses 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. |
Saturs
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 |
Bieži izmantoti vārdi un frāzes
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
Populāri fragmenti
15. lappuse - As far as the laws of mathematics refer to reality, they are not certain; and as far as they are certain, they do not refer to reality.
36. lappuse - S. Brin and L. Page. The anatomy of a large scale hypertextual web search engine, in: Proc.
23. lappuse - Each octant is represented by a vertex, and two vertices are connected by an edge if any trajectory initiated at one vertex goes to the other.
78. lappuse - A 0, 1 matrix is balanced if it does not contain a square submatrix of odd order with two ones per row and column.
65. lappuse - The nodes are distributed randomly over a rectangular coordinate grid. Each node is placed at a location with integer coordinates.
41. lappuse - Department of Computer Science and Engineering University of Minnesota Minneapolis, MN 55455 USA {jin, tchen, hsu, yew}@cs.
39. lappuse - JS Vitter. External memory algorithms and data structures: Dealing with massive data.
57. lappuse - G = (V,E,C,X), where V is the set of nodes, E is the set of...
48. lappuse - Mitchell [29] extended the 1-guillotine cut to the m-guillotine cut in the following way: A point p is a horizontal (vertical) m-dark point if the horizontal (vertical) line passing through p intersects at least 2m vertical (horizontal) segments of the considered rectangular partition P, among which at least m are on the left of p (above p) and at least m are on the right of p (below p). Let Hm (Vm) denote the set of all horizontal (vertical) m-dark points. An m-guillotine cut is either a horizontal...