The ellipsoid method and its consequences in combinatorial optimization

DOI10.1007/BF02579273zbMATH Open0492.90056DBLPjournals/combinatorica/GrotschelLS81WikidataQ55882924 ScholiaQ55882924MaRDI QIDQ1168215FDOQ1168215

Alexander Schrijver, Martin Grötschel, László Lovász

Publication date: 1981

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

matchingpolynomial complexitypolynomial algorithmsfractional chromatic numberNP hardnesssubmodular set functionKhachiyan's algorithmmatroid intersection problemsoptimum covering of directed cuts of a digraphvertex packing in perfect graphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Maximal Flow Through a Network
• A note on two problems in connexion with graphs
• Normal hypergraphs and the perfect graph conjecture
• Khachiyan’s algorithm for linear programming
• On the Shannon capacity of a graph
• Matching, Euler tours and the Chinese postman
• The NP-Completeness of Edge-Coloring
• Maximum matching and a polyhedron with 0,1-vertices
• Optimum branchings
• The Relaxation Method for Linear Inequalities
• On maximal independent sets of vertices in claw-free graphs
• A Minimax Theorem for Directed Graphs
• The matroids with the max-flow min-cut property
• Multi-Commodity Network Flows
• Odd Minimum Cut-Sets and b-Matchings
• Matroid Intersection
• On the orientation of graphs
• 2-Matchings and 2-covers of hypergraphs
• How to make a digraph strongly connected
• Multicommodity flows in planar graphs
• Packing rooted directed cuts in a weighted directed graph
• A two-commodity cut theorem
• Two-commodity cut-packing problem
• Convergence rate of the gradient descent method with dilatation of the space

Cited In (only showing first 100 items - show all)

• 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
• A polyhedral view to a generalization of multiple domination
• The complexity of lifted inequalities for the knapsack problem
• Valid inequalities for quadratic optimisation with domain constraints
• Are stable instances easy?
• Application of the ellipsoid method in an interactive procedure for multicriteria linear programming
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• NP-hardness of the recognition of coordinated graphs
• The Schrijver system of odd join polyhedra
• A new branch-and-bound algorithm for the maximum edge-weighted clique problem
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• \(b\)-matching degree-sequence polyhedra
• The principal lattice of partitions of a submodular function
• A note on submodular function minimization with covering type linear constraints
• The indefinite period traveling salesman problem
• Role of redundant constraints for improving dual bounds in polynomial optimization problems
• On the equivalence between some discrete and continuous optimization problems
• On \(f\)-domination: polyhedral and algorithmic results
• Approximate Deadline-Scheduling with Precedence Constraints
• The operator approach to entropy games
• Inductive graph invariants and approximation algorithms
• Computational implications of reducing data to sufficient statistics
• Social exchange networks with distant bargaining
• Stable sets and graphs with no even holes
• On the integral dicycle packings and covers and the linear ordering polytope
• Classes of perfect graphs
• On circular-perfect graphs: a survey
• Stability number and chromatic number of tolerance graphs
• On stability of collaborative supplier selection
• A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts
• The strong perfect graph conjecture: 40 years of attempts, and its resolution
• Mind the independence gap
• On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph
• Coloring planar perfect graphs by decomposition
• How to recycle your facets
• Undirected postman problems with zigzagging option: a cutting-plane approach
• On the integrality of an extreme solution to pluperfect graph and balanced systems
• Title not available (Why is that?)
• Bicliques and eigenvalues
• Reference points and approximation algorithms in multicriteria discrete optimization
• A note on matchings and separability
• Intelligent gradient search in linear programming
• A cutting plane algorithm for the windy postman problem
• Approximating Minimum Cost Connectivity Orientation and Augmentation
• Partitioning posets
• On routing in VLSI design and communication networks
• The Grothendieck constant of random and pseudo-random graphs
• Packing trees in communication networks
• A note on submodular set cover on matroids
• Cross line and column generation for the cut covering problem in wireless networks
• Strong formulations for mixed integer programming: A survey
• On the cut polytope
• Cardinality constraints and systems of restricted representatives
• Characterization of feedback Nash equilibria for multi-channel systems via a set of non-fragile stabilizing state-feedback solutions and dissipativity inequalities
• The maximum clique problem
• Metrics and undirected cuts
• Grothendieck’s Theorem, past and present
• Graph isomorphism and theorems of Birkhoff type
• Envy-free pricing in multi-item markets
• Vertex cover meets scheduling
• Tractability in constraint satisfaction problems: a survey
• A characterization of Delsarte's linear programming bound as a ratio bound
• Pseudo-Boolean optimization
• THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND
• The omnipresence of Lagrange
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• The History of the LLL-Algorithm
• Realizing symmetric set functions as hypergraph cut capacity
• Hybrid tractability of valued constraint problems
• George Dantzig's contributions to integer programming
• A 71/60 theorem for bin packing
• Quadratic forms on graphs
• On the core of network synthesis games
• Expressing combinatorial optimization problems by linear programs
• An approximation algorithm for clustering graphs with dominating diametral path
• A deep cut ellipsoid algorithm for convex programming: Theory and applications
• On approximately fair cost allocation in Euclidean TSP games
• Weighted independent sets in classes of \(P_6\)-free graphs
• The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds
• Maximum weight independent sets in classes related to claw-free graphs
• \(T\)-colorings of graphs: recent results and open problems
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• The expressive power of binary submodular functions
• Assignment problems with complementarities
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Optimal multiple interval assignments in frequency assignment and traffic phasing
• Maximum weight independent sets in hole- and dart-free graphs
• Routing of uncertain traffic demands
• 3-colouring AT-free graphs in polynomial time
• Lower bounds and algorithms for the 2-dimensional vector packing problem
• Finding feasible vectors of Edmonds-Giles polyhedra
• Stronger multi-commodity flow formulations of the capacitated vehicle routing problem
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• Biased positional games on matroids
• The maximum k-colorable subgraph problem for chordal graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• Weighted independent sets in a subclass of \(P_6\)-free graphs
• Facet identification for the symmetric traveling salesman polytope

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1168215)