Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing: Las Vegas, Nevada, May 29-June 1, 1995 |
Contents
Improved Approximation Algorithms for Uniform Connectivity Problems | 1 |
A Randomized Fully Polynomial Time Approximation Scheme for the All Terminal Network Reliability | 11 |
Adding Multiple Cost Constraints to Combinatorial Optimization Problems with Applications | 18 |
Copyright | |
75 other sections not shown
Common terms and phrases
adversary approximation algorithms assume bits boolean boolean functions circuit complexity component Computer Science connected consider constant construction contains copy Corollary data structure defined definition denote deterministic distribution edge exists expander graphs factor finite function given graph G IEEE implies input integer label leaf label least Lemma length linear log log lower bound machine Markov chains monotone node O(log operations optimal oracle output P₁ packets pair partition path permutation polynomial probabilistic probability probes problem Proc processors proof protocol prove query queue random recursive reduce representation class result rithm routing scheme sender sequence simulation sorting sorting network space spanning STCON step STOC stopping rule strategy string subset Symposium techniques Theorem tion tokens tree undirected graph update upper bound variables VC dimension vector vertex vertices weight