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

DOI10.1287/MOOR.2021.1181zbMATH Open1492.68142OpenAlexW3215027038MaRDI QIDQ5085153FDOQ5085153

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

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

zbMATH Keywords

approximation algorithmssubmodularitynetwork design

Mathematics Subject Classification ID

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

Cites Work

• Approximating the weight of shallow Steiner trees
• Relationships between nondeterministic and deterministic tape complexities
• The polymatroid Steiner problems
• A greedy approximation algorithm for the group Steiner problem
• Polylogarithmic inapproximability
• A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
• Title not available (Why is that?)
• Approximation Algorithms for Directed Steiner Problems
• Tighter Bounds for Graph Steiner Tree Approximation
• Steiner tree approximation via iterative randomized rounding
• Optimum branchings
• A series of approximation algorithms for the acyclic directed Steiner tree problem
• Title not available (Why is that?)
• Cost-Distance: Two Metric Network Design
• Saving an epsilon: a 2-approximation for the \(k\)-MST problem in graphs
• 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
• Approximating \(k\)-hop minimum-spanning trees
• Approximation algorithms for nonuniform buy-at-bulk network design
• Approximating directed buy-at-bulk network design
• Improved algorithms for orienteering and related problems
• The directed orienteering problem
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Linear Programming Hierarchies Suffice for Directed Steiner Tree
• On the approximability of some network design problems
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• \(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)