The Design of Approximation Algorithms
From MaRDI portal
Publication:3010438
DOI10.1017/CBO9780511921735zbMath1219.90004MaRDI QIDQ3010438
David B. Shmoys, David P. Williamson
Publication date: 1 July 2011
Full work available at URL: https://doi.org/10.1017/cbo9780511921735
computational complexity; approximation methods; semidefinite programming; combinatorial optimization
90C22: Semidefinite programming
90C60: Abstract computational complexity for mathematical programming problems
90C59: Approximation methods and heuristics in mathematical programming
90C27: Combinatorial optimization
90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
Related Items
Improving the Betweenness Centrality of a Node by Adding Links, DISTORTION IN THE FINITE DETERMINATION RESULT FOR EMBEDDINGS OF LOCALLY FINITE METRIC SPACES INTO BANACH SPACES, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, Geometric Packing under Nonuniform Constraints, On Integral Policies in Deterministic and Stochastic Distribution Systems, Finding Points in General Position, Fractals for Kernelization Lower Bounds, A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs, On Approximation Algorithms for Two-Stage Scheduling Problems, Approximation algorithm for partial set multicover versus full set multicover, Batching-Based Approaches for Optimized Packing of Jobs in the Spatial Scheduling Problem, Graph Stabilization: A Survey, Unnamed Item, Unnamed Item, A Lottery Model for Center-Type Problems With Outliers, Approximate 1-Norm Minimization and Minimum-Rank Structured Sparsity for Various Generalized Inverses via Local Search, Assortment Optimization and Pricing Under the Multinomial Logit Model with Impatient Customers: Sequential Recommendation and Selection, An improved primal-dual approximation algorithm for the k-means problem with penalties, An Optimal Control Framework for Online Job Scheduling with General Cost Functions, A Water-Filling Primal-Dual Algorithm for Approximating NonLinear Covering Problems, A survey of graph burning, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, Approximation Methods for Multiobjective Optimization Problems: A Survey, Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments, Unnamed Item, Technical Note—The Multinomial Logit Model with Sequential Offerings: Algorithmic Frameworks for Product Recommendation Displays, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms, Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, On Sparse Discretization for Graphical Games, Assortment Optimization Under the Paired Combinatorial Logit Model, A Local-Search Algorithm for Steiner Forest, A Quasi-Polynomial Approximation for the Restricted Assignment Problem, Learning in Combinatorial Optimization: What and How to Explore, Analysis of Solution Quality of a Multiobjective Optimization-Based Evolutionary Algorithm for Knapsack Problem, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm, Distributed set cover approximation: Primal-dual with optimal locality, A super-quadratic lower bound for depth four arithmetic circuits, Game efficiency through linear programming duality, Approximation algorithms in combinatorial scientific computing, Lazy Local Search Meets Machine Scheduling, The Parameterized Hardness of the k-Center Problem in Transportation Networks, Mixed integer programming with convex/concave constraints: fixed-parameter tractability and applications to multicovering and voting, Problems on track runners, On the shortest separating cycle, On scheduling inclined jobs on multiple two-stage flowshops, Set cover problems with small neighborhood covers, Multi-dimensional vector assignment problems, Approximating minimum-cost connected \(T\)-joins, Balanced partitions of trees and applications, Approximability and parameterized complexity of multicover by \(c\)-intervals, Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties, The tight absolute bound of First Fit in the parameterized case, Sorting on graphs by adjacent swaps using permutation groups, Efficient continuous contraflow algorithms for evacuation planning problems, Approximation and online algorithms for multidimensional bin packing: a survey, On embeddings of locally finite metric spaces into \(\ell_p\), On the tractability of finding disjoint clubs in a network, Approximation algorithms for the graph balancing problem with two speeds and two job lengths, Vertex cover in conflict graphs, Blessing of massive scale: spatial graphical model estimation with a total cardinality constraint approach, On the \(k\)-edge-incident subgraph problem and its variants, A note on the extension complexity of the knapsack polytope, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, The matroid intersection cover problem, A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times, The complexity of comparing optimal solutions, Approximate separable multichoice optimization over monotone systems, Benchmarking the quantum approximate optimization algorithm, Statistical matching and subclassification with a continuous dose: characterization, algorithm, and application to a health outcomes study, Nearly tight bounds on the price of explainability for the \(k\)-center and the maximum-spacing clustering problems, Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours, An approximation algorithm for \(P\)-prize-collecting set cover problem, Fractional decomposition tree algorithm: a tool for studying the integrality gap of integer programs, Sublinear-space approximation algorithms for Max \(r\)-SAT, Nonoblivious 2-Opt heuristics for the traveling salesman problem, Better Bin Packing Approximations via Discrepancy Theory, Balls and Funnels: Energy Efficient Group-to-Group Anycasts, New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs, Computing (and Life) Is All about Tradeoffs, A Region Growing Algorithm for Detecting Critical Nodes, The Parameterized Complexity of the Rainbow Subgraph Problem, Network Creation Games: Think Global – Act Local, On the Complexity of Wafer-to-Wafer Integration, LP-Based Algorithms for Capacitated Facility Location, Submodular Cost Allocation Problem and Applications, Basic Terminology, Notation and Results, Unnamed Item, Parameterized Power Vertex Cover, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Constant Factor Approximation for ATSP with Two Edge Weights, Approximation-Friendly Discrepancy Rounding, Approximation and Exact Algorithms for Special Cases of Connected f-Factors, Towards Tight Lower Bounds for Scheduling Problems, An Improved Approximation Algorithm for Knapsack Median Using Sparsification, Welfare Maximization with Deferred Acceptance Auctions in Reallocation Problems, Routing Under Uncertainty: The a priori Traveling Repairman Problem, The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online, Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation, Using Approximation Algorithms to Build Evidence Factors and Related Designs for Observational Studies, Combinatorial approximation algorithms for the robust facility location problem with penalties, A simple greedy approximation algorithm for the minimum connected \(k\)-center problem, Approximation algorithms for stochastic combinatorial optimization problems, 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, Towards duality of multicommodity multiroute cuts and flows: multilevel ball-growing, On the approximability and hardness of minimum topic connected overlay and its special instances, 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, Quell, 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, Fixed-parameter approximations for \(k\)-center problems in low highway dimension graphs, The A priori traveling repairman problem, Approximability of clique transversal in perfect graphs, A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem, \(\text{PSPIKE}+\): A family of parallel hybrid sparse linear system solvers, On the maximum betweenness improvement problem, Approximate algorithms for unrelated machine scheduling to minimize makespan, How to catch marathon cheaters: new approximation algorithms for tracking paths, Strong LP formulations for scheduling splittable jobs on unrelated machines, Centrality of trees for capacitated \(k\)-center, A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, Theoretical complexity of grid cover problems used in radar applications, Knapsack with variable weights satisfying linear constraints, Parameterized approximation via fidelity preserving transformations, Approximation schemes for parallel machine scheduling with non-renewable resources, Approximating bounded-degree spanning trees and connected factors with leaves, Recommending links through influence maximization, The parameterized complexity of the rainbow subgraph problem, 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, Improved bounds in stochastic matching and optimization, Constant-factor approximations for capacitated arc routing without triangle inequality, A continuous knapsack problem with separable convex utilities: approximation algorithms and applications, Dichotomous binary differential evolution for knapsack problems, Semidefinite and linear programming integrality gaps for scheduling identical machines, Constant factor approximation for ATSP with two edge weights, An introduction to the Ribe program, 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, Minimum constellation covers: hardness, approximability and polynomial cases, Approximation of the double traveling salesman problem with multiple stacks, 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, Real-time solving of computationally hard problems using optimal algorithm portfolios, 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, 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, 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, The parameterized hardness of the \(k\)-center problem in transportation networks, Group parking permit problems, The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm, Mean estimation with sub-Gaussian rates in polynomial time, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, 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, On the cycle augmentation problem: hardness and approximation algorithms, Partitioned EDF scheduling on a few types of unrelated multiprocessors, Hardness results for approximate pure Horn CNF formulae minimization, Optimizing node infiltrations in complex networks by a local search based heuristic, Local search approximation algorithms for the sum of squares facility location problems, On the approximability of the two-phase knapsack problem, Approximation of Steiner forest via the bidirected cut relaxation, Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem, Approximation algorithms for the connected sensor cover problem, Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem, On sparse reflexive generalized inverse, Assortment optimization under the multinomial logit model with product synergies, A simple algorithm for the multiway cut problem, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds, Computation in Causal Graphs, Unnamed Item, Unnamed Item, Unnamed Item, Approximating \(k\)-forest with resource augmentation: a primal-dual approach, The subset sum game revisited, Some graph optimization problems with weights satisfying linear constraints, Vertex deletion on split graphs: beyond 4-hitting set, Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments, Online unit covering in Euclidean space, An EPTAS for scheduling on unrelated machines of few different types, Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, A 2-approximation for the \(k\)-prize-collecting Steiner tree problem, An Improved Approximation Algorithm for the Matching Augmentation Problem, Unnamed Item, Unnamed Item, Unnamed Item, Generalized \(k\)-center: distinguishing doubling and highway dimension, Unconstrained traveling tournament problem is APX-complete, On the complexity of the cable-trench problem, Matheuristics: survey and synthesis, Building a small and informative phylogenetic supertree, Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties, Covering edges in networks, On a partition LP relaxation for min-cost 2-node connected spanning subgraphs, A parameterized approximation algorithm for the multiple allocation \(k\)-hub center, A fast approximation algorithm for the maximum 2-packing set problem on planar graphs, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, Complexity results on cosecure domination in graphs, Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane, Unified greedy approximability beyond submodular maximization, On the Facility Location Problem in Online and Dynamic Models.
