Processing graphs and intervals in the sliding window model

Abstract

In this thesis, we investigate how to process graphs and intervals in the sliding window
model. We will summarise the existing results in the research literature and explore some
widely used techniques for solving research questions in the sliding window model relating
to both graphs and intervals. Furthermore, as original contributions, we will study the
following problems in the sliding window model: Maximum Weighted Matching and Interval
Selection.
We provide the following results, which are presented in the works [ADKN23] and
[AK24]:
1. We improve upon the previous results of Maximum Weighted Matching in the sliding window model. Using O˜(n)
1
space, the best result for Maximum (Unweighted)
Matching computes a 3 + ε of the optimal matching, a result due to [CMS13]. Before our work, the state-of-the-art sliding-window algorithm for Maximum Weighted
Matching was a 3.5 + ε approximation factor due to [BdBM21] which employed
the vanilla smooth histogram method over the algorithm of Paz and Schwartzman
([PS17]). Applying smooth histogram on a different function (the sum of reduced
weights) and providing different analysis, we manage to improve this result and close
the approximation factor gap between weighted and unweighted matching (3 +ε approximation). While beating the 3 approximation using O˜(n) memory in the sliding
window model remains an open problem for both unweighted and weighted matching, we show that the approximation factor can be improved up to 2 + ε if we allow
more memory while still maintaining a nontrivial amount of memory (i.e., o(L)).
More specifically, O˜(
√
nL) memory is enough, where L is the window length. Furthermore, beyond our work in [ADKN23], we will show that we can maintain an
edge set of size O(k
2
) which contains a matching of size k in the sliding window
model using O(n + k
2
) memory and having a constant amortised update time.
2. We initiate the study of Interval Selection in the sliding window model. We will
give both algorithms and lower bounds for the warm-up case of unit-intervals (Unit
Interval Selection) and the general case of variable-length intervals (Interval Selection). The main technical contribution is an improvement over the vanilla smooth
histogram approach where local properties of instances are used to improve the approximation factor for Interval Selection while using O˜(|OP T|) space, where OP T is
the optimal solution. This work is notable since it provides one of the few memory
lower bounds for graph-theoretic problems in the sliding window model as Interval
Selection is equivalent to Maximum Independent Set on interval graphs.

1O(n) up to logarithmic factors

Date of Award	17 Jun 2025
Original language	English
Awarding Institution	University of Bristol
Sponsors	EPSRC College
Supervisor	Christian Konrad (Supervisor) & Raphael Clifford (Supervisor)