The ellipsoid method and its consequences in combinatorial optimization

From MaRDI portal

Publication:1168215

Jump to:navigation, search

DOI10.1007/BF02579273zbMath0492.90056WikidataQ55882924 ScholiaQ55882924MaRDI QIDQ1168215

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

Publication date: 1981

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

matching fractional chromatic number polynomial complexity polynomial algorithms NP hardness submodular set function Khachiyan's algorithm matroid intersection problems optimum covering of directed cuts of a digraph vertex packing in perfect graphs

Mathematics Subject Classification ID

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

Related Items

Clique and chromatic number of circular-perfect graphs, Cross line and column generation for the cut covering problem in wireless networks, Hyperplane separation technique for multidimensional mean-payoff games, The complexity of the node capacitated in-tree packing problem, Complexity of column generation in network design with path-based survivability mechanisms, On the independent dominating set polytope, Chromatic characterization of biclique covers, A Polytope for a Product of Real Linear Functions in 0/1 Variables, The story of perfectly orderable graphs, Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday), Are Stable Instances Easy?, Note on separation from membership, and folklore, On the equivalence between some discrete and continuous optimization problems, Colouring series-parallel graphs, Better s-t-Tours by Gao Trees, Deciding Emptiness of the Gomory-Chvátal Closure is NP-Complete, Even for a Rational Polyhedron Containing No Integer Point, On the approximability of adjustable robust convex optimization under uncertainty, Optimal allocation of stock levels and stochastic customer demands to a capacitated resource, Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs, Decomposition Algorithm for the Single Machine Scheduling Polytope, Independent sets in some classes of \(S_{i,j,k}\)-free graphs, Parameterized Weighted Containment, On additive approximate submodularity, When the Gomory-chvátal closure coincides with the integer hull, A note on the problem of \(r\) disjoint \((s, t)\)-cuts and some related issues, On the number of boundary classes in the 3-colouring problem, Trader multiflow and box-TDI systems in series-parallel graphs, On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube, Large Induced Subgraphs via Triangulations and CMSO, An LP-based approximation algorithm for the generalized traveling salesman path problem, Facets of a mixed-integer bilinear covering set with bounds on variables, Performance analysis of distance-1 distributed algorithms for admission control under the 2-hop interference model, A new branch-and-bound algorithm for the maximum edge-weighted clique problem, On the dominating set polytope, Multilinear Games, Polynomial-time data reduction for weighted problems beyond additive goal functions, The master equality polyhedron with multiple rows, A polyhedral approach to the \textit{alldifferent} system, Constructive Discrepancy Minimization for Convex Sets, LP-Based Algorithms for Capacitated Facility Location, Classes of perfect graphs, Characterizing N+-perfect line graphs, 3-colouring \(P_t\)-free graphs without short odd cycles, Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, Batch Coloring of Graphs, Graphic Submodular Function Minimization: A Graphic Approach and Applications, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, On the theta number of powers of cycle graphs, The complexity of LSH feasibility, An entire space polynomial-time algorithm for linear programming, A note on the Cornaz-Jost transformation to solve the graph coloring problem, An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem, Chromatic Gallai identities operating on Lovász number, The fundamental theorem of linear programming: extensions and applications, The complexity of soft constraint satisfaction, On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem, Submodular Function Minimization under a Submodular Set Covering Constraint, Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions, Nonmonotone Submodular Maximization via a Structural Continuous Greedy Algorithm, Proving total dual integrality with cross-free families—A general framework, Fractional covers for forests and matchings, Polyhedral aspects of discrete optimization, Mutual exclusion scheduling with interval graphs or related classes. II, Series-parallel graphs are windy postman perfect, Tree decomposition and discrete optimization problems: a survey, On classes of minimal circular-imperfect graphs, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Fractionally total colouring \(G_{n,p}\), Modeling and solving the periodic maintenance problem, Unnamed Item, Decomposition and dynamic cut generation in integer linear programming, Unnamed Item, Strong formulations of robust mixed 0-1 programming, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, Approximating the minimum clique cover and other hard problems in subtree filament graphs, The node-edge weighted 2-edge connected subgraph problem: linear relaxation, facets and separation, How to recycle your facets, Independent Sets in Classes Related to Chair-Free Graphs, Computing the clique number of \(a\)-perfect graphs in polynomial time, Tight Bounds on the Radius of Nonsingularity, Reassembling Trees for the Traveling Salesman, Optimal edge-coloring with edge rate constraints, Better Bin Packing Approximations via Discrepancy Theory, Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs, Covering Intersecting Bi-set Families under Matroid Constraints, On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming, The Stable Fixtures Problem with Payments, Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time, On Robust Solutions to Uncertain Linear Complementarity Problems and their Variants, Lovász-Schrijver PSD-Operator on Claw-Free Graphs, On the polynomial time computability of the circular-chromatic number for some superclasses of perfect graphs, Near-perfect graphs with polyhedral, Orthogonal representations over finite fields and the chromatic number of graphs, Perfect circular arc coloring, A linear programming formulation of Mader's edge-disjoint paths problem, On balanced graphs, A linear programming formulation for the maximum complete multipartite subgraph problem, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Variable and value elimination in binary constraint satisfaction via forbidden patterns, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, On the acyclic subgraph polytope, On the density of sets of the Euclidean plane avoiding distance 1, Solving matching problems with linear programming, POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM, An Improved Private Mechanism for Small Databases, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization, SOS Is Not Obviously Automatizable, Even Approximately, On box totally dual integral polyhedra, Approximate Deadline-Scheduling with Precedence Constraints, Non-interfering network flows, Some Results about the Contractions and the Pendant Pairs of a Submodular System, Method of obtaining estimates in quadratic extremal problems with Boolean variables, On the complexity of the surrogate dual of 0–1 programming, Scaling: A general framework, An objective-function ellipsoid-algorithm for convex quadraical programming, Intersection Disjunctions for Reverse Convex Sets, On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere, Karmarkar's projective method for linear programming: a computational survey, Finding and Recognizing Popular Coalition Structures, Hypergraph Cuts with General Splitting Functions, Polyhedral Combinatorics in Combinatorial Optimization, Inductive graph invariants and approximation algorithms, Quantum Annealing versus Digital Computing, Unnamed Item, Asymptotics of the chromatic number for quasi-line graphs, Constrained Submodular Maximization via a Nonsymmetric Technique, From Duels to Battlefields: Computing Equilibria of Blotto and Other Games, Unnamed Item, Tight Lower Bounds for the Complexity of Multicoloring, Unnamed Item, Unnamed Item, Approximating Minimum Cost Connectivity Orientation and Augmentation, Euclidean distortion and the sparsest cut, Packing and covering with integral feasible flows in integral supply-demand networks, Constraint and Satisfiability Reasoning for Graph Coloring, Bicriteria Approximation of Chance-Constrained Covering Problems, Submodularity in Conic Quadratic Mixed 0–1 Optimization, Densities, Matchings, and Fractional Edge-Colorings, Precoloring Extension III: Classes of Perfect Graphs, On coloring problems with local constraints, Hybrid Tractable Classes of Constraint Problems, Grothendieck’s Theorem, past and present, Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover, The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs, A guide to conic optimisation and its applications, Quadratic forms on graphs, Exploring the complexity boundary between coloring and list-coloring, THE GROTHENDIECK CONSTANT IS STRICTLY SMALLER THAN KRIVINE’S BOUND, On kernels in strongly game-perfect digraphs and a characterisation of weakly game-perfect digraphs, Exploring the complexity boundary between coloring and list-coloring, A semidefinite bound for mixing rates of Markov chains, Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions, Deriving compact extended formulations via LP-based separation techniques, Application of the ellipsoid method in an interactive procedure for multicriteria linear programming, Graph transformations preserving the stability number, Adjacency on polymatroids, The History of the LLL-Algorithm, Clique-connecting forest and stable set polytopes, A Note on k-Colorability of P 5-Free Graphs, Unnamed Item, POINT VISIBILITY GRAPHS AND ${\mathcal O}$-CONVEX COVER, The omnipresence of Lagrange, Graph transformations preserving the stability number, Improved approximation algorithms for minimum power covering problems, Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem, Geometric Rescaling Algorithms for Submodular Function Minimization, New results for recognizing convex-QP adverse graphs, A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant, Constant factor approximation for tracking paths and fault tolerant feedback vertex set, Unnamed Item, The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential, A Practicable Robust Counterpart Formulation for Decomposable Functions: A Network Congestion Case Study, Regularity radius: Properties, approximation and a not a priori exponential algorithm, ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS, Polyhedral techniques in combinatorial optimization I: Theory, FLOW ON DATA NETWORK AND A POSITIVE SEMIDEFINITE REPRESENTABLE DELAY FUNCTION, Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs, On the cut polytope, An Approximation Algorithm for Fully Planar Edge-Disjoint Paths, Notes on Hazard-Free Circuits, Graphs and Algorithms in Communication Networks on Seven League Boots, Efficient Online Linear Optimization with Approximation Algorithms, Upper bounds for packings of spheres of several radii, Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal, Envy-free pricing in multi-item markets, Perfect Digraphs, On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five, Improved Randomized Algorithm for k-Submodular Function Maximization, Method of ellipsoids, its generalizations and applications, Unnamed Item, Metrics and undirected cuts, Variable metric relaxation methods, part II: The ellipsoid method, Tight Cycle Relaxations for the Cut Polytope, Optimally Deceiving a Learning Leader in Stackelberg Games, Tight Approximation for Unconstrained XOS Maximization, A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering, Fast Core Pricing for Rich Advertising Auctions, Cardinality constraints and systems of restricted representatives, Vertex cover meets scheduling, Tractability in constraint satisfaction problems: a survey, 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, Realizing symmetric set functions as hypergraph cut capacity, A polyhedral view to a generalization of multiple domination, An approximation algorithm for clustering graphs with dominating diametral path, Routing of uncertain traffic demands, Strip packing with precedence constraints and strip packing with release times, Weighted independent sets in classes of \(P_6\)-free graphs, NP-hardness of the recognition of coordinated graphs, Assignment problems with complementarities, On total variation minimization and surface evolution using parametric maximum flows, Stronger multi-commodity flow formulations of the capacitated vehicle routing problem, On independent vertex sets in subclasses of apple-free graphs, Even pairs in square-free Berge graphs, Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope, Tent and a subclass of \(P_{5}\)-free graphs, Multicuts and perturb \& MAP for probabilistic graph clustering, Fixed interval scheduling: models, applications, computational complexity and algorithms, Maximum weight independent sets in classes related to claw-free graphs, The max-cut problem on graphs not contractible to \(K_ 5\), New applications of clique separator decomposition for the maximum weight stable set problem, Characterization of feedback Nash equilibria for multi-channel systems via a set of non-fragile stabilizing state-feedback solutions and dissipativity inequalities, A characterization of Delsarte's linear programming bound as a ratio bound, A lower bound for intuitionistic logic, Computing clique and chromatic number of circular-perfect graphs in polynomial time, Approximation algorithms for extensible bin packing, On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem, Computational implications of reducing data to sufficient statistics, The cluster deletion problem for cographs, The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect, Bilevel programming and the separation problem, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs, Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs, On 2-stage robust LP with RHS uncertainty: complexity results and applications, Packing cycles exactly in polynomial time, Static and dynamic routing under disjoint dominant extreme demands, Weighted independent sets in a subclass of \(P_6\)-free graphs, On claw-free \(t\)-perfect graphs, On separation and adjacency problems for perfectly matchable subgraph polytopes of a graph, A constraint sampling approach for multi-stage robust optimization, Hybrid tractability of valued constraint problems, Facet identification for the symmetric traveling salesman polytope, Regular inference as vertex coloring, Undirected postman problems with zigzagging option: a cutting-plane approach, The mixing-MIR set with divisible capacities, Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms, On the complexity of submodular function minimisation on diamonds, Faster algorithms for security games on matroids, Distributionally robust multi-item newsvendor problems with multimodal demand distributions, Partitioning posets, On routing in VLSI design and communication networks, Efficient minimization of higher order submodular functions using monotonic Boolean functions, The stable set polytope of quasi-line graphs, George Dantzig's contributions to integer programming, The Grothendieck constant of random and pseudo-random graphs, Semidefinite approximations of conical hulls of measured sets, Using conical regularization in calculating Lagrangian estimates in quadratic optimization problems, On the complexity of bandwidth allocation in radio networks, Strict chordal and strict split digraphs, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, A comparison of two edge-coloring formulations, Optimization with uniform size queries, 3-approximation algorithm for a two depot, heterogeneous traveling salesman problem, The expressive power of binary submodular functions, Pseudo-Boolean optimization, Robust network optimization under polyhedral demand uncertainty is \(NP\)-hard, A magnetic procedure for the stability number, The performance of an upper bound on the fractional chromatic number of weighted graphs, A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions, Maximum weight independent sets in hole- and dart-free graphs, On linear and semidefinite programming relaxations for hypergraph matching, Duality for balanced submodular flows, Algebraic optimization: The Fermat-Weber location problem, Exact localisations of feedback sets, A note on submodular function minimization with covering type linear constraints, The indefinite period traveling salesman problem, Submodular function minimization, Recognizing vertex intersection graphs of paths on bounded degree trees, Social exchange networks with distant bargaining, Stable sets and graphs with no even holes, Packing trees in communication networks, Bidimensional packing by bilinear programming, On the core of network synthesis games, A polynomial algorithm for minimum quadratic cost flow problems, Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization, A new polynomial-time algorithm for linear programming, Updating the complexity status of coloring graphs without a fixed induced linear forest, Combinatorial optimization with 2-joins, Mind the independence gap, Recent trends in combinatorial optimization, Finding feasible vectors of Edmonds-Giles polyhedra, On the integrality of an extreme solution to pluperfect graph and balanced systems, On some weakly bipartite graphs, A note on matchings and separability, Optimizing over the subtour polytope of the travelling salesman problem, Solution of large-scale symmetric travelling salesman problems, A comparison of heuristics and relaxations for the capacitated plant location problem, On standard quadratic programs with exact and inexact doubly nonnegative relaxations, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Forbidden induced pairs for perfectness and \(\omega\)-colourability of graphs, A new greedy strategy for maximizing monotone submodular function under a cardinality constraint, A rounding technique for the polymatroid membership problem, Book review of: L. Lovász, Graphs and geometry, On the integral dicycle packings and covers and the linear ordering polytope, Recognizing bull-free perfect graphs, A LP-based approximation algorithm for generalized traveling salesperson path problem, Maximizing a non-decreasing non-submodular function subject to various types of constraints, On some large-scale LP relaxations for the graph partitioning problem and their optimal solutions, Minimizing submodular functions over families of sets, A new performance bound for submodular maximization problems and its application to multi-agent optimal coverage problems, Reachability in arborescence packings, Extended formulations for the \(A\)-cut problem, Strongly polynomial simplex algorithm for bipartite vertex packing, Restrictions and preassignments in preemptive open shop scheduling, Minimizing submodular functions on diamonds via generalized fractional matroid matchings, \(\varepsilon\)-approximation minimization of convex functions in fixed dimension, Long range planning in the process industries: A projection approach, A linear programming primer: from Fourier to Karmarkar, Algorithms for synthesizing mechanical systems with maximal natural frequencies, Computational geometric approach to submodular function minimization for multiclass queueing systems, Postman problems on series-parallel mixed graphs, 3-colouring AT-free graphs in polynomial time, Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint, Transportation infrastructure network design in the presence of modal competition: computational complexity classification and a genetic algorithm, State partitioning based linear program for stochastic dynamic programs: an invariance property, Outer-product-free sets for polynomial optimization and oracle-based cuts, Portfolio selection under model uncertainty: a penalized moment-based optimization approach, Better 3-coloring algorithms: excluding a triangle and a seven vertex path, A computational complexity comparative study of graph tessellation problems, On circular-perfect graphs: a survey, Phylogenetic flexibility via Hall-type inequalities and submodularity, Perfect \((0,\pm 1)\)-matrices and perfect bidirected graphs, Valid inequalities for quadratic optimisation with domain constraints, Buyer selection and service pricing in an electric fleet supply chain, Ranking tournaments with no errors. II: Minimax relation, The capacitated vehicle routing problem: stronger bounds in pseudo-polynomial time, Hard to solve instances of the Euclidean traveling salesman problem, Random Laplacian matrices and convex relaxations, An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations, On the Lovász theta function and some variants, A copositive approach for two-stage adjustable robust optimization with uncertain right-hand sides, A utility theory based interactive approach to robustness in linear optimization, Reference points and approximation algorithms in multicriteria discrete optimization, Batch coloring of graphs, Network pollution games, A new branch-and-bound algorithm for the maximum weighted clique problem, Biased positional games on matroids, On survivable network polyhedra, Conversion of coloring algorithms into maximum weight independent set algorithms, On \(f\)-domination: polyhedral and algorithmic results, Optimization with additional variables and constraints, On the hardness of designing public signals, Robust flows over time: models and complexity results, On the integrality ratio of the subtour LP for Euclidean TSP, A new combinatorial branch-and-bound algorithm for the knapsack problem with conflicts, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Robust stochastic optimization with convex risk measures: a discretized subgradient scheme, A data-driven distributionally robust bound on the expected optimal value of uncertain mixed 0-1 linear programming, Ranking tournaments with no errors. I: Structural description, On the rational polytopes with Chvátal rank 1, Better \(s-t\)-tours by Gao trees, Transfer flow graphs, On stability of collaborative supplier selection, Structure of a simple scheduling polyhedron, A computational study of several heuristics for the DRPP, Multiple bipartite complete matching vertex blocker problem: complexity, polyhedral analysis and branch-and-cut, Symmetric submodular system: contractions and Gomory-Hu tree, The gap between monotone and non-monotone circuit complexity is exponential, \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts, On the complexity of surrogate and group relaxation for integer linear programs, On the linear extension complexity of stable set polytopes for perfect graphs, On fractional cut covers, On \({\mathbb{K}}^{\Delta}\), A cutting plane algorithm for minimum perfect 2-matchings, Hardness results for multimarginal optimal transport problems, Facets and algorithms for capacitated lot sizing, On the supermodular knapsack problem, Orthogonally convex covering of orthogonal polygons without holes, The operator approach to entropy games, The ellipsoid method and its implications, Minimizing ratio of monotone non-submodular functions, Lower bounds on matrix factorization ranks via noncommutative polynomial optimization, Total tessellation cover: bounds, hardness, and applications, On the number of vertices belonging to all maximum stable sets of a graph, A combinatorial algorithm minimizing submodular functions in strongly polynomial time., Bicliques and eigenvalues, A fully combinatorial algorithm for submodular function minimization., Generalized skew bisubmodularity: a characterization and a min-max theorem, Submodular function minimization and polarity, Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes, On maximum independent set of categorical product and ultimate categorical ratios of graphs, Efficient algorithms for privately releasing marginals via convex relaxations, Separation of partition inequalities for the \((1,2)\)-survivable network design problem, Point partition numbers: perfect graphs, Fractional cocoloring of graphs, Optimized Bonferroni approximations of distributionally robust joint chance constraints, Popular branchings and their dual certificates, Relaxations of vertex packing, Near-perfect matrices, Polyhedral proof methods in combinatorial optimization, A 71/60 theorem for bin packing, A separation algorithm for the matchable set polytope, On randomized stopping points and perfect graphs, Comparison of formulations and a heuristic for packing Steiner trees in a graph, Decomposition and optimization over cycles in binary matroids, Coloring planar perfect graphs by decomposition, Lattice-free polytopes and their diameter, On a conjecture of Meyniel, Matrices with the Edmonds-Johnson property, An application of simultaneous diophantine approximation in combinatorial optimization, The Schrijver system of odd join polyhedra, On submodular function minimization, Towards breaking the exponential barrier for general secret sharing, Costly circuits, submodular schedules and approximate Carathéodory theorems, Locally perfect graphs, The maximum k-colorable subgraph problem for chordal graphs, Valid inequalities and separation for capacitated economic lot sizing, Minimum dispersion problems, Semidefinite programming in combinatorial optimization, Cuts, matrix completions and graph rigidity, A fast algorithm for coloring Meyniel graphs, Lot-size models with backlogging: Strong reformulations and cutting planes, On a class of functions attaining their maximum at the vertices of a polyhedron, Complete formulations of polytopes related to extensions of assignment matrices, Generalized polymatroids and submodular flows, Strong tree-cographs are Birkhoff graphs, A new integer programming formulation for the permutation flowshop problem, Recognition problems for special classes of polynomials in 0-1 variables, Strong formulations for mixed integer programming: A survey, An extension of Karmarkar's projective algorithm for convex quadratic programming, The Boolean quadratic polytope: Some characteristics, facets and relatives, A cutting plane algorithm for a clustering problem, Approximating the independence number via the \(\vartheta\)-function, On approximately fair cost allocation in Euclidean TSP games, A double oracle approach to minmax regret optimization problems with interval data, Approximate strong separation with application in fractional graph coloring and preemptive scheduling., Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems, Data-driven robust optimization, A push-relabel framework for submodular function minimization and applications to parametric optimization, A compact linear program for testing optimality of perfect matchings., Minimal arc-sets spanning dicycles, Complexity of linear programming, Minimization on submodular flows, Coloring square-free Berge graphs, Weakly bipartite graphs and the max-cut problem, An appraisal of computational complexity for operations researchers, The complexity of controlled selection, The principal lattice of partitions of a submodular function, Two algorithms for maximizing a separable concave function over a polymatroid feasible region, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, \(b\)-matching degree-sequence polyhedra, COSINE: A new graph coloring algorithm, A polyhedral approach to edge coloring, \(T\)-colorings of graphs: recent results and open problems, A dual algorithm for submodular flow problems, The traveling salesman problem in graphs with some excluded minors, Stability number and chromatic number of tolerance graphs, Expressing combinatorial optimization problems by linear programs, Solving combinatorial optimization problems using Karmarkar's algorithm, Paths on polymatroids, A cutting plane algorithm for the windy postman problem, Compositions in the bipartite subgraph polytope, The complexity of lifted inequalities for the knapsack problem, Applications of combinatorics to statics --- a second survey, A hierarchical algorithm for making sparse matrices sparser, Optimal multiple interval assignments in frequency assignment and traffic phasing, Hard promise problems and nonuniform complexity, Valid inequalities and facets of the capacitated plant location problem, Multiline addressing by network flow, The optimal path-matching problem, A note on formulations for the \(A\)-partition problem on hypergraphs, Non-cancellative Boolean circuits: A generalization of monotone boolean circuits, Recent results on approximating the Steiner tree problem and its generalizations, The complexity of some problems related to GRAPH 3-COLORABILITY, Role of redundant constraints for improving dual bounds in polynomial optimization problems, The submodular knapsack polytope, A family of easy polyhedra, Approximation results for a bicriteria job scheduling problem on a single machine without preemption, A note on submodular set cover on matroids, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Acyclic digraphs with Gallai-Milgram-Linial property for clique-covers, A polyhedral approach to sequence alignment problems, Decomposition of submodular functions, Brick decompositions and the matching rank of graphs, Testing membership in matroid polyhedra, Boolean polynomials and set functions, A deep cut ellipsoid algorithm for convex programming: Theory and applications, The ellipsoid algorithm using parallel cuts, Partition-distance: A problem and class of perfect graphs arising in clustering, Graph isomorphism and theorems of Birkhoff type, The maximum clique problem, Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions, Coloring perfect \((K_ 4\)-e)-free graphs, Intelligent gradient search in linear programming, Small solutions of linear diophantine equations, Compact vs. exponential-size LP relaxations, Colouring graphs with no induced six-vertex path or diamond, Subgradient ellipsoid method for nonsmooth convex problems, Polynomial-time algorithms for multimarginal optimal transport problems with structure, Beyond submodularity: a unified framework of randomized set selection with group fairness constraints, Cycle selections, Minimum weighted clique cover on claw‐free perfect graphs, Independent set under a change constraint from an initial solution, Optimal hierarchical clustering on a graph, An extended formulation for the 1‐wheel inequalities of the stable set polytope, Universal Algorithms for Clustering Problems, Walrasian equilibria from an optimization perspective: A guide to the literature, A note on the computational complexity of the moment-SOS hierarchy for polynomial optimization, Distance to a constitutive tensor isotropy stratum by the Lasserre polynomial optimization method, Semidefinite programming and its applications to NP problems, Optimizing concurrency under Scheduling by Edge Reversal, A Sum of Squares Characterization of Perfect Graphs, Plowing with precedence in polynomial time, Efficient Optimization of Partition Scan Statistics via the Consecutive Partitions Property, A geometric approach to betweenness, Solving graph partitioning on sparse graphs: cuts, projections, and extended formulations, Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center, Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints, Integer programming models for round Robin tournaments, Stable commutator length in right‐angled Artin and Coxeter groups, Bilevel Programming: The Montreal School, Supermodularity and valid inequalities for quadratic optimization with indicators, A faster algorithm for determining the linear feasibility of systems of BTVPI constraints, On the generation of metric TSP instances with a large integrality gap by branch-and-cut, On the complexity of robust multi-stage problems with discrete recourse, Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles, Near optimal colourability on hereditary graph families, Unnamed Item, Lower bounds and algorithms for the 2-dimensional vector packing problem, On the parallel approximability of a subclass of quadratic programming., Fractional path coloring in bounded degree trees with applications, A characterization of the weighted Lovász number based on convex quadratic programming, Approximating the discrete time-cost tradeoff problem with bounded depth, Constant factor approximation for tracking paths and fault tolerant feedback vertex set, Colouring graphs with no induced six-vertex path or diamond

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1168215&oldid=13236005"