3 papers
cs.DS2025
Budget and Profit Approximations for Spanning Tree Interdiction
Rafail Ostrovsky, Yuval Rabani, Yoav Siman Tov
We give polynomial time logarithmic approximation guarantees for the budget minimization, as well as for the profit maximization versions of minimum spanning tree interdiction. In…
cs.LG2023
Identification of Mixtures of Discrete Product Distributions in Near-Optimal Sample and Time Complexity
Spencer L. Gordon, Erik Jahn, Bijan Mazaheri +2
We consider the problem of identifying, from statistics, a distribution of discrete random variables that is a mixture of product distributions. The best previ…
cs.DS2012
A Constant Factor Approximation Algorithm for Reordering Buffer Management
Noa Avigdor-Elgrabli, Yuval Rabani
In the reordering buffer management problem (RBM) a sequence of colored items enters a buffer with limited capacity . When the buffer is full, one item is removed to the out…