Saving an epsilon
From MaRDI portal
Publication:3581401
DOI10.1145/1060590.1060650zbMath1192.05159OpenAlexW2038190710WikidataQ56474461 ScholiaQ56474461MaRDI QIDQ3581401
Publication date: 16 August 2010
Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1060590.1060650
Related Items (58)
Bounded Degree Group Steiner Tree Problems ⋮ Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination ⋮ Approximation and complexity of multi-target graph search and the Canadian traveler problem ⋮ Solving the traveling repairman problem on a line with general processing times and deadlines ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ Online network design with outliers ⋮ Approximation algorithms for inventory problems with submodular or routing costs ⋮ Two multi-start heuristics for the \(k\)-traveling salesman problem ⋮ A general approximation method for bicriteria minimization problems ⋮ Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems ⋮ Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems ⋮ On the Integrality Gap of the Prize-Collecting Steiner Forest LP ⋮ The Steiner tree in \(K_{1,r}\)-free split graphs -- a dichotomy ⋮ A simple approximation algorithm for minimum weight partial connected set cover ⋮ A 4-approximation algorithm for \(k\)-prize collecting Steiner tree problems ⋮ Thresholded covering algorithms for robust and max-min optimization ⋮ A 5-approximation algorithm for the \(k\)-prize-collecting Steiner tree problem ⋮ Improved approximation algorithms for directed Steiner forest ⋮ A unified approach to approximate partial, prize-collecting, and budgeted sweep cover problems ⋮ Pruning 2-connected graphs ⋮ Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem ⋮ Euclidean prize-collecting Steiner forest ⋮ A unified approach to approximating partial covering problems ⋮ Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems ⋮ Unnamed Item ⋮ Complexity and approximation for traveling salesman problems with profits ⋮ Approximation algorithm for minimizing total latency in machine scheduling with deliveries ⋮ Degree-constrained \(k\)-minimum spanning tree problem ⋮ Improved budgeted connected domination and budgeted edge-vertex domination ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Approximating the \(k\)-traveling repairman problem with repair times ⋮ Capacitated Vehicle Routing with Non-uniform Speeds ⋮ Virtual machine placement for minimizing connection cost in data center networks ⋮ The online prize-collecting traveling salesman problem ⋮ A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem ⋮ A new approximation algorithm for the selective single-sink buy-at-bulk problem in network design ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem ⋮ Complexity of Steiner Tree in Split Graphs - Dichotomy Results ⋮ Approximating node-weighted \(k\)-MST on planar graphs ⋮ Maximum rooted connected expansion ⋮ Improved approximations for buy-at-bulk and shallow-light \(k\)-Steiner trees and \((k,2)\)-subgraph ⋮ Approximation algorithms for minimum weight partial connected set cover problem ⋮ Approximation Algorithms for Generalized Bounded Tree Cover ⋮ Approximation algorithms for the connected sensor cover problem ⋮ An approximation algorithm to the \(k\)-Steiner forest problem ⋮ Analyzing the Optimal Neighborhood: Algorithms for Partial and Budgeted Connected Dominating Set Problems ⋮ An approximation algorithm for vehicle routing with compatibility constraints ⋮ Approximation algorithms for the partition vertex cover problem ⋮ Balls and Funnels: Energy Efficient Group-to-Group Anycasts ⋮ Approximating buy-at-bulk and shallow-light \(k\)-Steiner trees ⋮ A Constant Factor Approximation for Minimum λ-Edge-Connected k-Subgraph with Metric Costs ⋮ The minimum degree group Steiner problem ⋮ Approximating fault-tolerant group-Steiner problems ⋮ Unnamed Item ⋮ The power of the weighted sum scalarization for approximating multiobjective optimization problems ⋮ Prize-Collecting TSP with a Budget Constraint ⋮ A 2-approximation for the \(k\)-prize-collecting Steiner tree problem ⋮ Solving energy issues for sweep coverage in wireless sensor networks
This page was built for publication: Saving an epsilon
