3 citations · 6 across the 10 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.DS2023
New Prophet Inequalities via Poissonization and Sharding
Elfarouk Harb
This work introduces \emph{sharding} and \emph{Poissonization} as a unified framework for analyzing prophet inequalities. Sharding involves splitting a random variable into several…
cs.DS2023
Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing
Elfarouk Harb, Kent Quanrud, Chandra Chekuri
Boob et al. [1] described an iterative peeling algorithm called Greedy++ for the Densest Subgraph Problem (DSG) and conjectured that it converges to an optimum solution. Chekuri, Q…