- Tight Bounds for Approximate Minimum Cuts in Insertion-Only Streaming Model
- Project Year:
2023
- REU Student (s):
Alexandro Garces | Massachusetts Institute of Technology MA
- Student 1 Institution:
Massachusetts Institute of Technology
- Project Mentor:
Sepehr Assadi
- Project Mentor Area:
Computer Science
- Project Abstract:
Finding the minimum cut of a graph has been studied extensively on its own as a fundamental graph problem and as a tool for understanding other important problems such as connectivity and network flow. We studied the minimum-cut problem in the insertion-only semi-streaming model, where edges of G are received one at a time in an input stream and space usage is confined to Õ(n) = O(n poly log n) bits. As such, we can't afford to store the entire graph at once, so we are forced to compute an approximation to the minimum cut. We present improved upper bound and lower bound results for the (1+ε)- approximation to the minimum cut problem in the insertion-only semi-streaming model. We achieve new results that are optimal in their dependence on ε.
