Data-Driven Solution Portfolios
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929609571827712 |
|---|---|
| author | Drygala, Marina Lattanzi, Silvio Maggiori, Andreas Stouras, Miltiadis Svensson, Ola Vassilvitskii, Sergei |
| author_facet | Drygala, Marina Lattanzi, Silvio Maggiori, Andreas Stouras, Miltiadis Svensson, Ola Vassilvitskii, Sergei |
| contents | In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select $k$ potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem $Π$, a set of value functions $V$ over the solutions of $Π$, and a distribution $D$ over $V$, our goal is to select $k$ solutions of $Π$ that maximize or minimize the expected value of the {\em best} of those solutions. For a simple example, consider the classic knapsack problem: given a universe of elements each with unit weight and a positive value, the task is to select $r$ elements maximizing the total value. Now suppose that each element's weight comes from a (known) distribution. How should we select $k$ different solutions so that one of them is likely to yield a high value?
In this work, we tackle this basic problem, and generalize it to the setting where the underlying set system forms a matroid. On the technical side, it is clear that the candidate solutions we select must be diverse and anti-correlated; however, it is not clear how to do so efficiently. Our main result is a polynomial-time algorithm that constructs a portfolio within a constant factor of the optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_00717 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Data-Driven Solution Portfolios Drygala, Marina Lattanzi, Silvio Maggiori, Andreas Stouras, Miltiadis Svensson, Ola Vassilvitskii, Sergei Data Structures and Algorithms In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select $k$ potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem $Π$, a set of value functions $V$ over the solutions of $Π$, and a distribution $D$ over $V$, our goal is to select $k$ solutions of $Π$ that maximize or minimize the expected value of the {\em best} of those solutions. For a simple example, consider the classic knapsack problem: given a universe of elements each with unit weight and a positive value, the task is to select $r$ elements maximizing the total value. Now suppose that each element's weight comes from a (known) distribution. How should we select $k$ different solutions so that one of them is likely to yield a high value? In this work, we tackle this basic problem, and generalize it to the setting where the underlying set system forms a matroid. On the technical side, it is clear that the candidate solutions we select must be diverse and anti-correlated; however, it is not clear how to do so efficiently. Our main result is a polynomial-time algorithm that constructs a portfolio within a constant factor of the optimal. |
| title | Data-Driven Solution Portfolios |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2412.00717 |