The Design of Approximation Algorithms
From MaRDI portal
Publication:3010438
DOI10.1017/CBO9780511921735zbMath1219.90004OpenAlexW4205585032MaRDI QIDQ3010438
David B. Shmoys, David P. Williamson
Publication date: 1 July 2011
Full work available at URL: https://doi.org/10.1017/cbo9780511921735
Semidefinite programming (90C22) Abstract computational complexity for mathematical programming problems (90C60) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Related Items (only showing first 100 items - show all)
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Combinatorial approximation algorithms for the robust facility location problem with penalties ⋮ A simple greedy approximation algorithm for the minimum connected \(k\)-center problem ⋮ How to catch marathon cheaters: new approximation algorithms for tracking paths ⋮ Theoretical complexity of grid cover problems used in radar applications ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ Provable randomized rounding for minimum-similarity diversification ⋮ Online unit clustering and unit covering in higher dimensions ⋮ Bin packing with divisible item sizes and rejection penalties ⋮ The limit of targeting in networks ⋮ Integrality gaps for strengthened linear relaxations of capacitated facility location ⋮ Scheduling arc shut downs in a network to maximize flow over time with a bounded number of jobs per time period ⋮ On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ A stochastic approach to handle resource constraints as knapsack problems in ensemble pruning ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ The two-stripe symmetric circulant TSP is in P ⋮ Bifactor approximation for location routing with vehicle and facility capacities ⋮ Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ Group parking permit problems ⋮ Knapsack with variable weights satisfying linear constraints ⋮ Parameterized approximation via fidelity preserving transformations ⋮ An introduction to the Ribe program ⋮ The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm ⋮ Strong LP formulations for scheduling splittable jobs on unrelated machines ⋮ Centrality of trees for capacitated \(k\)-center ⋮ Mean estimation with sub-Gaussian rates in polynomial time ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ On the approximability and hardness of minimum topic connected overlay and its special instances ⋮ Approximation schemes for parallel machine scheduling with non-renewable resources ⋮ An approximation algorithm for the \(k\)-prize-collecting multicut on a tree problem ⋮ Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem ⋮ Additive approximation algorithms for modularity maximization ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ Recommending links through influence maximization ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs ⋮ Local search algorithms for multiple-depot vehicle routing and for multiple traveling salesman problems with proved performance guarantees ⋮ Decomposition algorithms for data placement problem based on Lagrangian relaxation and randomized rounding ⋮ The parameterized complexity of the rainbow subgraph problem ⋮ Quell ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ Disruption recovery at airports: integer programming formulations and polynomial time algorithms ⋮ Approximation schemes for the generalized traveling salesman problem ⋮ Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming ⋮ Improved approximation algorithms for the maximum happy vertices and edges problems ⋮ An improved approximation algorithm for knapsack median using sparsification ⋮ On the complexity of wafer-to-wafer integration ⋮ Reference points and approximation algorithms in multicriteria discrete optimization ⋮ An approximation algorithm for a competitive facility location problem with network effects ⋮ Partitioned EDF scheduling on a few types of unrelated multiprocessors ⋮ Improved bounds in stochastic matching and optimization ⋮ Tightness of the maximum likelihood semidefinite relaxation for angular synchronization ⋮ Optimization with uniform size queries ⋮ A new approach to low-distortion embeddings of finite metric spaces into non-superreflexive Banach spaces ⋮ Hardness results for approximate pure Horn CNF formulae minimization ⋮ Geometric and LP-based heuristics for angular travelling salesman problems in the plane ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs ⋮ Optimizing node infiltrations in complex networks by a local search based heuristic ⋮ Local search approximation algorithms for the sum of squares facility location problems ⋮ Minimum constellation covers: hardness, approximability and polynomial cases ⋮ Constant-factor approximations for capacitated arc routing without triangle inequality ⋮ A continuous knapsack problem with separable convex utilities: approximation algorithms and applications ⋮ The A priori traveling repairman problem ⋮ On the approximability of the two-phase knapsack problem ⋮ Approximation of Steiner forest via the bidirected cut relaxation ⋮ Approximability of clique transversal in perfect graphs ⋮ Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ Approximation of the double traveling salesman problem with multiple stacks ⋮ Dichotomous binary differential evolution for knapsack problems ⋮ \(\text{PSPIKE}+\): A family of parallel hybrid sparse linear system solvers ⋮ On approximations for constructing 1-line minimum rectilinear Steiner trees in the Euclidean plane \(\mathbb{R}^2\) ⋮ Search complexity: a way for the quantitative analysis of the search space ⋮ Using Approximation Algorithms to Build Evidence Factors and Related Designs for Observational Studies ⋮ Approximation algorithms for the connected sensor cover problem ⋮ On the maximum betweenness improvement problem ⋮ Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ Constant factor approximation for ATSP with two edge weights ⋮ Real-time solving of computationally hard problems using optimal algorithm portfolios ⋮ On sparse reflexive generalized inverse ⋮ Assortment optimization under the multinomial logit model with product synergies ⋮ A simple algorithm for the multiway cut problem ⋮ Approximate algorithms for unrelated machine scheduling to minimize makespan ⋮ Disruption recovery at airports: ground holding, curfew restrictions and an approximation algorithm ⋮ Computing in combinatorial optimization ⋮ A simple rounding scheme for multistage optimization ⋮ A literature review on correlation clustering: cross-disciplinary taxonomy with bibliometric analysis ⋮ An approximation algorithm for a general class of multi-parametric optimization problems ⋮ An approximation algorithm for the maximum spectral subgraph problem ⋮ \(1\)-line minimum rectilinear Steiner trees and related problems ⋮ On the complexity of approximately matching a string to a directed graph ⋮ Weighted completion time minimization for capacitated parallel machines ⋮ Finding colorful paths in temporal graphs ⋮ MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms ⋮ Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds ⋮ Learning residual alternating automata ⋮ LP-based algorithms for multistage minimization problems
This page was built for publication: The Design of Approximation Algorithms
