Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems

DOI10.1287/moor.2021.1181zbMath1492.68142OpenAlexW3215027038MaRDI QIDQ5085153

Rohan Ghuge, Viswanath Nagarajan

Publication date: 27 June 2022

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.2021.1181

zbMATH Keywords

submodularitynetwork designapproximation algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• The directed orienteering problem
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Approximating the weight of shallow Steiner trees
• Approximating \(k\)-hop minimum-spanning trees
• Relationships between nondeterministic and deterministic tape complexities
• The polymatroid Steiner problems
• A greedy approximation algorithm for the group Steiner problem
• Approximation Algorithms for Nonuniform Buy-at-Bulk Network Design
• Approximating Directed Buy-at-Bulk Network Design
• Improved algorithms for orienteering and related problems
• Cost-Distance: Two Metric Network Design
• Polylogarithmic inapproximability
• Saving an epsilon
• A Constant Factor Approximation for the Single Sink Edge Installation Problem
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Approximation Algorithms for Directed Steiner Problems
• On the approximability of some network design problems
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• O (log ² k / log log k )-approximation algorithm for directed Steiner tree
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner Tree Approximation via Iterative Randomized Rounding
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• Optimum branchings

This page was built for publication: Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems