Clifford Stein

Orcid: 0000-0002-0614-6620

Affiliations:
  • Columbia University, New York City, USA


According to our database1, Clifford Stein authored at least 147 papers between 1990 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
A competitive algorithm for throughput maximization on identical machines.
Math. Program., July, 2024

Cluster Before You Hallucinate: Node-Capacitated Network Design and Energy Efficient Routing.
SIAM J. Comput., 2024

Polylog-Competitive Deterministic Local Routing and Scheduling.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Von Neumann-Morgenstern Stability and Internal Closedness in Matching Theory.
Proceedings of the Integer Programming and Combinatorial Optimization, 2024

Drawing Competitive Districts in Redistricting.
Proceedings of the 5th Symposium on Foundations of Responsible Computing, 2024

2023
A randomized algorithm for online metric b-matching.
Oper. Res. Lett., November, 2023

Learning-Augmented Online Packet Scheduling with Deadlines.
CoRR, 2023

Scheduling with Speed Predictions.
Proceedings of the Approximation and Online Algorithms - 21st International Workshop, 2023

Energy-Efficient Scheduling with Predictions.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022
Internal Closedness and von Neumann-Morgenstern Stability in Matching Theory: Structures and Complexity.
CoRR, 2022

Estimating the Longest Increasing Subsequence in Nearly Optimal Time.
Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021
A Competitive Algorithm for Throughout Maximization on Identical Machines.
CoRR, 2021

Incremental Edge Orientation in Forests.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Matching Drivers to Riders: A Two-Stage Robust Approach.
Proceedings of the Approximation, 2021

2020
Scheduling When You Do Not Know the Number of Machines.
ACM Trans. Algorithms, 2020

Hallucination Helps: Energy Efficient Virtual Circuit Routing.
SIAM J. Comput., 2020

A general framework for handling commitment in online throughput maximization.
Math. Program., 2020

Advance Service Reservations with Heterogeneous Customers.
Manag. Sci., 2020

Distributed Algorithms for Matching in Hypergraphs.
Proceedings of the Approximation and Online Algorithms - 18th International Workshop, 2020

Parallel approximate undirected shortest paths via low hop emulators.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019
MapReduce Meets Fine-Grained Complexity: MapReduce Algorithms for APSP, Matrix Multiplication, 3-SUM, and Beyond.
CoRR, 2019

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Submodular Secretary Problem with Shortlists.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Log Diameter Rounds Algorithms for 2-Vertex and 2-Edge Connectivity.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Resource cost aware scheduling.
Eur. J. Oper. Res., 2018

Scheduling (Dagstuhl Seminar 18101).
Dagstuhl Reports, 2018

Fast algorithms for knapsack via convolution and prediction.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Scheduling When You Don't Know the Number of Machines.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

The Online Set Aggregation Problem.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Approximate Matchings in Massive Graphs via Local Structure (Invited Talk).
Proceedings of the 29th International Symposium on Algorithms and Computation, 2018

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Parallel Graph Connectivity in Log Diameter Rounds.
Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

2017
Max-min Fair Rate Allocation and Routing in Energy Harvesting Networks: Algorithmic Analysis.
Algorithmica, 2017

Extending Search Phases in the Micali-Vazirani Algorithm.
Proceedings of the 16th International Symposium on Experimental Algorithms, 2017

An O(Log Log m)-Competitive Algorithm for Online Machine Minimization.
Proceedings of the 2017 IEEE Real-Time Systems Symposium, 2017

Simultaneously Load Balancing for Every p-norm, With Reassignments.
Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

2016
Scheduling (Dagstuhl Seminar 16081).
Dagstuhl Reports, 2016

An Empirical Study of Online Packet Scheduling Algorithms.
Proceedings of the Experimental Algorithms - 15th International Symposium, 2016

Experimental Analysis of Algorithms for Coflow Scheduling.
Proceedings of the Experimental Algorithms - 15th International Symposium, 2016

Faster Fully Dynamic Matchings with Small Approximation Ratios.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

A Fast Distributed Stateless Algorithm for alpha-Fair Packing Problems.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Towards a Convex HMM Surrogate for Word Alignment.
Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, 2016

2015
A Fast Distributed Algorithm for α-Fair Packing Problems.
CoRR, 2015

Minimizing the Total Weighted Completion Time of Coflows in Datacenter Networks.
Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Fully Dynamic Matching in Bipartite Graphs.
Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

On A Strictly Convex IBM Model 1.
Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, 2015

A 2-Competitive Algorithm For Online Convex Optimization With Switching Costs.
Proceedings of the Approximation, 2015

A Family of Latent Variable Convex Relaxations for IBM Model 2.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

