The price of information in combinatorial optimization

MaRDI QIDQ4608056zbMATH OpenFDO

Authors Sahil Singla

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1711.00405, http://dl.acm.org/citation.cfm?id=3175466

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59) Economics of information (91B44)

Recommendations

• The Markovian price of information
• Sampling and cost-sharing: approximation algorithms for stochastic optimization problems
• A stochastic probing problem with applications
• Maximizing expected utility for stochastic combinatorial optimization problems
• Network design for information networks

Cited in

(29)

• Algorithms for the unit-cost stochastic score classification problem
• Explorable uncertainty in scheduling with non-uniform testing times
• An adversarial model for scheduling with testing
• The Markovian price of information
• Shadow price of information in discrete time stochastic optimization
• Online purchasing under uncertainty
• Optimal Information Gathering on the Internet with Time and Cost Constraints
• A PTAS for a class of stochastic dynamic programs
• Online allocation and pricing: constant regret via Bellman inequalities
• The stochastic score classification problem
• On the Global Optimality of Whittle’s Index Policy for Minimizing the Age of Information
• Stochastic graph exploration
• Query minimization under stochastic uncertainty
• On partial information retrieval: the unconstrained 100 prisoner problem
• Stochastic graph exploration with limited resources
• Stochastic Probing with Increasing Precision
• Pandora’s Box Problem with Order Constraints
• Pandora Box problem with nonobligatory inspection: hardness and approximation scheme
• Pandora's problem with nonobligatory inspection: optimal structure and a PTAS
• Pandora's box problem with time constraints
• Learning-augmented query policies for minimum spanning tree with uncertainty
• Toward a better understanding of randomized greedy matching
• Random order vertex arrival contention resolution schemes for matching, with applications
• Matching with nested and bundled Pandora boxes
• Pandora's box problem over time
• Designing exploration contracts
• Identifying approximate minimizers under stochastic uncertainity
• Scheduling with testing on multiple identical parallel machines
• Online makespan minimization with budgeted uncertainty

This page was built for publication: The price of information in combinatorial optimization

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