Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems

DOI10.1287/MOOR.2021.1181MaRDI QIDQ5085153zbMATH OpenOpenAlexFDO

Authors 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

approximation algorithmssubmodularitynetwork design

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1303557
• Approximation Algorithms for Directed Steiner Problems
• $O(\log^2{k}/\log\log{k})$-Approximation Algorithm for Directed Steiner Tree: A Tight Quasi-Polynomial Time Algorithm
• scientific article; zbMATH DE number 1342141
• A series of approximation algorithms for the acyclic directed Steiner tree problem

Cites work

• scientific article; zbMATH DE number 2119644 (Why is no real title available?)
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• A constant factor approximation for the single sink edge installation problem
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• A greedy approximation algorithm for the group Steiner problem
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Approximating \(k\)-hop minimum-spanning trees
• Approximating directed buy-at-bulk network design
• Approximating the weight of shallow Steiner trees
• Approximation Algorithms for Directed Steiner Problems
• Approximation algorithms for nonuniform buy-at-bulk network design
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Cost-Distance: Two Metric Network Design
• Improved algorithms for orienteering and related problems
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• On the approximability of some network design problems
• Optimum branchings
• Polylogarithmic inapproximability
• Relationships between nondeterministic and deterministic tape complexities
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• Steiner tree approximation via iterative randomized rounding
• The directed orienteering problem
• The polymatroid Steiner problems
• Tighter Bounds for Graph Steiner Tree Approximation
• Using Variable Redefinition for Computing Lower Bounds for Minimum Spanning and Steiner Trees with Hop Constraints
• \(O(\log^2 k/\log\log k)\)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm

Cited in

(1)

• A cubic algorithm for the directed Eulerian subgraph problem

This page was built for publication: Quasi-polynomial algorithms for submodular tree orienteering and directed network design problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5085153)