## Proceedings of the ...ACM Symposium on Theory of Computing, Volume 31 |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow | 11 |

NearOptimal Hardness Results and Approximation Algorithms for EdgeDisjoint Paths | 19 |

Session | 29 |

Copyright | |

33 other sections not shown

### Common terms and phrases

1-block adversary apply approximation algorithm assignment assume assumption cache cell probe model circuit communication complexity competitive ratio Computer Science consider constant constraint construction cost cycle database defined definition denote deterministic directed graph distance product distribution edge-disjoint edges elements equation-system equations error exists extractor factor flow fraction given greedy algorithm Hence implies inequality input integer LDF-assumptions least Lemma length linear programming lower bound matching matrix min-entropy negative cost nodes NP-hard oblivious transfer obtain one-way functions online algorithm optimal output packets pairs parameter PIR protocol polylogarithmic polynomial private information retrieval prob probability problem Proc processors proof prove query random bits result rithm routing satisfies scheduling sequence server shortest paths solution STOC subset Symposium technique Theorem Theory of Computing tion tree undirected upper bound variables verifier vertex vertices weights