The ellipsoid method and its consequences in combinatorial optimization
From MaRDI portal
Redirect page
Cites work
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 3174052 (Why is no real title available?)
- scientific article; zbMATH DE number 3661345 (Why is no real title available?)
- scientific article; zbMATH DE number 3750968 (Why is no real title available?)
- scientific article; zbMATH DE number 3580570 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 3285076 (Why is no real title available?)
- scientific article; zbMATH DE number 3290885 (Why is no real title available?)
- scientific article; zbMATH DE number 3409134 (Why is no real title available?)
- 2-Matchings and 2-covers of hypergraphs
- A Minimax Theorem for Directed Graphs
- A note on two problems in connexion with graphs
- A two-commodity cut theorem
- Convergence rate of the gradient descent method with dilatation of the space
- How to make a digraph strongly connected
- Khachiyan’s algorithm for linear programming
- Matching, Euler tours and the Chinese postman
- Matroid Intersection
- Maximal Flow Through a Network
- Maximum matching and a polyhedron with 0,1-vertices
- Multi-Commodity Network Flows
- Multicommodity flows in planar graphs
- Normal hypergraphs and the perfect graph conjecture
- Odd Minimum Cut-Sets and b-Matchings
- On maximal independent sets of vertices in claw-free graphs
- On the Shannon capacity of a graph
- On the orientation of graphs
- Optimum branchings
- Packing rooted directed cuts in a weighted directed graph
- The NP-Completeness of Edge-Coloring
- The Relaxation Method for Linear Inequalities
- The matroids with the max-flow min-cut property
- Two-commodity cut-packing problem
Cited in
(only showing first 100 items - show all)- Multilinear games
- Cross line and column generation for the cut covering problem in wireless networks
- Regularity radius: properties, approximation and a not a priori exponential algorithm
- The cluster deletion problem for cographs
- A branch-and-cut algorithm for the multiple Steiner TSP with order constraints
- A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere
- Solving the minimum convex partition of point sets with integer programming
- A computational complexity comparative study of graph tessellation problems
- Ranking tournaments with no errors. II: Minimax relation
- An approximation algorithm for the parity-constrained k-supplier problem
- Constraint and satisfiability reasoning for graph coloring
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- Fairness in graph-theoretical optimization problems
- Submodular function minimization and polarity
- Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming
- Information design for multiple interdependent defenders: work less, pay off more
- Minimum dispersion problems
- Bilevel programming and the separation problem
- The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect
- Algorithms for synthesizing mechanical systems with maximal natural frequencies
- Covering intersecting bi-set families under matroid constraints
- A comparison of two edge-coloring formulations
- On maximum independent set of categorical product and ultimate categorical ratios of graphs
- An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
- On the cut polytope
- Cardinality constraints and systems of restricted representatives
- On independent vertex sets in subclasses of apple-free graphs
- Coloring square-free Berge graphs
- On the approximability of adjustable robust convex optimization under uncertainty
- Strongly polynomial simplex algorithm for bipartite vertex packing
- On the maximum weight independent set problem in graphs without induced cycles of length at least five
- Mixed integer formulations using natural variables for single machine scheduling around a common due date
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path
- A polyhedral view to a generalization of multiple domination
- On some weakly bipartite graphs
- Better bin packing approximations via discrepancy theory
- Constructive Discrepancy Minimization for Convex Sets
- Tight lower bounds for the complexity of multicoloring
- Submodularity in Conic Quadratic Mixed 0–1 Optimization
- Separation of partition inequalities for the \((1,2)\)-survivable network design problem
- Characterization of feedback Nash equilibria for multi-channel systems via a set of non-fragile stabilizing state-feedback solutions and dissipativity inequalities
- Orthogonally convex covering of orthogonal polygons without holes
- Finding and Recognizing Popular Coalition Structures
- A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions
- The maximum clique problem
- Buyer selection and service pricing in an electric fleet supply chain
- Submodular function minimization
- The complexity of lifted inequalities for the knapsack problem
- Graph transformations preserving the stability number
- Semi-definite programming and quantum information
- Multi-word-representability of graphs
- ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS
- The complexity of LSH feasibility
- On coloring problems with local constraints
- Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
- Tree decomposition and discrete optimization problems: a survey
- Ranking tournaments with no errors. I: Structural description
- Valid inequalities for quadratic optimisation with domain constraints
- Approximating minimum bounded degree spanning trees to within one of optimal
- On claw-free t-perfect graphs
- Metrics and undirected cuts
- Exploring the complexity boundary between coloring and list-coloring
- Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Graph isomorphism and theorems of Birkhoff type
- Perfect circular arc coloring
- A magnetic procedure for the stability number
- The performance of an upper bound on the fractional chromatic number of weighted graphs
- Are stable instances easy?
- On extensions of min-k-union
- Minimizing convex functions with rational minimizers
- Non-cancellative Boolean circuits: a generalization of monotone Boolean circuits
- Non-interfering network flows
- Grothendieck’s Theorem, past and present
- Recognition problems for special classes of polynomials in 0-1 variables
- Vertex cover meets scheduling
- Tractability in constraint satisfaction problems: a survey
- NP-hardness of the recognition of coordinated graphs
- Chromatic Gallai identities operating on Lovász number
- Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
- The Schrijver system of odd join polyhedra
- Application of the ellipsoid method in an interactive procedure for multicriteria linear programming
- Small solutions of linear diophantine equations
- A cutting plane algorithm for minimum perfect 2-matchings
- Independent sets in some classes of \(S_{i,j,k}\)-free graphs
- Efficient algorithms for privately releasing marginals via convex relaxations
- Hard promise problems and nonuniform complexity
- POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
- A linear programming formulation for the maximum complete multipartite subgraph problem
- A new branch-and-bound algorithm for the maximum edge-weighted clique problem
- Polynomial-time algorithms for multimarginal optimal transport problems with structure
- Constrained submodular maximization via a nonsymmetric technique
- On the relative complexity of 15 problems related to~0/1-integer programming
- A geometric approach to betweenness
- Brick decompositions and the matching rank of graphs
- Envy-free pricing in multi-item markets
- Polyhedral aspects of discrete optimization
- Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
- Chromatic characterization of biclique covers
- Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations
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)
