Geometric algorithms and combinatorial optimization
From MaRDI portal
Publication:1210712
zbMath0634.05001MaRDI QIDQ1210712
Alexander Schrijver, László Lovász, 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
68Q25: Analysis of algorithms and problem complexity
05-02: Research exposition (monographs, survey articles) pertaining to combinatorics
52B55: Computational aspects related to convexity
90C57: Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C60: Abstract computational complexity for mathematical programming problems
90C05: Linear programming
90C27: Combinatorial optimization
05B35: Combinatorial aspects of matroids and geometric lattices
90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Improving an upper bound on the stability number of a graph, Some new hereditary classes where graph coloring remains NP-hard, Flow metrics, Inductively inferring valid logical models of continuous-state dynamical systems, Computing the volume, counting integral points, and exponential sums, How hard is half-space range searching?, On existence theorems, A scaling technique for finding the weighted analytic center of a polytope, The even and odd cut polytopes, A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio, Non-standard approaches to integer programming, Cutting planes in integer and mixed integer programming, Semi-definite relaxation algorithm of multiple knapsack problem, On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality, Adapting polyhedral properties from facility to hub location problems, Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT, Approximation algorithms for scheduling unrelated parallel machines, Solution of large-scale symmetric travelling salesman problems, Mathematical programming formulations for machine scheduling: A survey, A fast algorithm for minimum weight odd circuits and cuts in planar graphs, Bimonotone linear inequalities and sublattices of \(\mathbb R^n\), The Van der Waerden conjecture for mixed discriminants, An algorithmic theory of learning: robust concepts and random projection, A construction for non-rank facets of stable set polytopes of webs, Novel evolutionary models and applications to sequence alignment problems, Semidefinite programming relaxations for graph coloring and maximal clique problems, Strengthened semidefinite programming bounds for codes, On the bin packing problem with a fixed number of object weights, The quadratic knapsack problem -- a survey, A characterization of Delsarte's linear programming bound as a ratio bound, Budget constrained minimum cost connected medians, Semidefinite bounds for the stability number of a graph via sums of squares of polynomials, Approximation algorithms for extensible bin packing, Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm, Analyzing the Held-Karp TSP bound: A monotonicity property with application, Precoloring extension of co-Meyniel graphs, Submodular function minimization, Optimization over the polyhedron determined by a submodular function on a co-intersecting family, A note on compact graphs, Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces, Negative circuits for flows and submodular flows, The complexity of two-person zero-sum games in extensive form, Projection algorithms for linear programming, On a graph partition problem with application to VLSI layout, A problem that is easier to solve on the unit-cost algebraic RAM, On the redundancy of fuzzy partitions, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case, Facets for node packing, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Weak \(k\)-majorization and polyhedra, Minimizing symmetric submodular functions, Two-best solutions under distance constraints: The model and exemplary results for matroids, Test sets of integer programs, Stable sets and polynomials, The computational complexity of knot and matroid polynomials, A unifying location model on tree graphs based on submodularity property, A technique for speeding up the solution of the Lagrangean dual, A deep cut ellipsoid algorithm for convex programming: Theory and applications, Directed Steiner problems with connectivity constraints, The maximum clique problem, Laplacian eigenvalues and the maximum cut problem, On the expected number of \(k\)-sets, Computing the Ehrhart polynomial of a convex lattice polytope, Approximations for the maximum acyclic subgraph problem, Minimum cost multiflows in undirected networks, Solving \(0/1\) integer programs with enumeration cutting planes, Characterizing consistency in probabilistic logic for a class of Horn clauses, Extreme convex set functions with many nonnegative differences, A branch bound method for subset sum problem, On the complexity of some basic problems in computational convexity. I. Containment problems, Weighted fractional and integral \(k\)-matching in hypergraphs, How to tidy up a symmetric set-system by use of uncrossing operations, Utility function programs and optimization over the efficient set in multiple-objective decision making, Order preserving assignments without contiguity, On the complexity of testing membership in the core of min-cost spanning tree games, Semidefinite programming in combinatorial optimization, Cuts, matrix completions and graph rigidity, Tight approximations for resource constrained scheduling and bin packing, Multiflows and disjoint paths of minimum total cost, A fully polynomial epsilon approximation cutting plane algorithm for solving combinatorial linear programs containing a sufficiently large ball, Complexity of searching an immobile hider in a graph, Minimum weight \((T,d)\)-joins and multi-joins, Polyhedral characterizations and perfection of line graphs, Some thoughts on combinatorial optimisation, Minimization of an M-convex function, A note on Schrijver's submodular function minimization algorithm., On tiling under tomographic constraints., Approximate strong separation with application in fractional graph coloring and preemptive scheduling., Packing cycles in graphs, Computing graph invariants on rotagraphs using dynamic algorithm approach: The case of (2, 1)-colorings and independence numbers, The task allocation problem with constant communication., A push-relabel framework for submodular function minimization and applications to parametric optimization, Clique family inequalities for the stable set polytope of quasi-line graphs., Separating multi-oddity constrained shortest circuits over the polytope of stable multisets., Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., Selected papers in honor of Manuel Blum on the occasion of his 60th birthday. Selected papers from the international conference in Theoretical Computer Science, Hong Kong, April 20-24, 1998, On the limits of nonapproximability of lattice problems, The toughness of split graphs, On one maximum multiflow problem and related metrics, Semidefinite programming, A 2-approximation algorithm for the minimum weight edge dominating set problem, On approximability of the independent/connected edge dominating set problems, Short vectors of planar lattices via continued fractions, Query by committee, linear separation and random walks., A polynomial-time algorithm for the bistable roommates problem, A 3-approximation algorithm for the \(k\)-level uncapacitated facility location problem, Approximation algorithms for shop scheduling problems with minsum objective, Totally tight Chvatal-Gomory cuts, K-submodular functions and convexity of their Lovász extension, On the mean radius of permutation polytopes, Biased positional games on matroids, A branch and cut algorithm for hub location problems with single assignment, Conversion of coloring algorithms into maximum weight independent set algorithms, Probing polygons minimally is hard, A random polynomial time algorithm for well-routing convex bodies, Combinatorial optimization and small polytopes, A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem, Determining lower and upper bounds on probabilities of atomic propositions in sets of logical formulas represented by digraphs, On the supermodular knapsack problem, Traveling salesman games with the Monge property, Polyhedral structure of submodular and posi-modular systems, A combinatorial algorithm minimizing submodular functions in strongly polynomial time., Bicliques and eigenvalues, Graph imperfection. I, A fully combinatorial algorithm for submodular function minimization., Graph imperfection. II, Approximating minimum cocolorings., A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, Random utility models and their applications: Recent developments, Minimum \(k\) arborescences with bandwidth constraints, Classical complexity and quantum entanglement, Lift-and-project ranks and antiblocker duality, On the even permutation polytope, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Applications of cut polyhedra. II, Approximating minimum-cost graph problems with spanning tree edges, Largest \(j\)-simplices in \(n\)-polytopes, On the integral dicycle packings and covers and the linear ordering polytope, A unified approach to polynomially solvable cases of integer ``non-separable quadratic optimization, On the core of the minimum cost Steiner tree game in networks, Interval stochastic matrices: A combinatorial lemma and the computation of invariant measures of dynamical systems, Some geometric results in semidefinite programming, Irregularities of point distributions relative to homothetic convex bodies. I, Stability critical graphs and ranks facets of the stable set polytope, On the partial order polytope of a digraph, Genetic algorithms in constrained optimization, Mixed-volume computation by dynamic lifting applied to polynomial system solving, A cutting plane algorithm for convex programming that uses analytic centers, A primal-dual potential reduction method for problems involving matrix inequalities, Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions, On complexity, representation and approximation of integral multicommodity flows, On the number of lattice free polytopes, Linear inequalities for flags in graded partially ordered sets, On the \(k\)-cut problem, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs, Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem, Solving the maximum clique problem using a tabu search approach, Computational complexity of inner and outer \(j\)-radii of polytopes in finite-dimensional normed spaces, Strengthened 0-1 linear formulation for the daily satellite mission planning, MIPping closures: An instant survey, On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids, A note on approximation of a ball by polytopes, Supermodular functions and the complexity of MAX CSP, When can a net fold to a polyhedron?, Exploiting semidefinite relaxations in constraint programming, Path problems in generalized stars, complete graphs, and brick wall graphs, Simulated annealing in convex bodies and an \(O^{*}(n^{4}\)) volume algorithm, Exploring the relationship between max-cut and stable set relaxations, On non-rank facets of stable set polytopes of webs with clique number four, Computational complexity of stochastic programming problems, A constraint generation algorithm for large scale linear programs using multiple-points separation, Toughness in graphs -- a survey, Uniform generation in spatial constraint databases and applications, Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems, On the severity of Braess's paradox: designing networks for selfish users is hard, An algorithmic theory of learning: Robust concepts and random projection, On the commutativity of antiblocker diagrams under lift-and-project operators, An ellipsoid algorithm for probabilistic robust controller design, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, On extracting maximum stable sets in perfect graphs using Lovász's theta function, Robust control strategies for multi--inventory systems with average flow constraints, General models in min-max continuous location: Theory and solution techniques, General models in min-max planar location: Checking optimality conditions, Submodular containment is hard, even for networks, An asymptotically exact algorithm for the high-multiplicity bin packing problem, New approaches for optimizing over the semimetric polytope, On cycles and the stable multi-set polytope, Projection results for vehicle routing, Almost all webs are not rank-perfect, A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, A two-dimensional strip cutting problem with sequencing constraint, The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem, Acceleration of cutting-plane and column generation algorithms: Applications to network design, Approximation algorithm for the group Steiner network problem, On cliques associated to 3-set packing problems, Algorithms for 3PC(⋅, ⋅)-free Berge graphs, On strongly circular-perfectness, Generalized clique family inequalities for claw-free graphs, Random walks in a convex body and an improved volume algorithm, Minimal volume ellipsoids, Unnamed Item, Approximation schemes for ordered vector packing problems, The 2-path network problem, Algorithms for a network design problem with crossing supermodular demands, Approximation algorithms for the covering Steiner problem, Approximation algorithms for finding low-degree subgraphs, Exact and approximative algorithms for coloring G(n,p), A Derivation of Lovász' Theta via Augmented Lagrange Duality, Coloration de graphes : fondements et applications, Packing cuts in undirected graphs, The multiroute maximum flow problem revisited, MAX k‐CUT and approximating the chromatic number of random graphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Classical cuts for mixed-integer programming and branch-and-cut, A branch-and-price approach for the maximum weight independent set problem, Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks, A branch and bound algorithm for the maximum clique problem, A set packing model for the ground holding problem in congested networks, Energy of convex sets, shortest paths, and resistance, A branch-and-cut algorithm for the maximum cardinality stable set problem, On project scheduling with irregular starting time costs, Discrete relaxations of combinatorial programs, A lower bound for the shortest path problem, Rearrangement of DNA fragments: a branch-and-cut algorithm., Optimal oblivious routing in polynomial time, On determining the imperfection ratio, On facets of stable set polytopes of claw-free graphs with stability number three, Hardness of robust network design, Unnamed Item, The computational complexity of graph problems with succinct multigraph representation, The cut cone,L1 embeddability, complexity, and multicommodity flows, A pseudopolynomial network flow formulation for exact knapsack separation, Unnamed Item, Unnamed Item
