# The Price of Information in Combinatorial Optimization

arXiv: https://arxiv.org/abs/1711.00405 · HTML: https://mlsanity.com/paper/1711.00405/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2017.

## Built on by (most cited first, 12 of 12)

- [Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index](https://mlsanity.com/paper/2406.20062/) (2024)
- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization](https://mlsanity.com/paper/2505.21692/) (2025)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [The Gittins Index: A Design Principle for Decision-Making Under Uncertainty](https://mlsanity.com/paper/2506.10872/) (2025)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality](https://mlsanity.com/paper/2505.18828/) (2025)
- [Approximating Pandora's Box with Correlations](https://mlsanity.com/paper/2108.12976/) (2021)
- [Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error](https://mlsanity.com/paper/2509.22023/) (2025)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)

## Abstract (arXiv)

Consider a network design application where we wish to lay down a minimum-cost spanning tree in a given graph; however, we only have stochastic information about the edge costs. To learn the precise cost of any edge, we have to conduct a study that incurs a price. Our goal is to find a spanning tree while minimizing the disutility, which is the sum of the tree cost and the total price that we spend on the studies. In a different application, each edge gives a stochastic reward value. Our goal is to find a spanning tree while maximizing the utility, which is the tree reward minus the prices that we pay. Situations such as the above two often arise in practice where we wish to find a good solution to an optimization problem, but we start with only some partial knowledge about the parameters of the problem. The missing information can be found only after paying a probing price, which we call the price of information. What strategy should we adopt to optimize our expected utility/disutility? A classical example of the above setting is Weitzman's "Pandora's box" problem where we are given probability distributions on values of n independent random variables. The goal is to choose a single variable with a large value, but we can find the actual outcomes only after paying a price. Our work is a generalization of this model to other combinatorial optimization problems such as matching, set cover, facility location, and prize-collecting Steiner tree. We give a technique that reduces such problems to their non-price counterparts, and use it to design exact/approximation algorithms to optimize our utility/disutility. Our techniques extend to situations where there are additional constraints on what parameters can be probed or when we can simultaneously probe a subset of the parameters.