## Abstract

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 language | English (US) |
---|---|

Title of host publication | Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |

Publisher | Association for Computing Machinery |

Pages | 468-479 |

Number of pages | 12 |

ISBN (Print) | 9781611973389 |

DOIs | |

State | Published - 2014 |

Event | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States Duration: Jan 5 2014 → Jan 7 2014 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 |
---|---|

Country/Territory | United States |

City | Portland, OR |

Period | 1/5/14 → 1/7/14 |

## ASJC Scopus subject areas

- Software
- General Mathematics