Geometric algorithms and combinatorial optimization
From MaRDI portal
Publication:1210712
zbMATH Open0634.05001MaRDI QIDQ1210712FDOQ1210712
László Lovász, Alexander Schrijver, Martin Grötschel
Publication date: 5 June 1993
Published in: Algorithms and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/204187
Linear programming (90C05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Abstract computational complexity for mathematical programming problems (90C60) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Computational aspects related to convexity (52B55) Combinatorial aspects of matroids and geometric lattices (05B35)
Cited In (only showing first 100 items - show all)
- Title not available (Why is that?)
- Algorithms that access the input via queries
- Combinatorial optimization problems in wireless switch design
- MAX k‐CUT and approximating the chromatic number of random graphs
- A new separation algorithm for the Boolean quadric and cut polytopes
- The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem
- Title not available (Why is that?)
- A heuristic for the stability number of a graph based on convex quadratic programming and tabu search
- LP-based solution methods for the asymmetric TSP
- Collaborative replenishment in the presence of intermediaries
- Title not available (Why is that?)
- An algorithmic theory of learning: robust concepts and random projection
- A Polyhedral Frobenius Theorem with Applications to Integer Optimization
- On extracting maximum stable sets in perfect graphs using Lovász's theta function
- A note on Schrijver's submodular function minimization algorithm.
- Novel evolutionary models and applications to sequence alignment problems
- A note on submodular function minimization with covering type linear constraints
- Clique clustering yields a PTAS for max-coloring interval graphs
- Approximability of clique transversal in perfect graphs
- Distributionally robust optimization with polynomial densities: theory, models and algorithms
- Test sets of integer programs
- Optimization of a convex program with a polynomial perturbation
- Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks
- Sublattices of product spaces: Hulls, representations and counting
- Role of redundant constraints for improving dual bounds in polynomial optimization problems
- Computing the least-core and nucleolus for threshold cardinality matching games
- Separation, dimension, and facet algorithms for node flow polyhedra
- A polynomial-time algorithm for the bistable roommates problem
- A variation of DS decomposition in set function optimization
- Title not available (Why is that?)
- Distances to lattice points in knapsack polyhedra
- On the bin packing problem with a fixed number of object weights
- Parallel Cholesky-based reduction for the weighted integer least squares problem
- Polytopes associated with symmetry handling
- Largest \(j\)-simplices in \(n\)-polytopes
- Set function optimization
- Budget constrained minimum cost connected medians
- Approximation and online algorithms for multidimensional bin packing: a survey
- On complexity, representation and approximation of integral multicommodity flows
- On cycles and the stable multi-set polytope
- Algorithmic Bayesian Persuasion
- Minimum \(k\) arborescences with bandwidth constraints
- On the integral dicycle packings and covers and the linear ordering polytope
- Complexity of searching an immobile hider in a graph
- The toughness of split graphs
- Perron vector optimization applied to search engines
- Strong LP formulations for scheduling splittable jobs on unrelated machines
- On circular-perfect graphs: a survey
- On non-rank facets of stable set polytopes of webs with clique number four
- Optimization over the polyhedron determined by a submodular function on a co-intersecting family
- A pseudopolynomial network flow formulation for exact knapsack separation
- The strong perfect graph conjecture: 40 years of attempts, and its resolution
- Dynamic programming bi-criteria combinatorial optimization
- Graphs vertex-partitionable into strong cliques
- Robust scheduling with budgeted uncertainty
- Geometric random edge
- Determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs
- A minmax regret linear regression model under uncertainty in the dependent variable
- A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem
- Test sets and inequalities for integer programs
- Sharp upper and lower bounds for maximum likelihood solutions to random Gaussian bilateral inequality systems
- A fast algorithm for minimum weight odd circuits and cuts in planar graphs
- Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling
- Coloration de graphes : fondements et applications
- Approximability of sparse integer programs
- On existence theorems
- The even and odd cut polytopes
- On the commutativity of antiblocker diagrams under lift-and-project operators
- Non-standard approaches to integer programming
- On facets of stable set polytopes of claw-free graphs with stability number 3
- Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs
- Lovász-Schrijver PSD-Operator on Claw-Free Graphs
- Some advances on lovász-schrijver \(N_+(\cdot)\) relaxations of the fractional stable set polytope
- Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs
- Semi-definite relaxation algorithm of multiple knapsack problem
- On one maximum multiflow problem and related metrics
- On the supermodular knapsack problem
- A fully combinatorial algorithm for submodular function minimization.
- On the redundancy of fuzzy partitions
- Approximation algorithms for extensible bin packing
- When can a net fold to a polyhedron?
- 0/1-Integer programming: Optimization and Augmentation are equivalent
- Improving an upper bound on the stability number of a graph
- Lift-and-project ranks and antiblocker duality
- A primal-dual potential reduction method for problems involving matrix inequalities
- Approximation algorithms for general packing problems and their application to the multicast congestion problem
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
- Network Design with Weighted Degree Constraints
- Conversion of coloring algorithms into maximum weight independent set algorithms
- The Van der Waerden conjecture for mixed discriminants
- Cuts, matrix completions and graph rigidity
- Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case
- Approximation algorithms for the Bipartite Multicut problem
- LP-oriented upper bounds for the weighted stability number of a graph
- An algorithmic theory of learning: Robust concepts and random projection
- Traveling salesman games with the Monge property
- Polyhedral structure of submodular and posi-modular systems
- Algorithms for a network design problem with crossing supermodular demands
- Flow metrics
- Quadratic bottleneck knapsack problems
Recommendations
This page was built for publication: Geometric algorithms and combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1210712)