2014
Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing.
Proceedings of the Symposium on Theory of Computing, 2014

Maintaining Assignments Online: Matching, Scheduling, and Flows.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Some Experiments with a Convex IBM Model 2.
Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, 2014

2013
Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints.
Oper. Res. Lett., 2013

The Complexity of Scheduling for p-norms of Flow and Stretch
CoRR, 2013

The Complexity of Scheduling for p-Norms of Flow and Stretch - (Extended Abstract).
Proceedings of the Integer Programming and Combinatorial Optimization, 2013

A Convex Alternative to IBM Model 2.
Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, 2013

2012
FairTorrent: A Deficit-Based Distributed Algorithm to Ensure Fairness in Peer-to-Peer Systems.
IEEE/ACM Trans. Netw., 2012

Online scheduling of packets with agreeable deadlines.
ACM Trans. Algorithms, 2012

Multicast Routing for Energy Minimization Using Speed Scaling.
Proceedings of the Design and Analysis of Algorithms, 2012

2011
Approximating Semidefinite Packing Programs.
SIAM J. Optim., 2011

Solving maximum flow problems on real-world bipartite graphs.
ACM J. Exp. Algorithmics, 2011

Energy Aware Scheduling for Weighted Completion Time and Weighted Tardiness
CoRR, 2011

2010
On distributing symmetric streaming computations.
ACM Trans. Algorithms, 2010

Online Stochastic Ad Allocation: Efficiency and Fairness
CoRR, 2010

Feasible and Accurate Algorithms for Covering Semidefinite Programs.
Proceedings of the Algorithm Theory, 2010

Online Stochastic Packing Applied to Display Ad Allocation.
Proceedings of the Algorithms, 2010

How to Schedule When You Have to Buy Your Energy.
Proceedings of the Approximation, 2010

2009
Divide-and-Conquer Approximation Algorithm for Vertex Cover.
SIAM J. Discret. Math., 2009

Speed Scaling for Weighted Flow Time.
SIAM J. Comput., 2009

Bounded-space online bin cover.
J. Sched., 2009

An O(n<sup>5/2</sup>logn) algorithm for the Rectilinear Minimum Link-Distance Problem in three dimensions.
Comput. Geom., 2009

Adding Trust to P2P Distribution of Paid Content.
Proceedings of the Information Security, 12th International Conference, 2009

FairTorrent: bringing fairness to peer-to-peer systems.
Proceedings of the 2009 ACM Conference on Emerging Networking Experiments and Technology, 2009

Introduction to Algorithms, 3rd Edition.
MIT Press, ISBN: 9780262533058, 2009

2008
Asymptotic performance of the non-forced idle time scheduling policies in the presence of variable demand for resources.
Proceedings of the 46th Annual Allerton Conference on Communication, 2008

2007
LP Decoding Corrects a Constant Fraction of Errors.
IEEE Trans. Inf. Theory, 2007

Vertex Cover Approximations on Random Graphs.
Proceedings of the Experimental Algorithms, 6th International Workshop, 2007

Models of malicious behavior in sponsored search.
Proceedings of the 2007 Spring Simulation Multiconference, 2007

Better online buffer management.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Budget optimization in search-based advertising auctions.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

Non-Preemptive Min-Sum Scheduling with Resource Augmentation.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006
On the Complexity of Processing Massive, Unordered, Distributed Data
CoRR, 2006

Grouped distributed queues: distributed queue, proportional share multiprocessor scheduling.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, 2006

Using Markov Chains To Design Algorithms For Bounded-Space On-Line Bin Cover.
Proceedings of the Eighth Workshop on Algorithm Engineering and Experiments, 2006

Discrete mathematics for computer science.
Mathematics accross the curriculum, Key College Publishing, ISBN: 978-1-930190-86-3, 2006

2005
Vertex Cover Approximations: Experiments and Observations.
Proceedings of the Experimental and Efficient Algorithms, 4th InternationalWorkshop, 2005

Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems.
Proceedings of the 2005 USENIX Annual Technical Conference, 2005

An optimal online algorithm for packet scheduling with agreeable deadlines.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

LP decoding achieves capacity.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring.
Proceedings of the Integer Programming and Combinatorial Optimization, 2005

An O(n<sup>5/2</sup>log n) Algorithm for the Rectilinear Minimum Link-Distance Problem.
Proceedings of the 17th Canadian Conference on Computational Geometry, 2005

2004
Approximating disjoint-path problems using packing integer programs.
Math. Program., 2004

Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut.
Math. Oper. Res., 2004

Scheduling an Industrial Production Facility.
Proceedings of the Integer Programming and Combinatorial Optimization, 2004

2003
Networks and Flows.
Proceedings of the Handbook of Graph Theory., 2003

