206818151
Graph bisection algorithms with good average case behavior
In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixedd≧3, all sufficiently largen and allb=o(n1−1/[(d+1)/2]), the algorithm finds the minimum bisection for almost alld-regular labelled simple graphs with 2n nodes and bisection widthb. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection widtho(n2/3). The algorithm differs from other graph bisection heuristics (as well as from many heuristics for other NP-complete problems) in several respects. Most notably:(i)the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimum bisection,(ii)whenever the algorithm produces a bisection, it is guaranteed to be optimal (i.e., the algorithm also produces a proof that the bisection it outputs is an optimal bisection),(iii)the algorithm works well both theoretically and experimentally,(iv)the algorithm employs global methods such as network flow instead of local operations such as 2-changes, and(v)the algorithm works well for graphs with small bisections (as opposed to graphs with large bisections, for which arbitrary bisections are nearly optimal).
32346819
Graph Bisection Algorithms with Good Average Case Behavior
We describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixed d⩾3, all suffciently large n and all b = o(n1-(1/[(d+1)/2]), the algorithm finds the minimum bisection for almost all d-regular labelled simple graphs with 2n nodes and bisection width b.
33123515
Safety and Liveness of omega-Context-Free Languages
We show several sufficient conditions for w-context free languages to have w-context free live sets, but fail to produce a necessary and sufficient condition.
42620016
More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems
Abstract We define the k -SET CONSENSUS PROBLEM as an extension of the CONSENSUS problem, where each processor decides on a single value such that the set of decided values in any run is of size at most k . We require the agreement condition that all values decided upon are initial values of some processor. We show that the problem has a simple ( k −1)-resilient protocol in a totally asynchronous system. In an attempt to come up with a matching lower bound on the number of failures, we study the uncertainty condition, which requires that there must be some initial configuration from which all possible input values can be decided. We prove using a combinatorial argument that any k -resilient protocol for the k -set agreement problem would satisfy the uncertainty condition, while this is not true for any ( k −1)-resilient protocol. This result seems to strengthen the conjecture that there is no k -resilient protocol for this problem. We prove this result for a restricted class of protocols. Our motivation for studying this problem is to test whether the number of choices allowed to the processors is related to the number of faults . We hope that this will provide intuition towards achieving better bounds for more practical problems that arise in distributed computing, e.g., the renaming problem. The larger goal is to characterize the boundary between possibility and impossibility in asynchronous systems given multiple faults.
7826204
Probabilistic Recurrence Relations Revisited
The performance attributes of a broad class of randomised algorithms can be described by a recurrence relation of the form T(x)=a(x)+T(H(x)), where a is a function and H(x) is a random variable. For instance, T(x) may describe the running time of such an algorithm on a problem of size x. Then T(x) is a random variable, whose distribution depends on the distribution of H(x). To give high probability guarantees on the performance of such randomised algorithms, it suffices to obtain bounds on the tail of the distribution of T(x). Karp derived tight bounds on this tail distribution, when the distribution of H(x) satisfies certain restrictions. However, his proof is quite difficult to understand. In this paper, we derive bounds similar to Karp's using standard tools from elementary probability theory, such as Markov's inequality, stochastic dominance and a variant of Chernoff bounds applicable to unbounded variables. Further, we extend the results, showing that similar bounds hold under weaker restrictions on H(x). As an application, we derive performance bounds for an interesting class of algorithms that was outside the scope of the previous results.