Iterative Methods in Combinatorial Optimization

DOI10.1017/CBO9780511977152zbMath1247.90002OpenAlexW2552451242MaRDI QIDQ3087101

Publication date: 2 August 2011

Full work available at URL: https://doi.org/10.1017/cbo9780511977152

Combinatorial optimization approximation algorithms

Combinatorial optimization (90C27) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming (90-01) Approximation algorithms (68W25)

Related Items (61)

An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ The recoverable robust spanning tree problem with interval costs is polynomially solvable ⋮ Bounded Degree Group Steiner Tree Problems ⋮ Approximation Limits of Linear Programs (Beyond Hierarchies) ⋮ Random Walks in Polytopes and Negative Dependence ⋮ Approximation Algorithms for Multi-budgeted Network Design Problems ⋮ k-Trails: Recognition, Complexity, and Approximations ⋮ Approximation-Friendly Discrepancy Rounding ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ On some network design problems with degree constraints ⋮ On the tree augmentation problem ⋮ Recoverable robust spanning tree problem under interval uncertainty representations ⋮ A Spectral Approach to Network Design ⋮ Unnamed Item ⋮ On fair covering and hitting problems ⋮ A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint ⋮ Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design ⋮ Proper orientations and proper chromatic number ⋮ Tight approximation algorithms for geometric bin packing with skewed items ⋮ Integrality gaps for colorful matchings ⋮ An iterative rounding 2-approximation algorithm for the \(k\)-partial vertex cover problem ⋮ Analyzing Residual Random Greedy for monotone submodular maximization ⋮ On colorful vertex and edge cover problems ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ Coupled and \(k\)-sided placements: generalizing generalized assignment ⋮ A unified algorithm for degree bounded survivable network design ⋮ Arboricity games: the core and the nucleolus ⋮ Resource management in device-to-device communications ⋮ Eigenpolytope Universality and Graphical Designs ⋮ Network bargaining: using approximate blocking sets to stabilize unstable instances ⋮ Discrepancy theory and related algorithms ⋮ Uniform s-Cross-Intersecting Families ⋮ Approximating Minimum Cost Connectivity Orientation and Augmentation ⋮ Approximating minimum cost source location problems with local vertex-connectivity demands ⋮ LP-relaxations for tree augmentation ⋮ Maximizing coverage while ensuring fairness: a tale of conflicting objectives ⋮ Assortment Optimization Under the Paired Combinatorial Logit Model ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ Approximating Unique Games Using Low Diameter Graph Decomposition ⋮ Degree constrained node-connectivity problems ⋮ A Lottery Model for Center-Type Problems with Outliers ⋮ Approximation and hardness of shift-Bribery ⋮ Complexity of some graph-based bounds on the probability of a union of events ⋮ On tree-constrained matchings and generalizations ⋮ Unnamed Item ⋮ ILP models for the allocation of recurrent workloads upon heterogeneous multiprocessors ⋮ Scheduling problems over a network of machines ⋮ Independent sets and hitting sets of bicolored rectangular families ⋮ Algorithms for hierarchical and semi-partitioned parallel scheduling ⋮ \(k\)-trails: recognition, complexity, and approximations ⋮ Unnamed Item ⋮ Approximate multi-matroid intersection via iterative refinement ⋮ Computing the nucleolus of weighted cooperative matching games in polynomial time ⋮ A Lottery Model for Center-Type Problems With Outliers ⋮ Upper and lower degree-constrained graph orientation with minimum penalty ⋮ The minimum degree group Steiner problem ⋮ Socially fair network design via iterative rounding ⋮ Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal ⋮ Unnamed Item ⋮ Nearly optimal robust secret sharing against rushing adversaries ⋮ Approximating minimum-cost connected \(T\)-joins

This page was built for publication: Iterative Methods in Combinatorial Optimization