Maintaining assignments online: Matching, scheduling, and flows

Anupam Gupta, Amit Kumar, Cliff Stein

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Consider the following edge-orientation problem: edges of a graph appear online one-by-one and they to be directed- given an "orientation". We want to ensure that the in- degree of each vertex remains low. (This is a simple case of scheduling unit-sized jobs on machines, where each job can only go on one of two machines.) If the edge-orientations we assign are irrevocable, we suffer a significant loss in quality due to online decision-making (as compared to the offline performance). For instance the best online competitive ratio achievable is Θ(logm) for even this toy problem. But what if the decisions are not irrevocable - what if we allow a limited number of reassignments? Can we do much better? We show that indeed we can. For instance, for edge-orientation, we can achieve a constant-competitive load while doing only a constant number of re-orientations per edge (in an amortized sense). For more substantial problems, our results are as follows: For online matching, where the left vertices arrive online and must be matched to the right vertices, we give an algorithm that reassigns the left vertices an (amortized) constant number of times, and maintains a constant factor to the optimal load on the right vertices. We extend this to restricted machine scheduling with arbitrary sized jobs and give an algorithm that maintains load which is O(log log mn) times the optimum, and reassigns each job only an (amortized) constant number of times. Consider a digraph with a single source, where sinks arrive online and want to send unit flow to the source. The goal is to minimize the congestion on the edges. Suppose there is an offline flow such that the total length of the flow paths is F*. We give an algorithm that reroutes flow along O(F*) edges and achieves a O(l)-approximation to the congestion.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Print)9781611973389
StatePublished - 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Country/TerritoryUnited States
CityPortland, OR

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Maintaining assignments online: Matching, scheduling, and flows'. Together they form a unique fingerprint.

Cite this