2 papers
cs.DS2026
Unit Interval Selection in Random Order Streams
Cezar-Mihail Alexandru, Adithya Diddapur, Magnús M. Halldórsson +2
We consider the \textsf{Unit Interval Selection} problem in the one-pass random order streaming model. Here, an algorithm is presented a sequence of unit-length intervals on th…
cs.DS2025
Semi-Robust Communication Complexity of Maximum Matching
Gabriel Cipriani Huete, Adithya Diddapur, Pavel DvoÅák +1
We study the one-way two-party communication complexity of Maximum Matching in the semi-robust setting where the edges of a maximum matching are randomly partitioned between Alice…