The design of approximation algorithms
From MaRDI portal
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Semidefinite programming (90C22) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Abstract computational complexity for mathematical programming problems (90C60)
Recommendations
Cited in
(only showing first 100 items - show all)- Approximation algorithms for Steiner forest: An experimental study
- Design Is as Easy as Optimization
- Welfare maximization with deferred acceptance auctions in reallocation problems
- Travelling salesman paths on Demidenko matrices
- On the fine-grained parameterized complexity of partial scheduling to minimize the makespan
- Set cover problems with small neighborhood covers
- Vertex cover in conflict graphs
- On the complexity of winner determination and strategic control in conditional approval voting
- Approximation of the double traveling salesman problem with multiple stacks
- Complexity results on cosecure domination in graphs
- Parameterized complexity of incomplete connected fair division
- Assortment optimization under the paired combinatorial logit model
- Algorithms for scheduling deadline-sensitive malleable tasks
- On min-max graph balancing with strict negative correlation constraints
- Improved approximation algorithm for capacitated facility location with uniform facility cost
- Approximating bounded-degree spanning trees and connected factors with leaves
- Hardness of continuous local search: query complexity and cryptographic lower bounds
- Approximation algorithms for connected graph factors of minimum weight
- On the approximability of the two-phase knapsack problem
- The parameterized complexity of the rainbow subgraph problem
- Learning residual alternating automata
- How to catch marathon cheaters: new approximation algorithms for tracking paths
- The matroid intersection cover problem
- The parameterized complexity of the rainbow subgraph problem
- Better bin packing approximations via discrepancy theory
- A tight (1.5+)-approximation for unsplittable capacitated vehicle routing on trees
- Partitioning Vectors into Quadruples: Worst-Case Analysis of a Matching-Based Algorithm
- A super-quadratic lower bound for depth four arithmetic circuits
- Approximation algorithm for partial set multicover versus full set multicover
- Exact and approximate algorithms for discounted \(\{0\text{-}1\}\) knapsack problem
- Further results on the hunters and rabbit game through monotonicity
- Local search approximation algorithms for the sum of squares facility location problems
- Vertex Cover in Conflict Graphs: Complexity and a Near Optimal Approximation
- Recommending links through influence maximization
- Approximation algorithm for solving the 1-line Steiner tree problem with minimum number of Steiner points
- On sparse hitting sets: from fair vertex cover to highway dimension
- Addressing bias in algorithmic solutions: exploring vertex cover and feedback vertex set
- (In-)approximability results for interval, resource restricted, and low rank scheduling
- Geometric Packing under Nonuniform Constraints
- Greedy Algorithms for the Maximum Satisfiability Problem: Simple Algorithms and Inapproximability Bounds
- scientific article; zbMATH DE number 1566497 (Why is no real title available?)
- A fast approximation algorithm for the maximum 2-packing set problem on planar graphs
- Bounding the price-of-fair-sharing using knapsack-cover constraints to guide near-optimal cost-recovery algorithms
- Unified Greedy Approximability beyond Submodular Maximization
- Analysis of solution quality of a multiobjective optimization-based evolutionary algorithm for knapsack problem
- A note on the extension complexity of the knapsack polytope
- Design and analysis of approximation algorithms
- A simple algorithm for the multiway cut problem
- From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
- On the approximability and hardness of minimum topic connected overlay and its special instances
- Geometric and LP-based heuristics for angular travelling salesman problems in the plane
- A dual-index rule for managing temporary congestion
- On the shortest separating cycle
- The circular balancing problem
- Improved approximation algorithms for cycle and path packings
- Combinatorial algorithms for solving the constrained knapsack problems with divisible item sizes and penalties
- On the tractability of finding disjoint clubs in a network
- Combinatorial multi-armed bandits with fairness constraints: an online convex optimization perspective
- Mean estimation with sub-Gaussian rates in polynomial time
- Multidepot capacitated vehicle routing with improved approximation guarantees
- Combinatorial approximation algorithms for the robust facility location problem with penalties
- A simple greedy approximation algorithm for the minimum connected k-center problem
- The matching augmentation problem: a \(\frac{7}{4}\)-approximation algorithm
- Learning in combinatorial optimization: what and how to explore
- A survey of graph burning
- An improved primal-dual approximation algorithm for the k-means problem with penalties
- On the \(k\)-edge-incident subgraph problem and its variants
- Circulant TSP special cases: easily-solvable cases and improved approximations
- A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem
- A multiobjective approach for maximizing the reach or GRP of different brands in TV advertising
- On the complexity of the cable-trench problem
- A water-filling primal-dual algorithm for approximating nonlinear covering problems
- Disruption recovery at airports: integer programming formulations and polynomial time algorithms
- Parameterized Algorithms for Power-Efficiently Connecting Wireless Sensor Networks: Theory and Experiments
- A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
- Approximation and exact algorithms for special cases of connected f-factors
- Generalized \(k\)-center: distinguishing doubling and highway dimension
- On the Facility Location Problem in Online and Dynamic Models.
- Theoretical complexity of grid cover problems used in radar applications
- Online unit clustering and unit covering in higher dimensions
- Using randomized rounding of linear programs to obtain unweighted natural strata that balance many covariates
- Makespan minimization on unrelated parallel machines with simple job-intersection structure and bounded job assignments
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Approximation algorithms for stochastic combinatorial optimization problems
- Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming
- A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs
- Improved approximation algorithms by generalizing the primal-dual method beyond uncrossable functions
- A theoretical and empirical study of job scheduling in cloud computing environments: the weighted completion time minimization problem with capacitated parallel machines
- A deterministic approximation algorithm for metric triangle packing
- Improved approximation algorithms for multidepot capacitated vehicle routing
- An improved approximation algorithm for knapsack median using sparsification
- On the complexity of wafer-to-wafer integration
- An approximation algorithm for a competitive facility location problem with network effects
- On Approximation Algorithms for Two-Stage Scheduling Problems
- A parameterized approximation algorithm for the multiple allocation \(k\)-hub center
- Improved bounds in stochastic matching and optimization
- The power of deferral: maintaining a constant-competitive Steiner tree online
- scientific article; zbMATH DE number 7651222 (Why is no real title available?)
- Improved approximation algorithms for the maximum happy vertices and edges problems
- An improved approximation algorithm for metric triangle packing
This page was built for publication: The design of approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3010438)
