Proceedings of the ...ACM Symposium on Theory of Computing, Volume 311999 - Formal languages |
Contents
A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow | 11 |
NearOptimal Hardness Results and Approximation Algorithms for EdgeDisjoint Paths | 19 |
Session | 29 |
Copyright | |
41 other sections not shown
Other editions - View all
Common terms and phrases
adversary agent allocated apply approximation algorithm assignment assume assumption cache caching algorithm circuit communication complexity competitive ratio Computer Science consider constant constraint construction cost cycle defined definition denote directed graph distance product distribution edge-disjoint edges entropy equation-system EQUI error error-correcting code exists extractor fraction fully parallelizable given greedy algorithm Hence inequality input integer interval k-median problem least Lemma length linear programming lower bound matching mechanism min-entropy nodes NP-hard O(log obtain one-way functions online algorithm optimal output packets pairs parameters PIR protocol polylogarithmic polynomial private information retrieval prob probability Proc processors proof prove pseudo-random random bits request result rithm routing satisfies scheduling Section sequence server shortest path solution strategy T₁ technique Theorem Theory of Computing tion tree undirected upper bound variables verifier vertex vertices Wigderson