The design of approximation algorithms
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Semidefinite programming (90C22) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Abstract computational complexity for mathematical programming problems (90C60)
Recommendations
Cited in
(only showing first 100 items - show all)- Using Approximation Algorithms to Build Evidence Factors and Related Designs for Observational Studies
- 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
- 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 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
- 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
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)
