scientific article; zbMATH DE number 7278099

DOI10.4230/LIPIcs.FSTTCS.2017.27zbMath1491.68268arXiv1610.01058MaRDI QIDQ5136319

Viswanath Nagarajan, Alina Ene, Rishi Saket

Publication date: 25 November 2020

Full work available at URL: https://arxiv.org/abs/1610.01058

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

approximation algorithmsadaptivity gapstochastic TSP

Mathematics Subject Classification ID

Stochastic programming (90C15) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items

Non-adaptive stochastic score classification and explainable halfspace evaluation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum bipartite flow in networks with adaptive channel width
• When LP is the cure for your matching woes: improved bounds for stochastic matchings
• On the adaptivity gap of stochastic orienteering
• Improved analysis of the greedy algorithm for stochastic matching
• Adaptive submodular ranking
• Incremental medians via online bidding
• Minimum Latency Submodular Cover
• Scenario Submodular Cover
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Submodular Stochastic Probing on Matroids
• Improved algorithms for orienteering and related problems
• Improved Approximation Algorithms for Stochastic Matching
• Stochastic Covering and Adaptivity
• Saving an epsilon
• Approximating Matches Made in Heaven
• Adaptivity Gaps for Stochastic Probing: Submodular and XOS Functions
• A Stochastic Probing Problem with Applications
• Approximation Algorithms for Stochastic Submodular Set Cover with Applications to Boolean Function Evaluation and Min-Knapsack
• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering
• Multi-armed Bandits with Metric Switching Costs
• Improved Bounds in Stochastic Matching and Optimization
• Improvements and Generalizations of Stochastic Knapsack and Multi-Armed Bandit Approximation Algorithms: Extended Abstract
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• A General Approach for Incremental Approximation and Hierarchical Clustering
• Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits