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
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, 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, Sorting on graphs by adjacent swaps using permutation groups, 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, Unnamed Item, 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, Parameterized Power Vertex Cover, The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Constant Factor Approximation for ATSP with Two Edge Weights, Approximation-Friendly Discrepancy Rounding, Improving the Betweenness Centrality of a Node by Adding Links, Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation, DISTORTION IN THE FINITE DETERMINATION RESULT FOR EMBEDDINGS OF LOCALLY FINITE METRIC SPACES INTO BANACH SPACES, Approximation and Exact Algorithms for Special Cases of Connected f-Factors, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, Efficient continuous contraflow algorithms for evacuation planning problems, Approximation and online algorithms for multidimensional bin packing: a survey, A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem, Approximation Methods for Multiobjective Optimization Problems: A Survey, Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments, The matroid intersection cover problem, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, A Region Growing Algorithm for Detecting Critical Nodes, A parallel randomized approximation algorithm for non-preemptive single machine scheduling with release dates and delivery times, Unnamed Item, The Parameterized Complexity of the Rainbow Subgraph Problem, Network Creation Games: Think Global – Act Local, The complexity of comparing optimal solutions, On the Complexity of Wafer-to-Wafer Integration, On embeddings of locally finite metric spaces into \(\ell_p\), Approximate separable multichoice optimization over monotone systems, Geometric Packing under Nonuniform Constraints, On the tractability of finding disjoint clubs in a network, Technical Note—The Multinomial Logit Model with Sequential Offerings: Algorithmic Frameworks for Product Recommendation Displays, Benchmarking the quantum approximate optimization algorithm, 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, 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, From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More, On Integral Policies in Deterministic and Stochastic Distribution Systems, Finding Points in General Position, Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms, LP-Based Algorithms for Capacitated Facility Location, Sublinear-space approximation algorithms for Max \(r\)-SAT, Fractals for Kernelization Lower Bounds, 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, On the \(k\)-edge-incident subgraph problem and its variants, A 2/3-Approximation Algorithm for Vertex Weighted Matching in Bipartite Graphs, A note on the extension complexity of the knapsack polytope, A Local-Search Algorithm for Steiner Forest, A Quasi-Polynomial Approximation for the Restricted Assignment Problem, On Approximation Algorithms for Two-Stage Scheduling Problems, Learning in Combinatorial Optimization: What and How to Explore, Approximation algorithm for partial set multicover versus full set multicover, Batching-Based Approaches for Optimized Packing of Jobs in the Spatial Scheduling Problem, Submodular Cost Allocation Problem and Applications, Unnamed Item, Unnamed Item, Analysis of Solution Quality of a Multiobjective Optimization-Based Evolutionary Algorithm for Knapsack Problem, Graph Stabilization: A Survey, Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem, 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, A Lottery Model for Center-Type Problems With Outliers, 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, New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs, 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, On scheduling inclined jobs on multiple two-stage flowshops, Lazy Local Search Meets Machine Scheduling, Set cover problems with small neighborhood covers, Computing (and Life) Is All about Tradeoffs, The Parameterized Hardness of the k-Center Problem in Transportation Networks, Basic Terminology, Notation and Results, Approximate 1-Norm Minimization and Minimum-Rank Structured Sparsity for Various Generalized Inverses via Local Search, 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, An Improved Approximation Algorithm for the Matching Augmentation Problem, 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, Approximation algorithms for Steiner forest: An experimental study, A multiobjective approach for maximizing the reach or GRP of different brands in TV advertising, 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, Research trends in combinatorial optimization, 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, Polyhedral techniques in combinatorial optimization: matchings and tours, Complexity results on cosecure domination in graphs, Model-Based Deep Learning, Unified Greedy Approximability beyond Submodular Maximization, Faster distance-based representative skyline and \(k\)-center along Pareto front in the plane, Unnamed Item, Unified greedy approximability beyond submodular maximization, Approximation algorithms with constant factors for a series of asymmetric routing problems, Ordered scheduling in control-flow distributed transactional memory, Algorithms and hardness results for edge total domination problem in graphs, Unnamed Item, Unnamed Item, Computation in Causal Graphs, Unnamed Item, On the Facility Location Problem in Online and Dynamic Models., 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, The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg, Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices, Unnamed Item, Unnamed Item, A 2-approximation for the \(k\)-prize-collecting Steiner tree problem, Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
