The coalition structure formation problem represents an active research area in multi-agent systems. A coalition structure is defined as a partition of the agents involved in a system into disjoint coalitions. The problem of finding the optimal coalition structure is NP-complete. In order to find the optimal solution in a combinatorial optimization problem it is theoretically possible to enumerate the solutions and evaluate each. But this approach is infeasible since the number of solutions often grows exponentially with the size of the problem. In this paper we present a greedy adaptive search procedure (GRASP) to efficiently search the space of coalition structures in order to find an optimal one. Experiments and comparisons to other algorithms prove the validity of the proposed method in solving this hard combinatorial problem.
Both DP and IDP are not anytime algorithms, they cannot be interrupted before their normal termination. @cite_1 , have presented the first anytime algorithm, sketched in Algorithm , that can be interrupted to obtain a solution within a time limit but not guaranteed to be optimal. When not interrupted it returns the optimal solution. The coalition structure generation process can be viewed as a search in a coalition structure graph as reported in Figure . One desideratum is to be able to guarantee that the coalition structure is within a worst case bound from optimal, i.e. that searching through a subset @math of coalition structures, is finite, and as small as possible, where @math is the best CS and @math is the best CS that has been seen in the subset @math . @cite_1 has been proved that: to bound @math , it suffices to search the lowest two levels of the coalition structure graph (with this search, the bound @math , and the number of nodes searched is @math ); this bound is tight; and, no other search algorithm can establish any bound @math while searching only @math nodes or fewer.
@cite_1
144107075 2156887976 2949393806 2151239055
We present a new Dynamic Programming (DP) formulation of the Coalition Structure Generation (CSG) problem based on imposing a hierarchical organizational structure over the agents. We show the efficiency of this formulation by deriving DyPE, a new optimal DP algorithm which significantly outperforms current DP approaches in speed and memory usage. In the classic case, in which all coalitions are feasible, DyPE has half the memory requirements of other DP approaches. On graph-restricted CSG, in which feasibility is restricted by a (synergy) graph, DyPE has either the same or lower computational complexity depending on the underlying graph structure of the problem. Our empirical evaluation shows that DyPE outperforms the state-of-the-art DP approaches by several orders of magnitude in a large range of graph structures (e.g. for certain scalefree graphs DyPE reduces the memory requirements by @math and solves problems that previously needed hours in minutes). Coalition formation is a key topic in multiagent systems. One may prefer a coalition structure that maximizes the sum of the values of the coalitions, but often the number of coalition structures is too large to allow exhaustive search for the optimal one. Furthermore, finding the optimal coalition structure is NP-complete. But then, can the coalition structure found via a partial search be guaranteed to be within a bound from optimum? We show that none of the previous coalition structure generation algorithms can establish any bound because they search fewer nodes than a threshold that we show necessary for establishing a bound. We present an algorithm that establishes a tight bound within this minimal amount of search, and show that any other algorithm would have to search strictly more. The fraction of nodes needed to be searched approaches zero as the number of agents grows. If additional time remains, our anytime algorithm searches further, and establishes a progressively lower tight bound. Surprisingly, just searching one more node drops the bound in half. As desired, our algorithm lowers the bound rapidly early on, and exhibits diminishing returns to computation. It also significantly outperforms its obvious contenders. Finally, we show how to distribute the desired search across self-interested manipulative agents. © 1999 Elsevier Science B.V. All rights reserved. We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every 2-CSP instance I a rounding algorithm for r rounds of the Lasserre SDP hierarchy for I that obtains an integral solution that is at most worse than the relaxation's value (normalized to lie in [0,1]), as long as r > k ( ) ( ) ;, where k is the alphabet size of I, @math , and @math denotes the number of eigenvalues larger than @math in the normalized adjacency matrix of the constraint graph of @math . In the case that @math is a instance, the threshold @math is only a polynomial in @math , and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the @math constraints specified by the @math level of the Lasserre hierarchy, and in some cases @math rounds of our program can be evaluated in time @math . Given an arc-weighted directed graph G = (V, A, spl lscr ) and a pair of nodes s, t, we seek to find an s-t walk of length at most B that maximizes some given function f of the set of nodes visited by the walk. The simplest case is when we seek to maximize the number of nodes visited: this is called the orienteering problem. Our main result is a quasi-polynomial time algorithm that yields an O(log OPT) approximation for this problem when f is a given submodular set function. We then extend it to the case when a node v is counted as visited only if the walk reaches v in its time window [R(v), D(v)]. We apply the algorithm to obtain several new results. First, we obtain an O(log OPT) approximation for a generalization of the orienteering problem in which the profit for visiting each node may vary arbitrarily with time. This captures the time window problem considered earlier for which, even in undirected graphs, the best approximation ratio known [Bansal, (2004)] is O(log sup 2 OPT). The second application is an O(log sup 2 k) approximation for the k-TSP problem in directed graphs (satisfying asymmetric triangle inequality). This is the first non-trivial approximation algorithm for this problem. The third application is an O(log sup 2 k) approximation (in quasi-poly time) for the group Steiner problem in undirected graphs where k is the number of groups. This improves earlier ratios (Garg, ) by a logarithmic factor and almost matches the inapproximability threshold on trees (Halperin and Krauthgamer, 2003). This connection to group Steiner trees also enables us to prove that the problem we consider is hard to approximate to a ratio better than spl Omega (log sup 1- spl epsi OPT), even in undirected graphs. Even though our algorithm runs in quasi-poly time, we believe that the implications for the approximability of several basic optimization problems are interesting.