Approximating \(k\)-forest with resource augmentation: a primal-dual approach
DOI10.1016/j.tcs.2018.11.029zbMath1423.68586arXiv1611.07489OpenAlexW2553394537WikidataQ128732286 ScholiaQ128732286MaRDI QIDQ5919564
Thang Nguyen Kim, Shikha Singh, Eric Angel
Publication date: 9 August 2019
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.07489
optimization problemsapproximation algorithmsprimal-dual algorithmsresource augmentation\(k\)-forest problemLP duality algorithmsprize-collecting generalized Steiner tree problem
Programming involving graphs or networks (90C35) Integer programming (90C10) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- A unified approach to approximating partial covering problems
- Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing
- A factor 2 approximation algorithm for the generalized Steiner network problem
- Approximation algorithms for combinatorial problems
- Competitive paging with locality of reference
- Propagation via lazy clause generation
- Primal-dual and dual-fitting analysis of online scheduling algorithms for generalized flow-time problems
- An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- Lagrangian Duality in Online Scheduling with Resource Augmentation and Speed Scaling
- Detecting high log-densities
- The Design of Approximation Algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Online Computation with Advice
- Bounds and Heuristics for Capacitated Routing Problems
- Improving the performance guarantee for approximate graph coloring
- New approximation algorithms for graph coloring
- On the hardness of approximating minimization problems
- Speed is as powerful as clairvoyance
- The Online Transportation Problem
- Beyond Competitive Analysis
- On-Line Paging Against Adversarially Biased Random Inputs
- Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality
- A General Approximation Technique for Constrained Forest Problems
- Greedily Finding a Dense Subgraph
- Competitive algorithms from competitive equilibria
- Rejecting jobs to Minimize Load and Maximum Flow-time
- Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms
- The Online Transportation Problem: On the Exponential Boost of One Extra Server
- Max flows in O(nm) time, or better
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- The dense \(k\)-subgraph problem
- Optimal time-critical scheduling via resource augmentation
This page was built for publication: Approximating \(k\)-forest with resource augmentation: a primal-dual approach
