2026-08-10T22:31:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22674 2026-04-17T05:32:09Z ddc:004 open_access

Data-Driven Solution Portfolios Drygala, Marina Lattanzi, Silvio Maggiori, Andreas Stouras, Miltiadis Svensson, Ola Vassilvitskii, Sergei solution portfolios data-driven algorithm design matroids 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 𝒱 over the solutions of Π, and a distribution 𝒟 over 𝒱, our goal is to select k solutions of Π that maximize or minimize the expected value of the 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marina Drygala and Silvio Lattanzi and Andreas Maggiori and Miltiadis Stouras and Ola Svensson and Sergei Vassilvitskii 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.46 urn:nbn:de:0030-drops-226740 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.46 eng https://creativecommons.org/licenses/by/4.0/legalcode