The ellipsoid method and its consequences in combinatorial optimization
From MaRDI portal
Publication:1168215
DOI10.1007/BF02579273zbMath0492.90056MaRDI QIDQ1168215
Alexander Schrijver, László Lovász, Martin Grötschel
Publication date: 1981
Published in: Combinatorica (Search for Journal in Brave)
matching; fractional chromatic number; polynomial complexity; polynomial algorithms; NP hardness; submodular set function; Khachiyan's algorithm; matroid intersection problems; optimum covering of directed cuts of a digraph; vertex packing in perfect graphs
68Q25: Analysis of algorithms and problem complexity
65K05: Numerical mathematical programming methods
90C10: Integer programming
90C05: Linear programming
90C09: Boolean programming
Related Items
Polyhedral techniques in combinatorial optimization I: Theory, Precoloring Extension III: Classes of Perfect Graphs, A comparison of two edge-coloring formulations, The complexity of controlled selection, The principal lattice of partitions of a submodular function, Two algorithms for maximizing a separable concave function over a polymatroid feasible region, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, \(b\)-matching degree-sequence polyhedra, COSINE: A new graph coloring algorithm, A polyhedral approach to edge coloring, \(T\)-colorings of graphs: recent results and open problems, A dual algorithm for submodular flow problems, The traveling salesman problem in graphs with some excluded minors, Stability number and chromatic number of tolerance graphs, Expressing combinatorial optimization problems by linear programs, Solving combinatorial optimization problems using Karmarkar's algorithm, Paths on polymatroids, A cutting plane algorithm for the windy postman problem, Compositions in the bipartite subgraph polytope, The complexity of lifted inequalities for the knapsack problem, Applications of combinatorics to statics --- a second survey, A hierarchical algorithm for making sparse matrices sparser, Optimal multiple interval assignments in frequency assignment and traffic phasing, Hard promise problems and nonuniform complexity, The optimal path-matching problem, A note on formulations for the \(A\)-partition problem on hypergraphs, The complexity of some problems related to GRAPH 3-COLORABILITY, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers, Boolean polynomials and set functions, A deep cut ellipsoid algorithm for convex programming: Theory and applications, The ellipsoid algorithm using parallel cuts, The maximum clique problem, Near-perfect matrices, A separation algorithm for the matchable set polytope, Comparison of formulations and a heuristic for packing Steiner trees in a graph, Lattice-free polytopes and their diameter, Minimum dispersion problems, Semidefinite programming in combinatorial optimization, Cuts, matrix completions and graph rigidity, Approximating the independence number via the \(\vartheta\)-function, On approximately fair cost allocation in Euclidean TSP games, Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, Recent results on approximating the Steiner tree problem and its generalizations, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, A polyhedral approach to sequence alignment problems, Transfer flow graphs, Structure of a simple scheduling polyhedron, A computational study of several heuristics for the DRPP, The gap between monotone and non-monotone circuit complexity is exponential, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, A rounding technique for the polymatroid membership problem, On the integral dicycle packings and covers and the linear ordering polytope, Recognizing bull-free perfect graphs, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, Minimizing submodular functions over families of sets, Extended formulations for the \(A\)-cut problem, Strongly polynomial simplex algorithm for bipartite vertex packing, Restrictions and preassignments in preemptive open shop scheduling, \(\varepsilon\)-approximation minimization of convex functions in fixed dimension, Long range planning in the process industries: A projection approach, Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs, Orthogonal representations over finite fields and the chromatic number of graphs, A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
