Geometric algorithms and combinatorial optimization.
From MaRDI portal
Publication:1309040
zbMath0837.05001MaRDI QIDQ1309040
Martin Grötschel, Alexander Schrijver, László Lovász
Publication date: 28 November 1993
Published in: Algorithms and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/204222
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Computational aspects related to convexity (52B55) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries, The power of two choices for random walks, A Technique for Obtaining True Approximations for k-Center with Covering Constraints, Lifting for Simplicity: Concise Descriptions of Convex Sets, A Polytope for a Product of Real Linear Functions in 0/1 Variables, Extremal Probability Bounds in Combinatorial Optimization, Generalized Optimal Matching Methods for Causal Inference, Concentration phenomena in high dimensional geometry, Unnamed Item, A Fast and Practical Method to Estimate Volumes of Convex Polytopes, Improving Variable Orderings of Approximate Decision Diagrams Using Reinforcement Learning, Unreliable point facility location problems on networks, Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics, On Fault-Tolerant Low-Diameter Clusters in Graphs, Small Chvátal rank, Convex hulls, oracles, and homology, Effective lattice point counting in rational convex polytopes, Submodular Functions: Learnability, Structure, and Optimization, On the convexity of independent set games, Solving the Distance-Based Critical Node Problem, Minimization of even conic functions on the two-dimensional integral lattice, Finding a Stable Allocation in Polymatroid Intersection, Optimization over Degree Sequences, On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms, A class of optimization problems motivated by rank estimators in robust regression, Finding and certifying a large hidden clique in a semirandom graph, Hypergraph Cuts with General Splitting Functions, Ratio and Weight Quantiles, Attacking the linear congruential generator on elliptic curves via lattice techniques, Drainage area maximization in unconventional hydrocarbon fields with integer linear programming techniques, Polynomial-time algorithms for multimarginal optimal transport problems with structure, Complexity and Approximation of the Continuous Network Design Problem, High-multiplicity \(N\)-fold IP via configuration LP, Separation problems for the stable set polytope, Portioning using ordinal preferences: fairness and efficiency, Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model, The Mixed Evacuation Problem, Unnamed Item, Unnamed Item, Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem, Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs, Expander graphs and their applications, Unnamed Item, A Polynomial Time Algorithm for Computing Extinction Probabilities of Multitype Branching Processes, Unnamed Item, Prescribing the binary digits of squarefree numbers and quadratic residues, Computation in Causal Graphs, Unnamed Item, Approximating Tverberg points in linear time for any fixed dimension, The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems, A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization, The capacitated arc routing problem with intermediate facilities, Grothendieck’s Theorem, past and present, Odd Multiway Cut in Directed Acyclic Graphs, The Optimal Design of Low-Latency Virtual Backbones, The Complexity of Partial Function Extension for Coverage Functions, Integer Programming in Parameterized Complexity: Three Miniatures., Finding nucleolus of flow game, Comparison of Metric Spectral Gaps, Relaxation Analysis for the Dynamic Knapsack Problem with Stochastic Item Sizes, A Heuristic Solution of a Cutting Problem Using Hypergraphs, LP Solutions of Vectorial Integer Subset Sums – Cryptanalysis of Galbraith’s Binary Matrix LWE, Algorithmic Cost Allocation Games: Theory and Applications, Approximating the volume of tropical polytopes is difficult, Predicting nonlinear pseudorandom number generators, Unnamed Item, Unnamed Item, Short rational generating functions for lattice point problems, On the Max Coloring Problem, Matrix convex hulls of free semialgebraic sets, Graph Stabilization: A Survey, Fractional path coloring in bounded degree trees with applications, Introduction to Semidefinite, Conic and Polynomial Optimization, Convex Hulls of Algebraic Sets, A short proof of a min–max relation for the bases packing of a matroid, Robust Independence Systems, An efficient characterization of submodular spanning tree games, A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations, Computing the Ehrhart quasi-polynomial of a rational simplex, A Strongly Polynomial Algorithm for a Class of Minimum-Cost Flow Problems with Separable Convex Objectives, A Dynamic Programming Approach for a Class of Robust Optimization Problems, Generalized Center Problems with Outliers, Unnamed Item, The Stable Fixtures Problem with Payments, The Computational Complexity of Duality, Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope, Binary Component Decomposition Part I: The Positive-Semidefinite Case, Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms, Coloring Fuzzy Circular Interval Graphs, Perfect Digraphs, Explicit Near-Ramanujan Graphs of Every Degree, Newell-Littlewood numbers, Reducing Path TSP to TSP, Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming, On the Complexity of Inverse Mixed Integer Linear Optimization, Approximation algorithms for cost-robust discrete minimization problems based on their LP-relaxations, A characterization of odd-hole inequalities related to Latin squares, Parametric Shortest-Path Algorithms via Tropical Geometry, Unnamed Item, Satgraphs and independent domination. I, König graphs for 3-paths and 3-cycles, Energy-efficient scheduling and routing via randomized rounding, A linear optimization oracle for zonotope computation, Integer programming techniques for the nurse rostering problem, Recognizing Hamming graphs in linear time and space, Improved approximation algorithms for metric maximum ATSP and maximum 3-cycle cover problems, The mixed evacuation problem, Competitive online multicommodity routing, A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks, Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory, Vertical perimeter versus horizontal perimeter, Quasi-Newton algorithm for optimal approximate linear regression design: optimization in matrix space, Min-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutions, Matroid optimisation problems with nested non-linear monomials in the objective function, Costly circuits, submodular schedules and approximate Carathéodory theorems, The stable fixtures problem with payments, Improving the efficiency of the branch and bound algorithm for integer programming based on ``flatness information, Fixed interval scheduling: models, applications, computational complexity and algorithms, Designing two-echelon supply networks, Checking strict positivity of Kraus maps is NP-hard, Computational study of large-scale \(p\)-median problems, Polytopes of minimum positive semidefinite rank, A computational study of a cutting plane algorithm for university course timetabling, Scheduling orders for multiple product types to minimize total weighted completion time, The probability of choosing primitive sets, A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars, Combinatorial optimization with one quadratic term: spanning trees and forests, On the configuration LP for maximum budgeted allocation, Coloring fuzzy circular interval graphs, Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\), Space-efficient scheduling of stochastically generated tasks, Tight lower bounds for halfspace range searching, A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization, Online variable-sized bin packing with conflicts, Many 2-level polytopes from matroids, Geometric complexity theory. III: On deciding nonvanishing of a Littlewood-Richardson coefficient, Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Scheduling of uniform parallel machines with s-precedence constraints, A time-indexed LP-based approach for min-sum job-shop problems, The maximum deviation just-in-time scheduling problem., Moment inequalities for sums of random matrices and their applications in optimization, Fair cost allocations under conflicts - a game-theoretic point of view -, Packing and partitioning orbitopes, A \({\mathsf{D}}\)-induced duality and its applications, Tight results on minimum entropy set cover, Specialized fast algorithms for IQC feasibility and optimization problems., A cost-aggregating integer linear program for motif finding, Two-dimensional packing with conflicts, Some efficiently solvable problems over integer partition polytopes, On the maximum acyclic subgraph problem under disjunctive constraints, The wheels of the OLS polytope: Facets and separation, A Euclid style algorithm for MacMahon's partition analysis, The maximum \(k\)-colorable subgraph problem and orbitopes, Efficient edge-skeleton computation for polytopes defined by oracles, Robust combinatorial optimization under convex and discrete cost uncertainty, Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time, Epsilon-net method for optimizations over separable states, Partitioning posets, On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data, The travelling preacher, projection, and a lower bound for the stability number of a graph, Computing robust basestock levels, On the complexity of bandwidth allocation in radio networks, An axiomatic duality framework for the theta body and related convex corners, A generalized approximation framework for fractional network flow and packing problems, Matching theory -- a sampler: From Dénes König to the present, On the hardness of computing intersection, union and Minkowski sum of polytopes, A fast space-decomposition scheme for nonconvex eigenvalue optimization, Min-max-min robust combinatorial optimization, On the max coloring problem, An improved semidefinite programming hierarchy for testing entanglement, Minimal containment under homothetics: a simple cutting plane approach, Ear decomposition for pair comparison data, Aggregate operators in constraint query languages, Computing regions of interest for geometric features in digital images, An improved approximation algorithm for the partial Latin square extension problem., Computability in linear algebra, On the tractability of coloring semirandom graphs, The inverse Fermat-Weber problem, Optimal routing in double loop networks, Lattice-based treshold-changeability for standard CRT secret-sharing schemes, Small Littlewood-Richardson coefficients, Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits, Extended formulations, nonnegative factorizations, and randomized communication protocols, On randomized fictitious play for approximating saddle points over convex sets, Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results, Minimum entropy coloring, On column generation formulations for the RWA problem, Approximation algorithms for the weighted independent set problem in sparse graphs, Fair welfare maximization, Mixed volume techniques for embeddings of Laman graphs, An improved approximation algorithm of MULTIWAY CUT., Linear-shaped partition problems, Perfectness and imperfectness of unit disk graphs on triangular lattice points, Applications of semidefinite programming, Tropical varieties for exponential sums, Mathematical problems for the next century, Spectral characterizations of the Lovász number and the Delsarte number of a graph, Enumerating a subset of the integer points inside a Minkowski sum, The polytope of degree sequences of hypergraphs, Lifts for Voronoi cells of lattices, The Complexity of Diagonalization, An indefinite proximal subgradient-based algorithm for nonsmooth composite optimization, Semidefinite Relaxation Methods for Tensor Absolute Value Equations, Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem, A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization, Advances on strictly \(\varDelta \)-modular IPs, Breaking Indecision in Multiagent, Multioption Dynamics, A Unified Framework for Pricing in Nonconvex Resource Allocation Games, The polyhedral-surface cutting plane method of optimization over a vertex-located set, Discrete Optimal Transport with Independent Marginals is #P-Hard, Valid Inequalities and Separation Algorithms for the Set Partitioning Problem, Anti Tai mapping for unordered labeled trees, Robust two-stage combinatorial optimization problems under convex second-stage cost uncertainty, Optimal patchings for consecutive ones matrices, Notes on \(\{a,b,c\}\)-modular matrices, Graph theory -- a survey on the occasion of the Abel Prize for László Lovász, On a positive semidefinite relaxation of the cut polytope, Note on maximal split-stable subgraphs, Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion, Complexity of integer quasiconvex polynomial optimization, Packing Steiner trees with identical terminal sets, Testing probabilistic models of choice using column generation, Local cuts for mixed-integer programming, Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables, Vaidya's method for convex stochastic optimization problems in small dimension, A space decomposition scheme for maximum eigenvalue functions and its applications, Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, Robust ranking and portfolio optimization, On imposing connectivity constraints in integer programs, On tail dependence matrices. The realization problem for parametric families, Transportation infrastructure network design in the presence of modal competition: computational complexity classification and a genetic algorithm, A polynomial algorithm for minimizing discrete convic functions in fixed dimension, Unconditional reflexive polytopes, Alternatives for testing total dual integrality, Ideals of graph homomorphisms, Combinatorial \(n\)-fold integer programming and applications, Approximation algorithms for energy-efficient scheduling of parallel jobs, Structural aspects of ordered polymatroids, Scheduling split intervals with non-uniform demands, Generalized Littlewood-Richardson coefficients for branching rules of \(\mathrm{GL}(n)\) and extremal weight crystals, Parsimonious formulations for low-diameter clusters, Tropical Ehrhart theory and tropical volume, Complete description for the spanning tree problem with one linearised quadratic term, On the frontiers of polynomial computations in tropical geometry, A new framework to relax composite functions in nonlinear programs, Extremal general affine surface areas, Enumeration of 2-level polytopes, On the complexity of 4-coloring graphs without long induced paths, On the symmetry function of a convex set, Relative blocking in posets, Improved bounds on the diameter of lattice polytopes, Polynomial-time algorithms for computing distances of fuzzy transition systems, On exact and approximate stochastic dominance strategies for portfolio selection, Preemptive and non-preemptive generalized min sum set cover, A probabilistic analytic center cutting plane method for feasibility of uncertain LMIs, A note on non-degenerate integer programs with small sub-determinants, Subgroups generated by rational functions in finite fields, Quantitative evaluation of time-dependent Petri nets and applications to biochemical networks, Sandwich theorems and capacity bounds for non-commutative graphs, Computing the spark: mixed-integer programming for the (vector) matroid girth problem, A new class of facets for the Latin square polytope, Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem, On the computational complexity of weighted voting games, A comparison of two different formulations for arc routing problems on mixed graphs, Strong IP formulations need large coefficients, Polynomial inequalities representing polyhedra, Polyhedral properties of the induced cluster subgraphs, Exact solution algorithms for the maximum flow problem with additional conflict constraints, A convex optimisation framework for the unequal-areas facility layout problem, Preprocessing and cutting planes with conflict graphs, Achieving target equilibria in network routing games without knowing the latency functions, Robust sample average approximation, The fairest core in cooperative games with transferable utilities, On exact Reznick, Hilbert-Artin and Putinar's representations, An oracle for the discrete-time integral quadratic constraint problem, Noisy polynomial interpolation modulo prime powers, A new distributed approximation algorithm for the maximum weight independent set problem, Subexponential parameterized algorithms and kernelization on almost chordal graphs, A fast approximation algorithm for solving the complete set packing problem, Volume computation for sparse Boolean quadric relaxations, Solving degenerate sparse polynomial systems faster, Cutting-plane proofs in polynomial space, Face dimensions of general-purpose cutting planes for mixed-integer linear programs, Generalized Greenberger-Horne-Zeilinger arguments from quantum logical analysis, Vanishing of Littlewood-Richardson polynomials is in P, Matroid optimization problems with monotone monomials in the objective, Polynomial size linear programs for problems in \textsc{P}, On fractional cut covers, Noisy Chinese remaindering in the Lee norm, An approximation algorithm for a general class of multi-parametric optimization problems, Quantum generalizations of the polynomial hierarchy with applications to \(\mathrm{QMA(2)}\), Strongly polynomial FPTASes for monotone dynamic programs, Polymatroid-based capacitated packing of branchings, Robust inventory problem with budgeted cumulative demand uncertainty, A new parallel lattice reduction algorithm for BKZ reduced bases, Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs, Monotone maps, sphericity and bounded second eigenvalue, Permutohedra and minimal matrices, Kantorovich-Rubinstein distance and barycenter for finitely supported measures: foundations and algorithms, A framework for generalized Benders' decomposition and its application to multilevel optimization, Dynamic node packing, On some algorithmic aspects of hypergraphic matroids, The complexity of partition functions, Network reinforcement, The wheels of the orthogonal Latin squares polytope: classification and valid inequalities, Enforcing efficient equilibria in network design games via subsidies, Suppression distance computation for hierarchical clusterings, Graph-theoretical properties of parallelism in the digital plane, Convex generalized flows, Rank-one quantum games, Point partition numbers: perfect graphs, A technique for obtaining true approximations for \(k\)-center with covering constraints
