3 papers
cs.DS2026
Simple and Almost Non-Adaptive \(\frac{1}{2}\)-Approximation for Matroid Prophet Inequalities
Sina Kalantarzadeh, Kanstantin Pashkovich
Prophet inequalities are a fundamental model for online decision-making under uncertainty. For matroid constraints, Kleinberg and Weinberg gave a tight -approximation, but the…
cs.DM2025
Improved Lower Bounds on Multiflow-Multicut Gaps
Sina Kalantarzadeh, Nikhil Kumar
Given a set of source-sink pairs, the maximum multiflow problem asks for the maximum total amount of flow that can be feasibly routed between them. The minimum multicut, a dual pro…
cs.DS2025
A Randomized Rounding Approach for DAG Edge Deletion
Sina Kalantarzadeh, Nathan Klein, Victor Reis
In the DAG Edge Deletion problem, we are given an edge-weighted directed acyclic graph and a parameter , and the goal is to delete the minimum weight set of edges so that the re…