4 papers
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…
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…
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…
Bounding the sum of the largest signless Laplacian eigenvalues of a graph
Aida Abiad, Leonardo de Lima, Sina Kalantarzadeh +2
We show several sharp upper and lower bounds for the sum of the largest eigenvalues of the signless Laplacian matrix. These bounds improve and extend previously known bounds.