5 papers
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Yinhao Dong, Pan Peng, Ali Vakilian +2
We study learning-augmented streaming algorithms for estimating the value of Boolean Maximum Constraint Satisfaction Problems (Max-CSPs). Specifically, we consider streaming algori…
Four-Cycle Counting in Low-Degeneracy Graph Streams
Sebastian Lüderssen, Stefan Neumann, Pan Peng
We study the problem of -approximating the number of four-cycles in graphs given as arbitrary order edge streams. We propose two new algorithms based on sampling i…
Learning-Augmented Streaming Algorithms for Correlation Clustering
Yinhao Dong, Shan Jiang, Shi Li +1
We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partit…
Learning-Augmented Streaming Algorithms for Approximating MAX-CUT
Yinhao Dong, Pan Peng, Ali Vakilian
We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a -approximation for estimating the va…
Sublinear-Time Opinion Estimation in the Friedkin--Johnsen Model
Stefan Neumann, Yinhao Dong, Pan Peng
Online social networks are ubiquitous parts of modern societies and the discussions that take place in these networks impact people's opinions on diverse topics, such as politics o…