Geometric algorithms and combinatorial optimization
From MaRDI portal
Publication:1210712
zbMath0634.05001MaRDI QIDQ1210712
Martin Grötschel, László Lovász, Alexander Schrijver
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
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
The Van der Waerden conjecture for mixed discriminants, Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique, Realizing symmetric set functions as hypergraph cut capacity, Note on shortest and nearest lattice vectors, Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs, A note on minimizing submodular functions, A fast cost scaling algorithm for submodular flow, Distributionally robust mixed integer linear programs: persistency models with applications, Book review of: J.-B. Lasserre, An introduction to polynomial and semi-algebraic optimization, Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope, A computational study for bilevel quadratic programs using semidefinite relaxations, The firefighter problem: empirical results on random graphs, Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities, Colouring perfect graphs with bounded clique number, Flow metrics, Techniques for exploring the suboptimal set, A polyhedral approach to the single row facility layout problem, Strong lift-and-project cutting planes for the stable set problem, An FPTAS for optimizing a class of low-rank functions over a polytope, On N. Z. Shor's three scientific ideas, Fast recognition of doubled graphs, Advertisement allocation for generalized second-pricing schemes, Constructing uniquely realizable graphs, The stable set polytope of claw-free graphs with stability number at least four. I. Fuzzy antihat graphs are \(\mathcal{W}\)-perfect, Improving an upper bound on the size of \(k\)-regular induced subgraphs, Knapsack problem with probability constraints, Packing cycles exactly in polynomial time, Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme, Vector bin packing with multiple-choice, A stronger LP bound for formula size lower bounds via clique constraints, Network design with weighted degree constraints, On claw-free \(t\)-perfect graphs, Tightening simple mixed-integer sets with guaranteed bounds, Fractional packing in ideal clutters, Approximability of sparse integer programs, Rank-two update algorithms for the minimum volume enclosing ellipsoid problem, Complexity results for the gap inequalities for the max-cut problem, Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number, Competitive evaluation of threshold functions in the priced information model, On prime inductive classes of graphs, Cycle bases in graphs characterization, algorithms, complexity, and applications, On the computational complexity of membership problems for the completely positive cone and its dual, Tree metrics and edge-disjoint \(S\)-paths, Polyhedral study of the connected subgraph problem, A set partitioning reformulation of a school bus scheduling problem, Criticality for multicommodity flows, Emergency connectivity in ad-hoc networks with selfish nodes, Primal-dual approximation algorithm for the two-level facility location problem via a dual quasi-greedy approach, Computational complexity analysis of the sensor location flow observability problem, Approximation bounds for trilinear and biquadratic optimization problems over nonconvex constraints, Fast computation of minimal elementary decompositions of metabolic flux vectors, A randomized sieving algorithm for approximate integer programming, On the complexity of submodular function minimisation on diamonds, Stochastic and semidefinite optimization for scheduling in orthogonal frequency division multiple access networks, Computing cooperative solution concepts in coalitional skill games, Coloring perfect graphs with no balanced skew-partitions, Faster separation of 1-wheel inequalities by graph products, Polynomial time recognition of essential graphs having stability number equal to matching number, Inductively inferring valid logical models of continuous-state dynamical systems, Towards more practical linear programming-based techniques for algorithmic mechanism design, Perfect matching and polymatroids, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, An axiomatic duality framework for the theta body and related convex corners, Computing lower bounds on basket option prices by discretizing semi-infinite linear programming, Computing the volume, counting integral points, and exponential sums, How hard is half-space range searching?, On existence theorems, A polynomial Turing-kernel for weighted independent set in bull-free graphs, 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, On the barrier graph of an arrangement of ray sensors, Equal-need sharing of a network under connectivity constraints, Non-standard approaches to integer programming, Cutting planes in integer and mixed integer programming, Semi-definite relaxation algorithm of multiple knapsack problem, Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree, 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, Improving an upper bound on the stability number of a graph, Some new hereditary classes where graph coloring remains NP-hard, On linear and semidefinite programming relaxations for hypergraph matching, Clique clustering yields a PTAS for max-coloring interval graphs, A note on submodular function minimization with covering type linear constraints, Approximability of clique transversal in perfect graphs, Parallel Cholesky-based reduction for the weighted integer least squares problem, The stable set polytope of claw-free graphs with stability number at least four. II. Striped graphs are \(\mathcal{G}\)-perfect, Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope, Approximation algorithms for scheduling unrelated parallel machines, Combinatorial optimization with 2-joins, Dynamic programming bi-criteria combinatorial optimization, 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, The single-item lot-sizing polytope with continuous start-up costs and uniform production capacity, Regular independent sets, PTAS for densest \(k\)-subgraph in interval graphs, Bimonotone linear inequalities and sublattices of \(\mathbb R^n\), Error bounds for mixed integer linear optimization problems, Stochastic Quadratic Knapsack with Recourse, Comparing Imperfection Ratio and Imperfection Index for Graph Classes, Matrix Relaxations in Combinatorial Optimization, Approximation algorithms for hard capacitated \(k\)-facility location problems, Reconfiguration of colorable sets in classes of perfect graphs, New techniques for cost sharing in combinatorial optimization games, Solving a real-world train-unit assignment problem, Max flow and min cut with bounded-length paths: complexity, algorithms, and approximation, Separation, dimension, and facet algorithms for node flow polyhedra, Centerpoints: A Link Between Optimization and Convex Geometry, Recovering zeros of polynomials modulo a prime, A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, A two-dimensional strip cutting problem with sequencing constraint, Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs, Extended and discretized formulations for the maximum clique problem, Polynomial size IP formulations of knapsack may require exponentially large coefficients, Generating irreducible copositive matrices using the stable set problem, The stable set problem: clique and nodal inequalities revisited, Exact solution approaches for integer linear generalized maximum multiplicative programs through the lens of multi-objective optimization, On the complexity of recognizing integrality and total dual integrality of the \(\{0,1/2\}\)-closure, On some variants of Euclidean \(k\)-supplier, Geodesic geometry on graphs, Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms, Structural Investigation of Piecewise Linearized Network Flow Problems, Facility location problems with user cooperation, A polynomial algorithm for weighted scattering number in interval graphs, On the complexity of quasiconvex integer minimization problem, Polynomial-time data reduction for weighted problems beyond additive goal functions, New Formulations for Choice Network Revenue Management, Convex geometry and its applications. Abstracts from the workshop held December 12--18, 2021 (hybrid meeting), Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph, On the \(d\)-claw vertex deletion problem, The Steiner connectivity problem, Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, Theory of Principal Partitions Revisited, Graphic Submodular Function Minimization: A Graphic Approach and Applications, On the Relative Complexity of 15 Problems Related to 0/1-Integer Programming, Some Problems on Approximate Counting in Graphs and Matroids, Fair allocation of indivisible items with conflict graphs, Approximating the least core value and least core of cooperative games with supermodular costs, 2-clique-bond of stable set polyhedra, Perron vector optimization applied to search engines, Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope, The maximum vertex coverage problem on bipartite graphs, Approximating max-min weighted \(T\)-joins, The traveling salesman problem on cubic and subcubic graphs, Parameterized Algorithms for the Independent Set Problem in Some Hereditary Graph Classes, A branch-and-cut algorithm for a resource-constrained scheduling problem, A primal-dual method for approximating tree cover with two weights, A New Approach to the Stable Set Problem Based on Ellipsoids, A Primal-Dual Algorithm for Weighted Abstract Cut Packing, A cutting plane algorithm for graph coloring, Submodular Function Minimization under a Submodular Set Covering Constraint, On Tree-Constrained Matchings and Generalizations, Clique Clustering Yields a PTAS for max-Coloring Interval Graphs, Batch processing with interval graph compatibilities between tasks, Projected Chvátal-Gomory cuts for mixed integer linear programs, Sublattices of product spaces: Hulls, representations and counting, 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, A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming, An ellipsoid algorithm for probabilistic robust controller design, Wavelength assignment in multifiber star networks, 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, A survey on models and algorithms for discrete evacuation planning network problems, The warehouse-retailer network design game, Semidefinite Programming and Constraint Programming, A one-to-one correspondence between colorings and stable sets, Single Commodity-Flow Algorithms for Lifts of Graphic and CoGraphic Matroids, On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming, Exact Algorithms for Linear Matrix Inequalities, Lovász-Schrijver PSD-Operator on Claw-Free Graphs, Strengthening Chvátal-Gomory Cuts for the Stable Set Problem, Two-Level Polytopes with a Prescribed Facet, On a General Framework for Network Representability in Discrete Optimization, Some advances on Lovász-Schrijver relaxations of the fractional stable set polytope, Near-perfect graphs with polyhedral, 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, Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint, 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, 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, Algorithms that access the input via queries, 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, 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, How to tidy up a symmetric set-system by use of uncrossing operations, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, Utility function programs and optimization over the efficient set in multiple-objective decision making, An algorithmic theory of learning: robust concepts and random projection, Order preserving assignments without contiguity, A construction for non-rank facets of stable set polytopes of webs, 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, 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, Optimization over the polyhedron determined by a submodular function on a co-intersecting family, Tight approximations for resource constrained scheduling and bin packing, Multiflows and disjoint paths of minimum total cost, On the bin packing problem with a fixed number of object weights, 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, 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, Minimum weight \((T,d)\)-joins and multi-joins, Polyhedral characterizations and perfection of line graphs, Approximation algorithms for extensible bin packing, Some thoughts on combinatorial optimisation, Minimization of an M-convex function, Strong LP formulations for scheduling splittable jobs on unrelated machines, A note on Schrijver's submodular function minimization algorithm., Computing the least-core and nucleolus for threshold cardinality matching games, The stable set polytope of icosahedral graphs, 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, A generalization of the integer linear infeasibility problem, Approximation algorithms for general packing problems and their application to the multicast congestion problem, Combinatorial optimization problems in wireless switch design, A note on compact graphs, Inner and outer \(j\)-radii of convex bodies in finite-dimensional normed spaces, Semidefinite programming and arithmetic circuit evaluation, Clique-circulants and the stable set polytope of fuzzy circular interval graphs, The stable set polytope of quasi-line graphs, Negative circuits for flows and submodular flows, Exploiting planarity in separation routines for the symmetric traveling salesman problem, 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, On facets of stable set polytopes of claw-free graphs with stability number 3, A problem that is easier to solve on the unit-cost algebraic RAM, A simpler characterization of a spectral lower bound on the clique number, The expressive power of binary submodular functions, Non-cyclic train timetabling and comparability graphs, A fast exact algorithm for the problem of optimum cooperation and the structure of its solutions, Approximation algorithms for the Bipartite Multicut problem, Precoloring extension of co-Meyniel graphs, Submodular function minimization, Approximation algorithms for group prize-collecting and location-routing problems, Gear composition and the stable set polytope, Minimizing the stabbing number of matchings, trees, and triangulations, Cycle-based facets of chromatic scheduling polytopes, The effect of corners on the complexity of approximate range searching, Characterizing and bounding the imperfection ratio for some classes of graphs, A faster strongly polynomial time algorithm for submodular function minimization, Multiline addressing by network flow, Linear optimization over permutation groups, On the redundancy of fuzzy partitions, Triangle-free strongly circular-perfect graphs, A relation of primal--dual lattices and the complexity of shortest lattice vector problem, Paintshop, odd cycles and necklace splitting, 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, LP-oriented upper bounds for the weighted stability number of a graph, A family of easy polyhedra, Weak \(k\)-majorization and polyhedra, Minimizing symmetric submodular functions, Two-best solutions under distance constraints: The model and exemplary results for matroids, Optimization of a convex program with a polynomial perturbation, The strong perfect graph conjecture: 40 years of attempts, and its resolution, 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, K-submodular functions and convexity of their Lovász extension, Minimum \(k\) arborescences with bandwidth constraints, A branch-and-bound algorithm for a class of mixed integer linear maximum multiplicative programs: a bi-objective optimization approach, 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, On a general framework for network representability in discrete optimization, 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, A linear programming based algorithm to solve a class of optimization problems with a multi-linear objective function and affine constraints, 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, Computing and estimating the volume of the solution space of SMT(LA) constraints, On the partial order polytope of a digraph, A polynomial projection-type algorithm for linear programming, 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, Revisiting \(k\)-sum optimization, Reformulation of the linear program for completely ergodic MDPs with average cost criteria, Computational geometric approach to submodular function minimization for multiclass queueing systems, LLL-reduction for integer knapsacks, A convex programming-based algorithm for mean payoff stochastic games with perfect information, Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time, 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, A simple \(OPT+1\) algorithm for cutting stock under the modified integer round-up property assumption, The task allocation problem with constant communication., A push-relabel framework for submodular function minimization and applications to parametric optimization, Explicit convex and concave envelopes through polyhedral subdivisions, Clique family inequalities for the stable set polytope of quasi-line graphs., Graphs vertex-partitionable into strong cliques, Separating multi-oddity constrained shortest circuits over the polytope of stable multisets., Dimensionality reduction of SDPs through sketching, Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., Complex-demand scheduling problem with application in smart grid, Quantum algorithm design: techniques and applications, Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017, A two-level graph partitioning problem arising in mobile wireless communications, Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via operator scaling, A semidefinite programming method for integer convex quadratic minimization, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Polyhedral studies of vertex coloring problems: the standard formulation, Polyhedral results and a branch-and-cut algorithm for the double traveling salesman problem with multiple stacks, Feasibility recovery for the unit-capacity constrained permutation problem, On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs, The separation problem of rounded capacity inequalities: some polynomial cases, On the Lovász theta function and some variants, Projection results for the \(k\)-partition problem, Collaborative replenishment in the presence of intermediaries, Robust multicovers with budgeted uncertainty, Saving colors and max coloring: some fixed-parameter tractability results, Approximation algorithms for the max-buying problem with limited supply, 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, Integer convex minimization by mixed integer linear optimization, On the lattice programming gap of the group problems, Optimization algorithms for the disjunctively constrained knapsack problem, Complexity and approximations for submodular minimization problems on two variables per inequality constraints, 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, 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, Polyhedral structure of submodular and posi-modular systems, The toughness of split graphs, On one maximum multiflow problem and related metrics, 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., Semidefinite programming, A new transference theorem in the geometry of numbers and new bounds for Ajtai's connection factor, 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, Random utility models and their applications: Recent developments, Totally tight Chvatal-Gomory cuts, Quadratic bottleneck knapsack problems, An SDP-based approach for computing the stability number of a graph, Integer round-up property for the chromatic number of some \(h\)-perfect graphs, Geometric random edge, 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, Covering convex bodies and the closest vector problem, MIPping closures: An instant survey, Tightening a copositive relaxation for standard quadratic optimization problems, The possible winner problem with uncertain weights revisited, Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials, On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids, A note on approximation of a ball by polytopes, Information theoretic parameters of noncommutative graphs and convex corners, Supermodular functions and the complexity of MAX CSP, An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem, Vertex deletion into bipartite permutation graphs, A simple method for convex optimization in the oracle model, Revisiting a cutting-plane method for perfect matchings, Rational factorizations of completely positive matrices, Approximation and online algorithms for multidimensional bin packing: a survey, Optimal multi-unit mechanisms with private demands, Solving rank-constrained semidefinite programs in exact arithmetic, A linear programming primer: from Fourier to Karmarkar, Robust scheduling with budgeted uncertainty, Polytopes associated with symmetry handling, A variation of DS decomposition in set function optimization, A note on the 2-circulant inequalities for the MAX-cut problem, Lattice closures of polyhedra, Distributionally robust optimization with polynomial densities: theory, models and algorithms, Independent sets, cliques, and colorings in graphons, Distances to lattice points in knapsack polyhedra, The clique problem with multiple-choice constraints under a cycle-free dependency graph, Packing, partitioning, and covering symresacks, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring, PASS approximation: a framework for analyzing and designing heuristics, Extensions of dynamic programming for multi-stage combinatorial optimization, Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions, The Collatz-Wielandt quotient for pairs of nonnegative operators., On complexity, representation and approximation of integral multicommodity flows, On the number of lattice free polytopes, Shorter tours and longer detours: uniform covers and a bit beyond, Facets from gadgets, A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees, On circular-perfect graphs: a survey, Linear inequalities for flags in graded partially ordered sets, Diffusion bank networks and capital flows, 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, Computation and efficiency of potential function minimizers of combinatorial congestion games, A smaller extended formulation for the odd cycle inequalities of the stable set polytope, On the parameterized tractability of single machine scheduling with rejection, Abstract flows over time: a first step towards solving dynamic packing problems, A minmax regret linear regression model under uncertainty in the dependent variable, On the approximability of robust network design, Pricing lotteries, A branch and cut algorithm for minimum spanning trees under conflict constraints, On tree-constrained matchings and generalizations, The graph tessellation cover number: chromatic bounds, efficient algorithms and hardness, Analysis of a generalized linear ordering problem via integer programming, Sharp upper and lower bounds for maximum likelihood solutions to random Gaussian bilateral inequality systems, A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation, Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, Inequity aversion pricing over social networks: approximation algorithms and hardness results, Dispersing obnoxious facilities on a graph, Separation routine and extended formulations for the stable set problem in claw-free graphs, Forbidden subgraphs of power graphs, Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time, The complexity of computing a robust flow, On the structure of linear programs with overlapping cardinality constraints, Independent sets in \((P_4+P_4\),triangle)-free graphs, Symmetric submodular system: contractions and Gomory-Hu tree, Fractional matching preclusion number of graphs and the perfect matching polytope, A PTAS for a class of binary non-linear programs with low-rank functions, Strengthened clique-family inequalities for the stable set polytope, Complexity of branch-and-bound and cutting planes in mixed-integer optimization. II, Rotor-routing reachability is easy, chip-firing reachability is hard, Set function optimization, Computing in combinatorial optimization, The general graph matching game: approximate core, Reachability analysis of low-order discrete state reaction networks obeying conservation laws, Computing the weighted isolated scattering number of interval graphs in polynomial time, Computing the nucleolus of weighted voting games in pseudo-polynomial time, Generalized skew bisubmodularity: a characterization and a min-max theorem, A new separation algorithm for the Boolean quadric and cut polytopes, Algorithms for the clique problem with multiple-choice constraints under a series-parallel dependency graph, Revisiting surrogate relaxation for the multidimensional knapsack problem, Estimating the volume of solution space for satisfiability modulo linear real arithmetic, The ultimate rank of tropical matrices, Polynomial-time computation of exact correlated equilibrium in compact games, A gentle, geometric introduction to copositive optimization, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, Three-monotone interpolation, Complete positivity and distance-avoiding sets, Constructing lattice-free gradient polyhedra in dimension two, Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, Disjointness graphs of segments in the space, Solving Linear Programming with Constraints Unknown, Towards More Practical Linear Programming-Based Techniques for Algorithmic Mechanism Design, Convex Relaxations for Permutation Problems, Decomposition Algorithm for the Single Machine Scheduling Polytope, Efficient joint object matching via linear programming, Minimum weighted clique cover on claw‐free perfect graphs, Fair allocation algorithms for indivisible items under structured conflict constraints, Least distortion Euclidean embeddings of flat tori, Unified representation of the classical ellipsoid method, Optimal Embedded and Enclosing Isosceles Triangles, An extended formulation for the 1‐wheel inequalities of the stable set polytope, A criterion space search algorithm for mixed integer linear maximum multiplicative programs: a multiobjective optimization approach, Vector balancing in Lebesgue spaces, Minimax Problems with Coupled Linear Constraints: Computational Complexity and Duality, From approximate to exact integer programming, Optimizing concurrency under Scheduling by Edge Reversal, Deciding feasibility of a booking in the European gas market on a cycle is in P for the case of passive networks, A Sum of Squares Characterization of Perfect Graphs, Reconstructing points of superelliptic curves over a prime finite field, Coloring \((4K_1,C_4,C_6)\)-free graphs, Solving larger maximum clique problems using parallel quantum annealing, Approximation algorithms for feasible cut and multicut problems, 0/1-Integer programming: Optimization and Augmentation are equivalent, Minimum weight clustered dominating tree problem, A colorful Steinitz lemma with application to block-structured integer programs, On Integrality in Semidefinite Programming for Discrete Optimization, The possible winner with uncertain weights problem, Treewidth versus clique number. II: Tree-independence number, A polytime preprocess algorithm for the maximum independent set problem, Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube, Complexity of optimizing over the integers, A Modern View on Stability of Approximation, Unnamed Item, An approximation algorithm for indefinite mixed integer quadratic programming, On permuting some coordinates of polytopes, Revisiting security estimation for LWE with hints from a geometric perspective, Eigenpolytope Universality and Graphical Designs, Computing the fully optimal spanning tree of an ordered bipolar directed graph, Unnamed Item, Efficient Convex Optimization with Oracles, Asymmetric Distances for Approximate Differential Privacy, Classical cuts for mixed-integer programming and branch-and-cut, A branch-and-price approach for the maximum weight independent set problem, A simple polynomial-time rescaling algorithm for solving linear programs, Deriving compact extended formulations via LP-based separation techniques, Minimum ratio canceling in oracle polynomial for linear programming, but not strongly polynomial, even for networks, Centerpoints: A Link between Optimization and Convex Geometry, 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, Parameterized Traveling Salesman Problem: Beating the Average, A branch-and-cut algorithm for the maximum cardinality stable set problem, Vertex deletion into bipartite permutation graphs, On project scheduling with irregular starting time costs, The maximum residual flow problem: NP‐hardness with two‐arc destruction, Discrete relaxations of combinatorial programs, The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem, A lower bound for the shortest path problem, Rearrangement of DNA fragments: a branch-and-cut algorithm., Optimal oblivious routing in polynomial time, On describing the routing capacity regions of networks, Discrete convexity and polynomial solvability in minimum 0-extension problems, Distributionally robust chance constraints for non-linear uncertainties, A characterization of the weighted Lovász number based on convex quadratic programming, Maximum bipartite matchings with low rank data: locality and perturbation analysis, On the \(d\)-claw vertex deletion problem, Sparse Approximate Solutions to Semidefinite Programs, A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant, Constant factor approximation for tracking paths and fault tolerant feedback vertex set, Linear programming using limited-precision oracles, Computing the nucleolus of weighted cooperative matching games in polynomial time, Constant factor approximation for tracking paths and fault tolerant feedback vertex set, The multiroute maximum flow problem revisited, Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation, MAX k‐CUT and approximating the chromatic number of random graphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Graphs and Algorithms in Communication Networks on Seven League Boots, Deterministic Construction of an Approximate M-Ellipsoid and its Application to Derandomizing Lattice Algorithms, Book Review: The basic George B. Dantzig, A Polyhedral Frobenius Theorem with Applications to Integer Optimization, Acceleration of cutting-plane and column generation algorithms: Applications to network design, On the Stable Set Polytope of Claw-Free Graphs, Firefighting as a Strategic Game, The Computational Complexity of Understanding Binary Classifier Decisions, Approximation algorithm for the group Steiner network problem, Unnamed Item, Unnamed Item, 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, On determining the imperfection ratio, On facets of stable set polytopes of claw-free graphs with stability number three, Distributed Distance-Bounded Network Design Through Distributed Convex Programming, Weighted Triangle-Free 2-Matching Problem with Edge-Disjoint Forbidden Triangles, Constructing Lattice-Free Gradient Polyhedra in Dimension Two, Approximation algorithms for the covering Steiner problem, Complexity and Polynomially Solvable Special Cases of QUBO, The Boolean Quadric Polytope, Mathematical Programming Models and Exact Algorithms, The Random QUBO, Polynomial Time Reachability Analysis in Discrete State Chemical Reaction Networks Obeying Conservation Laws, SOS Is Not Obviously Automatizable, Even Approximately, Eternal domination and clique covering, Non-interfering network flows, Odd Multiway Cut in Directed Acyclic Graphs, The cut cone,L1 embeddability, complexity, and multicommodity flows, A Derivation of Lovász' Theta via Augmented Lagrange Duality, Coloration de graphes : fondements et applications, Enumerating Integer Points in Polytopes with Bounded Subdeterminants, Testing Consumer Rationality Using Perfect Graphs and Oriented Discs, Packing cuts in undirected graphs, Random walks in a convex body and an improved volume algorithm, Minimal volume ellipsoids, Simultaneously dominating all spanning trees of a graph, On the Lovász Theta Function for Independent Sets in Sparse Graphs, The Maximum k-Colorable Subgraph Problem and Related Problems, Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming, A pseudopolynomial network flow formulation for exact knapsack separation, Statistical Query Algorithms for Mean Vector Estimation and Stochastic Convex Optimization, A $\frac{4}{3}$-Approximation Algorithm for the Minimum 2-Edge Connected Multisubgraph Problem in the Half-Integral Case, $t$-Perfection in $P_5$-Free Graphs, Nonlinear formulations and improved randomized approximation algorithms for multicut problems, Polyhedra and optimization in connection with a weak majorization ordering, Computing Optimized Path Integrals for Knapsack Feasibility, The Computational Complexity of Integer Programming with Alternations, Easily Testable Graph Properties, Query Complexity of Sampling and Small Geometric Partitions, ISOLATED SCATTERING NUMBER OF SPLIT GRAPHS AND GRAPH PRODUCTS, Lattice complete graphs, Unnamed Item, Bandits with Global Convex Constraints and Objective, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, The Complexity of Valued CSPs, The computational complexity of graph problems with succinct multigraph representation, Two-dimensional translation-invariant probability distributions: approximations, characterizations and no-go theorems, The Alcuin Number of a Graph, Robust Estimators in High-Dimensions Without the Computational Intractability, A guide to conic optimisation and its applications, Approximating Unique Games Using Low Diameter Graph Decomposition, Unnamed Item, Test sets and inequalities for integer programs, Cone-LP's and semidefinite programs: Geometry and a simplex-type method, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, Transitive packing, Interior Point Methods for Nonlinear Optimization, Approximation algorithms for finding low-degree subgraphs, A Comparison of Certain Representations of Regularly Closed Sets, Hardness of robust network design, Channel assignment and weighted coloring, Approximating maximum independent sets by excluding subgraphs, Network Design with Weighted Degree Constraints, A Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors, Unnamed Item, Geometric Rescaling Algorithms for Submodular Function Minimization, New results for recognizing convex-QP adverse graphs, Simpler and Better Algorithms for Minimum-Norm Load Balancing, Analysis of LP relaxations for multiway and multicut problems, Traveling Salesman Problem and Membership in Pedigree Polytope - A Numerical Illustration, The Minimum Euclidean-Norm Point in a Convex Polytope: Wolfe's Combinatorial Algorithm is Exponential, Approximation schemes for ordered vector packing problems, Testing the Complexity of a Valued CSP Language, Dispersing Obnoxious Facilities on a Graph, Packing algorithms for arborescences (and spanning trees) in capacitated graphs, The 2-path network problem, Algorithms for a network design problem with crossing supermodular demands, The problem of quantum correlations and the totalitarian principle, Exact and approximative algorithms for coloring G(n,p), Counting Weighted Independent Sets beyond the Permanent, Algorithmic Bayesian Persuasion, Reconfiguration of Colorable Sets in Classes of Perfect Graphs, Combinatorial Optimization: The Interplay of Graph Theory, Linear and Integer Programming Illustrated on Network Flow, On the complexity of the chip-firing reachability problem, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, 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, Unnamed Item
