共查询到20条相似文献,搜索用时 15 毫秒
1.
Recently Dadush et al. (2017) have devised a polynomial submodular function minimization (SFM) algorithm based on their LP algorithm. In the present note we also show a weakly polynomial algorithm for SFM based on the recently developed linear programming feasibility algorithm of Chubanov (2017) to stimulate further research on SFM. 相似文献
2.
Maurice Queyranne 《Mathematical Programming》1998,82(1-2):3-12
We describe a purely combinatorial algorithm which, given a submodular set functionf on a finite setV, finds a nontrivial subsetA ofV minimizingf[A] + f[V A]. This algorithm, an extension of the Nagamochi—Ibaraki minimum cut algorithm as simplified by Stoer and Wagner [M. Stoer, 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 Artémis, IMAG, Université J. Fourier, Grenbole, 1994], minimizes any symmetric submodular function using O(|V|3) calls to a function value oracle. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper was presented at the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) in January 1995. This research was supported by the Natural Sciences and Engineering Research Council (NSERC) of Canada. 相似文献
3.
Satoru Fujishige 《Mathematical Programming》1984,29(2):125-141
The present paper shows that for any submodular functionf on a crossing family
with
, if the polyhedron
is nonempty, then there exist a unique distributive lattice
with
and a unique submodular function
with
such thatB(f) coincides with the base polyhedron
associated with the submodular system
. Here, iff is integer-valued, thenf
1 is also integer-valued.
Based on this fact, we also show the relationship between the independent-flow problem considered by the author and the minimum
cost flow problem considered by J. Edmonds and R. Giles. 相似文献
4.
5.
Maxim Sviridenko 《Operations Research Letters》2004,32(1):41-43
In this paper, we obtain an (1−e−1)-approximation algorithm for maximizing a nondecreasing submodular set function subject to a knapsack constraint. This algorithm requires O(n5) function value computations. 相似文献
6.
Zoltán Miklós 《Discrete Mathematics》2013,313(22):2650-2655
7.
8.
Submodular functions are powerful tools to model and solve either to optimality or approximately many operational research problems including problems defined on graphs. After reviewing some long-standing theoretical results about the structure of local and global maxima of submodular functions, Cherenin’s selection rules and his Dichotomy Algorithm, we revise the above mentioned theory and show that our revision is useful for creating new non-binary branching algorithms and finding either approximation solutions with guaranteed accuracy or exact ones. 相似文献
9.
Theory of submodular programs: A fenchel-type min-max theorem and subgradients of submodular functions 总被引:3,自引:0,他引:3
Satoru Fujishige 《Mathematical Programming》1984,29(2):142-155
We consider submodular programs which are problems of minimizing submodular functions on distributive lattices with or without
constraints. We define a convex (or concave) conjugate function of a submodular (or supermodular) function and show a Fenchel-type
min-max theorem for submodular and supermodular functions. We also define a subgradient of a submodular function and derive
a necessary and sufficient condition for a feasible solution of a submodular program to be optimal, which is a counterpart
of the Karush-Kuhn-Tucker condition for convex programs.
This work is supported by the Alexander von Humboldt fellowship (1982/83), West Germany. 相似文献
10.
Fredrik Kuivinen 《Discrete Optimization》2011,8(3):459-477
Let (L;?,?) be a finite lattice and let n be a positive integer. A function f:Ln→R is said to be submodular if for all . In this article we study submodular functions when L is a diamond. Given oracle access to f we are interested in finding such that as efficiently as possible. We establish
•
a min–max theorem, which states that the minimum of the submodular function 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:Ln→Z and an integer m such that , there is a proof of this fact which can be verified in time polynomial in n and ; and •
a pseudopolynomial-time algorithm for the minimisation problem, i.e., given an oracle for computing a submodular f:Ln→Z one can find in time bounded by a polynomial in n and .
11.
Satoru Fujishige 《Mathematical Programming》1984,29(3):348-360
The author recently introduced a concept of a subdifferential of a submodular function defined on a distributive lattice. Each subdifferential is an unbounded polyhedron. In the present paper we determine the set of all the extreme points and rays of each subdifferential and show the relationship between subdifferentials of a submodular function and subdifferentials, in an ordinary sense of convex analysis, of Lovász's extension of the submodular function. Furthermore, for a modular function on a distributive lattice we give an algorithm for determining which subdifferential contains a given vector and finding a nonnegative linear combination of extreme vectors of the subdifferential which expresses the given vector minus the unique extreme point of the subdifferential. 相似文献
12.
We consider the problem of partitioning a graph into cliques of bounded cardinality. The goal is to find a partition that minimizes the sum of clique costs where the cost of a clique is given by a set function on the nodes. We present a general algorithmic solution based on solving the problem variant without the cardinality constraint. We obtain constant factor approximations depending on the solvability of this relaxation for a large class of submodular cost functions which we call value-monotone submodular functions. For special graph classes we give optimal algorithms. 相似文献
13.
JianMing Chang 《中国科学 数学(英文版)》2012,55(8):1669-1676
In this paper,we continue to study the normality of a family of meromorphic functions without simple zeros and simple poles such that their derivatives omit a given holomorphic function.Such a family in general is not normal at the zeros of the omitted function.Our main result is the characterization of the non-normal sequences,and hence some known results are its corollaries. 相似文献
14.
Structure of a simple scheduling polyhedron 总被引:5,自引:0,他引:5
Maurice Queyranne 《Mathematical Programming》1993,58(1-3):263-285
15.
The expressive power of binary submodular functions 总被引:1,自引:0,他引:1
We investigate whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This question has been considered in several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively.Our results have several corollaries. First, we characterise precisely which submodular polynomials of arity 4 can be expressed by binary submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish, for the first time, that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions. 相似文献
16.
17.
《Operations Research Letters》2020,48(3):356-361
We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of the random function. We demonstrate the proposed method on a stochastic set covering problem that admits an efficient CVaR oracle for the random coverage function. 相似文献
18.
Jeremy E Dawson 《Journal of Mathematical Analysis and Applications》1983,95(1):214-222
A submodular (and non-decreasing) function on a set induces an independence structure; the notion of a “balanced” set in this situation helps us determine whether a given independence structure is induced by any submodular function other than its own rank function, answering a question of U. S. R. Murty and I. Simon. The notion “balanced” also has a natural meaning when one independence structure is induced from another across a bipartite graph. 相似文献
19.