2002
Optimal Time-Critical Scheduling via Resource Augmentation.
Algorithmica, 2002

Minimizing Makespan for the Lazy Bureaucrat Problem.
Proceedings of the Algorithm Theory, 2002

Existence theorems, lower bounds and algorithms for scheduling to meet two objectives.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

2001
Approximation Algorithms for Single-Source Unsplittable Flow.
SIAM J. Comput., 2001

Approximation Techniques for Average Completion Time Scheduling.
SIAM J. Comput., 2001

Reducing Mass Degeneracy in SAR by MS by Stable Isotopic Labeling.
J. Comput. Biol., 2001

Scheduling Multi-task Agents.
Proceedings of the Mobile Agents, 5th International Conference, 2001

Simultaneously optimizing two scheduling objectives.
Proceedings of the 15th International Parallel & Distributed Processing Symposium (IPDPS-01), 2001

Approximation Algorithms for the Minimum Bends Traveling Salesman Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

Implementation of a PTAS for Scheduling with Release Dates.
Proceedings of the Algorithm Engineering and Experimentation, Third International Workshop, 2001

Scheduling multi-task multi-agent systems.
Proceedings of the Fifth International Conference on Autonomous Agents, 2001

Introduction to Algorithms, Second Edition
The MIT Press and McGraw-Hill Book Company, ISBN: 0-07-013151-1, 2001

2000
Clustering Data without Prior Knowledge.
Proceedings of the Algorithm Engineering, 2000

1999
Improved Bicriteria Existence Theorems for Scheduling.
Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, 1999

Experimental Evaluation of Approximation Algorithms for Single-Source Unsplittable Flow.
Proceedings of the Integer Programming and Combinatorial Optimization, 1999

Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Scheduling Algorithms.
Proceedings of the Algorithms and Theory of Computation Handbook., 1999

1998
Minimizing average completion time in the presence of release dates.
Math. Program., 1998

Improved Bounds on Relaxations of a Parallel Machine Scheduling Problem.
J. Comb. Optim., 1998

Finding Real-Valued Single-Source Shortest Paths in <i>o(n<sup>3</sup>)</i> Expected Time.
J. Algorithms, 1998

A 2 2/3 Superstring Approximation Algorithm.
Discret. Appl. Math., 1998

Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998

An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998

1997
Task Scheduling in Networks.
SIAM J. Discret. Math., 1997

On the existence of schedules that are near-optimal for both makespan and total weighted completion time.
Oper. Res. Lett., 1997

Distributed Job Scheduling in Rings.
J. Parallel Distributed Comput., 1997

Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Experimental Study of Minimum Cut Algorithms.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Improved Approximation Algorithms for Unsplittable Flow Problems.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
A New Approach to the Minimum Cut Problem.
J. ACM, 1996

Finding Real-Valued Single-Source Shortest Paths.
Proceedings of the Integer Programming and Combinatorial Optimization, 1996

Improved Scheduling Algorithms for Minsum Criteria.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

A 2 2/3-Approximation Algorithm for the Shortest Superstring Problem.
Proceedings of the Combinatorial Pattern Matching, 7th Annual Symposium, 1996

1995
Fast Approximation Algorithms for Multicommodity Flow Problems.
J. Comput. Syst. Sci., 1995

Short Superstrings and the Structure of Overlapping Strings.
J. Comput. Biol., 1995

Scheduling Jobs that Arrive Over Time (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Improved Length Bounds for the Shortest Superstring Problem (Extended Abstract).
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

1994
Improved Approximation Algorithms for Shop Scheduling Problems.
SIAM J. Comput., 1994

Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts.
SIAM J. Comput., 1994

Improved Algorithms for Bipartite Network Flow.
SIAM J. Comput., 1994

Task Scheduling in Networks (Extended Abstract).
Proceedings of the Algorithm Theory, 1994

Job Scheduling in Rings.
Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994

Long Tours and Short Superstrings (Preliminary Version)
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Parallel algorithms for the assignment and minimum-cost flow problems.
Oper. Res. Lett., 1993

A Parallel Algorithm for Approximating the Minimum Cycle Cover.
Algorithmica, 1993

An O~(n<sup>2</sup>) algorithm for minimum cuts.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992
Approximation algorithms for multicommodity flow and shop scheduling problems.
PhD thesis, 1992

Approximating the Minimum-Cost Maximum Flow is P-Complete.
Inf. Process. Lett., 1992

1991
Implementation of a Combinatorial Multicommodity Flow Algorithm.
Proceedings of the Network Flows And Matching, 1991

1990
A Parallel Algorithm for Eliminating Cycles in Undirected Graphs.
Inf. Process. Lett., 1990

Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990


  Loading...