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