5 papers
A Massively Parallel Algorithm for Minimum Weight Vertex Cover
Mohsen Ghaffari, Ce Jin, Daan Nilis
We present a massively parallel algorithm, with near-linear memory per machine, that computes a -approximation of minimum-weight vertex cover in ro…
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
Mohsen Ghaffari, Christoph Grunau, Ce Jin
We present round scalable Massively Parallel Computation algorithms for maximal independent set and maximal matching, in trees and more generally graphs of bounded…
Faster Algorithms for All Pairs Non-decreasing Paths Problem
Ran Duan, Ce Jin, Hongxun Wu
In this paper, we present an improved algorithm for the All Pairs Non-decreasing Paths (APNP) problem on weighted simple digraphs, which has running time $\tilde{O}(n^{\frac{3 + ω}…
An Improved FPTAS for 0-1 Knapsack
Ce Jin
The 0-1 knapsack problem is an important NP-hard problem that admits fully polynomial-time approximation schemes (FPTASs). Previously the fastest FPTAS by Chan (2018) with approxim…
Simulating Random Walks on Graphs in the Streaming Model
Ce Jin
We study the problem of approximately simulating a -step random walk on a graph where the input edges come from a single-pass stream. The straightforward algorithm using reservo…