### Abstract

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 prac-tice where we wish to find a good solution to an optimiza-tion problem, but we start with only some partial knowledge about the parameters of the problem. The missing informa-tion 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 combi-natorial 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 al-gorithms 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 simulta-neously probe a subset of the parameters.

Original language | English (US) |
---|---|

Title of host publication | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |

Editors | Artur Czumaj |

Publisher | Association for Computing Machinery |

Pages | 2523-2532 |

Number of pages | 10 |

ISBN (Electronic) | 9781611975031 |

DOIs | |

State | Published - Jan 1 2018 |

Externally published | Yes |

Event | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 - New Orleans, United States Duration: Jan 7 2018 → Jan 10 2018 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018 |
---|---|

Country | United States |

City | New Orleans |

Period | 1/7/18 → 1/10/18 |

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'The price of information in combinatorial optimization'. Together they form a unique fingerprint.

## Cite this

*29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018*(pp. 2523-2532). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms). Association for Computing Machinery. https://doi.org/10.1137/1.9781611975031.161