Let (L: boolean AND, boolean OR) be a finite lattice and let n be a positive integer. A function f : L-n -> R is said to be submodular if f(a boolean AND b) + f(a boolean OR b) Z and an integer m such that min(x i...
详细信息
Let (L: boolean AND, boolean OR) be a finite lattice and let n be a positive integer. A function f : L-n -> R is said to be submodular if f(a boolean AND b) + f(a boolean OR b) <= f(a) + f(b) for all a, b is an element of L-n. In this article we study submodularfunctions when L is a diamond. Given oracle access to f we are interested in finding x is an element of L-n such that f(x) = min(y is an element of Ln) f(y) as efficiently as possible. We establish a min-max theorem, which states that the minimum of the submodularfunction is equal to the maximum of a certain function defined over a certain polyhedron;and a good characterisation of the minimisation problem, i.e., we show that given an oracle for computing a submodular f : L-n -> Z and an integer m such that min(x is an element of Ln) f(x) = there is a proof of this fact which can be verified in time polynomial in n and max(t is an element of Ln) log vertical bar f(t)vertical bar;and a pseudopolynomial-time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f : L-n -> Z one can find min(t is an element of Ln) f(t) in time bounded by a polynomial in n and max(t is an element of Ln) vertical bar f(t)vertical bar. (C) 2011 Elsevier B.V. All rights reserved.
Given a graph G=(V,E) with edge weights w (e) aa"e, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of the edges with nodes in the same class plu...
详细信息
Given a graph G=(V,E) with edge weights w (e) aa"e, the optimum cooperation problem consists in determining a partition of the graph that maximizes the sum of weights of the edges with nodes in the same class plus the number of the classes of the partition. The problem is also known in the literature as the optimum attack problem in networks. Furthermore, a relevant physics application exists. In this work, we present a fast exact algorithm for the optimum cooperation problem. Algorithms known in the literature require |V|-1 minimum cut computations in a corresponding network. By theoretical considerations and appropriately designed heuristics, we considerably reduce the numbers of minimum cut computations that are necessary in practice. We show the effectiveness of our method by presenting results on instances coming from the physics application. Furthermore, we analyze the structure of the optimal solutions.
We describe a purely combinatorial algorithm which, given a submodular set function f on a finite set V, finds a nontrivial subset A of V minimizing f[A] + f[V \ A].:This algorithm, an extension of the Nagamochi-Ibara...
详细信息
We describe a purely combinatorial algorithm which, given a submodular set function f on a finite set V, finds a nontrivial subset A of V minimizing f[A] + f[V \ A].:This algorithm, an extension of the Nagamochi-Ibaraki minimum cut algorithm as simplified by Steer and Wagner [M. Steer, F. Wagner, A simple min cut algorithm, Proceedings of the European Symposium on Algorithms ESA '94, LNCS 855, Springer, Berlin, 1994, pp. 141-147] and by Frank [A. Frank, On the edge-connectivity algorithm of Nagamochi and Ibaraki, Laboratoire Artemis, IMAG, Universite J. Fourier, Grenbole, 1994], minimizes any symmetric submodularfunction using O(/V/(3)) calls to a function value oracle. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
暂无评论