Geometric algorithms and combinatorial optimization
From MaRDI portal
Publication:1210712
zbMath0634.05001MaRDI QIDQ1210712
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 (only showing first 100 items - show all)
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
This page was built for publication: Geometric algorithms and combinatorial optimization
