The ellipsoid method and its consequences in combinatorial optimization

DOI10.1007/BF02579273zbMath0492.90056DBLPjournals/combinatorica/GrotschelLS81WikidataQ55882924 ScholiaQ55882924MaRDI QIDQ1168215

Martin Grötschel

Publication date: 1981

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Integer programming (90C10) Linear programming (90C05) Boolean programming (90C09)

Related Items (only showing first 100 items - show all)

Cardinality constraints and systems of restricted representatives ⋮ Vertex cover meets scheduling ⋮ Tractability in constraint satisfaction problems: a survey ⋮ Solving the minimum convex partition of point sets with integer programming ⋮ Mixed integer formulations using natural variables for single machine scheduling around a common due date ⋮ Realizing symmetric set functions as hypergraph cut capacity ⋮ A polyhedral view to a generalization of multiple domination ⋮ An approximation algorithm for clustering graphs with dominating diametral path ⋮ Routing of uncertain traffic demands ⋮ Strip packing with precedence constraints and strip packing with release times ⋮ Weighted independent sets in classes of \(P_6\)-free graphs ⋮ NP-hardness of the recognition of coordinated graphs ⋮ Assignment problems with complementarities ⋮ On total variation minimization and surface evolution using parametric maximum flows ⋮ Stronger multi-commodity flow formulations of the capacitated vehicle routing problem ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ Even pairs in square-free Berge graphs ⋮ Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope ⋮ Tent and a subclass of \(P_{5}\)-free graphs ⋮ Multicuts and perturb \& MAP for probabilistic graph clustering ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ The max-cut problem on graphs not contractible to \(K_ 5\) ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Characterization of feedback Nash equilibria for multi-channel systems via a set of non-fragile stabilizing state-feedback solutions and dissipativity inequalities ⋮ A characterization of Delsarte's linear programming bound as a ratio bound ⋮ A lower bound for intuitionistic logic ⋮ Computing clique and chromatic number of circular-perfect graphs in polynomial time ⋮ Approximation algorithms for extensible bin packing ⋮ On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Computational implications of reducing data to sufficient statistics ⋮ The cluster deletion problem for cographs ⋮ The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect ⋮ Bilevel programming and the separation problem ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ On 2-stage robust LP with RHS uncertainty: complexity results and applications ⋮ Packing cycles exactly in polynomial time ⋮ Static and dynamic routing under disjoint dominant extreme demands ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ On claw-free \(t\)-perfect graphs ⋮ On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph ⋮ A constraint sampling approach for multi-stage robust optimization ⋮ Hybrid tractability of valued constraint problems ⋮ Facet identification for the symmetric traveling salesman polytope ⋮ Regular inference as vertex coloring ⋮ Undirected postman problems with zigzagging option: a cutting-plane approach ⋮ The mixing-MIR set with divisible capacities ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ On the complexity of submodular function minimisation on diamonds ⋮ Faster algorithms for security games on matroids ⋮ Distributionally robust multi-item newsvendor problems with multimodal demand distributions ⋮ Partitioning posets ⋮ On routing in VLSI design and communication networks ⋮ Efficient minimization of higher order submodular functions using monotonic Boolean functions ⋮ The stable set polytope of quasi-line graphs ⋮ George Dantzig's contributions to integer programming ⋮ The Grothendieck constant of random and pseudo-random graphs ⋮ Semidefinite approximations of conical hulls of measured sets ⋮ Using conical regularization in calculating Lagrangian estimates in quadratic optimization problems ⋮ On the complexity of bandwidth allocation in radio networks ⋮ Strict chordal and strict split digraphs ⋮ Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs ⋮ A comparison of two edge-coloring formulations ⋮ Optimization with uniform size queries ⋮ 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem ⋮ The expressive power of binary submodular functions ⋮ Pseudo-Boolean optimization ⋮ Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard ⋮ A magnetic procedure for the stability number ⋮ The performance of an upper bound on the fractional chromatic number of weighted graphs ⋮ A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions ⋮ Maximum weight independent sets in hole- and dart-free graphs ⋮ On linear and semidefinite programming relaxations for hypergraph matching ⋮ Duality for balanced submodular flows ⋮ Algebraic optimization: The Fermat-Weber location problem ⋮ Exact localisations of feedback sets ⋮ A note on submodular function minimization with covering type linear constraints ⋮ The indefinite period traveling salesman problem ⋮ Submodular function minimization ⋮ Recognizing vertex intersection graphs of paths on bounded degree trees ⋮ Social exchange networks with distant bargaining ⋮ Stable sets and graphs with no even holes ⋮ Packing trees in communication networks ⋮ Bidimensional packing by bilinear programming ⋮ On the core of network synthesis games ⋮ A polynomial algorithm for minimum quadratic cost flow problems ⋮ Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization ⋮ A new polynomial-time algorithm for linear programming ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ Combinatorial optimization with 2-joins ⋮ Mind the independence gap ⋮ Recent trends in combinatorial optimization ⋮ Finding feasible vectors of Edmonds-Giles polyhedra ⋮ On the integrality of an extreme solution to pluperfect graph and balanced systems ⋮ On some weakly bipartite graphs ⋮ A note on matchings and separability ⋮ Optimizing over the subtour polytope of the travelling salesman problem ⋮ Solution of large-scale symmetric travelling salesman problems ⋮ A comparison of heuristics and relaxations for the capacitated plant location problem

Cites Work

This page was built for publication: The ellipsoid method and its consequences in combinatorial optimization