A local algorithm is a distributed algorithm where each node must operate solely based on the information that was available at system startup within a constant-size neighbourhood of the node. We study the applicability of local algorithms to max-min LPs where the objective is to maximise mink Sigmav CkvXv subject to Sigmav alphaivXv les 1 far each i and Xv ges 0 far each v. Here ckv ges 0, and the support sets Vi = v : alphaiv> 0 , Vk = v : ckv > 0 , Iv = i: alphaiv > 0 and Kv = k : Ckv > 0 have bounded size. In the distributed setting, each agent v is responsible for choosing the value of Xv, and the communication network is a hypergraph H where the sets Vk and Vi constitute the hyperedges. We present inapproximability results for a wide range of structural assumptions; for example, even if |Vi| and |Vk| are bounded by some constants larger than 2, there is no local approximation scheme. To contrast the negative results, we present a local approximation algorithm which achieves good approximation ratios if we can bound the relative growth of the vertex neighbourhoods in H.
For combinatorial problems, there are both negative @cite_10 @cite_0 and positive @cite_7 @cite_11 @cite_9 @cite_16 @cite_1 results on the applicability of local algorithms.
@cite_7 @cite_9 @cite_1 @cite_0 @cite_16 @cite_10 @cite_11
1494455882 1810595280 2011058337 2017345786
In this chapter we review the main results known on local search algorithms with worst case guarantees. We consider classical combinatorial optimization problems: satisfiability problems, traveling salesman and quadratic assignment problems, set packing and set covering problems, maximum independent set, maximum cut, several facility location related problems and finally several scheduling problems. A replica placement problem in a distributed file systems is also considered as an example of the use of a local search algorithm in a distributed environment. For each problem we have provided the neighborhoods used along with approximation results. Proofs when too technical are omitted, but often sketch of proofs are provided. The algorithm for Lovasz Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects that satisfy a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm from the witness tree. We apply our technique to improve the best known upper bound to acyclic chromatic index. Specifically we show that a graph with maximum degree Δ has an acyclic proper edge coloring with at most ⌈3.74(Δ − 1)⌉ + 1 colors, whereas the previously known best bound was 4(Δ − 1). The same technique is also applied to improve corresponding bounds for graphs with bounded girth. An interesting aspect of this application is that the probability of the "undesirable" events do not have a uniform upper bound, i.e. it constitutes a case of the asymmetric Lovasz Local Lemma. We present a novel, general, optimally fast, incremental way of searching for a universal algorithm that solves each task in a sequence of tasks. The Optimal Ordered Problem Solver (OOPS) continually organizes and exploits previously found solutions to earlier tasks, efficiently searching not only the space of domain-specific algorithms, but also the space of search algorithms. Essentially we extend the principles of optimal nonincremental universal search to build an incremental universal learner that is able to improve itself through experience. The initial bias is embodied by a task-dependent probability distribution on possible program prefixes. Prefixes are self-delimiting and executed in online fashion while being generated. They compute the probabilities of their own possible continuations. Let p^n denote a found prefix solving the first n tasks. It may exploit previously stored solutions p^i, i >n, by calling them as subprograms, or by copying them and editing the copies before applying them. We provide equal resources for two searches that run in parallel until p^ n+1 is discovered and stored. The first search is exhaustive; it systematically tests all possible prefixes on all tasks up to n+1. The second search is much more focused; it only searches for prefixes that start with p^n, and only tests them on task n+1, which is safe, because we already know that such prefixes solve all tasks up to n. Both searches are depth-first and bias-optimal: the branches of the search trees are program prefixes, and backtracking is triggered once the sum of the runtimes of the current prefix on all current tasks exceeds the prefix probability multiplied by the total search time so far. In illustrative experiments, our self-improver becomes the first general system that learns to solve all n disk Towers of Hanoi tasks (solution size 2^n-1) for n up to 30, profiting from previously solved, simpler tasks involving samples of a simple context free language. The purpose of this paper is a study of computation that can be done locally in a distributed network, where "locally" means within time (or distance) independent of the size of the network. Locally checkable labeling (LCL) problems are considered, where the legality of a labeling can be checked locally (e.g., coloring). The results include the following: There are nontrivial LCL problems that have local algorithms. There is a variant of the dining philosophers problem that can be solved locally. Randomization cannot make an LCL problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. It is undecidable, in general, whether a given LCL has a local algorithm. However, it is decidable whether a given LCL has an algorithm that operates in a given time @math . Any LCL problem that has a local algorithm has one that is order-invariant (the algorithm depends only on the order of the processor IDs).