2 papers
cs.DS2026
Single-Pass Streaming CSPs via Two-Tier Sampling
Amir Azarmehr, Soheil Behnezhad, Shane Ferrante
We study the maximum constraint satisfaction problem, Max-CSP, in the streaming setting. Given variables, the constraints arrive sequentially in an arbitrary order, with each c…
cs.DS2026
Half-Approximating Maximum Dicut in the Streaming Setting
Amir Azarmehr, Soheil Behnezhad, Shane Ferrante +1
We study streaming algorithms for the maximum directed cut problem. The edges of an -vertex directed graph arrive one by one in an arbitrary order, and the goal is to estimate t…