39 citations · 135 across the 18 of their papers we have counts for
17 papers · 1 filter
Learning-Augmented Online Packet Scheduling with Deadlines
Ya-Chun Liang, Clifford Stein, Hao-Ting Wei
The modern network aims to prioritize critical traffic over non-critical traffic and effectively manage traffic flow. This necessitates proper buffer management to prevent the loss…
Scheduling with Speed Predictions
Eric Balkanski, Tingting Ou, Clifford Stein +1
Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, ver…
Estimating the Longest Increasing Subsequence in Nearly Optimal Time
Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha +1
Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length can be computed exactly i…
A Competitive Algorithm for Throughput Maximization on Identical Machines
Benjamin Moseley, Kirk Pruhs, Clifford Stein +1
This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on identical machines. The main resu…
Incremental Edge Orientation in Forests
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul +2
For any forest it is possible to orient the edges so that no vertex in has out-degree greater than . This paper considers the incremental edge-orientation p…
Distributed Algorithms for Matching in Hypergraphs
Oussama Hanguir, Clifford Stein
We study the -Uniform Hypergraph Matching (-UHM) problem: given an -vertex hypergraph where every hyperedge is of size , find a maximum cardinality set of disjoi…
Parallel Approximate Undirected Shortest Paths Via Low Hop Emulators
Alexandr Andoni, Clifford Stein, Peilin Zhong
We present a -approximate parallel algorithm for computing shortest paths in undirected graphs, achieving depth and $m\mathrm{poly}(\log n)…
Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time
Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi +2
We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic ti…
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond
MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin +1
Distributed processing frameworks, such as MapReduce, Hadoop, and Spark are popular systems for processing large amounts of data. The design of efficient algorithms in these framew…
Log Diameter Rounds Algorithms for -Vertex and -Edge Connectivity
Alexandr Andoni, Clifford Stein, Peilin Zhong
Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data --- da…
A general framework for handling commitment in online throughput maximization
Lin Chen, Franziska Eberle, Nicole Megow +2
We study a fundamental online job admission problem where jobs with deadlines arrive online over time at their release dates, and the task is to determine a preemptive single-serve…
Parallel Graph Connectivity in Log Diameter Rounds
Alexandr Andoni, Clifford Stein, Zhao Song +2
We study graph connectivity problem in MPC model. On an undirected graph with nodes and edges, round connectivity algorithms have been known for over 35 years.…
An O(log log m)-competitive Algorithm for Online Machine Minimization
Sungjin Im, Benjamin Moseley, Kirk Pruhs +1
This paper considers the online machine minimization problem, a basic real time scheduling problem. The setting for this problem consists of n jobs that arrive over time, where eac…
An Empirical Study of Online Packet Scheduling Algorithms
Nourhan Sakr, Cliff Stein
This work studies online scheduling algorithms for buffer management, develops new algorithms, and analyzes their performances. Packets arrive at a release time r, with a non-negat…
Fully Dynamic Matching in Bipartite Graphs
Aaron Bernstein, Cliff Stein
Maximum cardinality matching in bipartite graphs is an important and well-studied problem. The fully dynamic version, in which edges are inserted and deleted over time has also bee…
Online Stochastic Packing Applied to Display Ad Allocation
Jon Feldman, Monika Henzinger, Nitish Korula +2
Inspired by online ad allocation, we study online stochastic packing linear programs from theoretical and practical standpoints. We first present a near-optimal online algorithm fo…
Budget Optimization in Search-Based Advertising Auctions
Jon Feldman, S. Muthukrishnan, Martin Pal +1
Internet search companies sell advertisement slots based on users' search queries via an auction. While there has been a lot of attention on the auction process and its game-theore…