共查询到20条相似文献,搜索用时 31 毫秒
1.
Akihisa Tamura 《Mathematical Programming》2005,102(2):339-354
We present a polynomial time scaling algorithm for the minimization of an M-convex function. M-convex functions are nonlinear discrete functions with (poly)matroid structures, which are being recognized as playing a fundamental role in tractable cases of discrete optimization. The algorithm is applicable also to a variant of quasi M-convex functions.Mathematics Subject Classification (2000):90C27, 68W40, 05B35This work is supported by a Grant-in-Aid for Scientific Research from the Ministry of Education, Culture, Sports, Science and Technology of Japan. 相似文献
2.
A proximity theorem is a statement that, given an optimization problem and its relaxation, an optimal solution to the original problem exists in a certain neighborhood of a solution to the relaxation. Proximity theorems have been used successfully, for example, in designing efficient algorithms for discrete resource allocation problems. After reviewing the recent results for L-convex and M-convex functions, this paper establishes proximity theorems for larger classes of discrete convex functions, L2-convex functions and M2-convex functions, that are relevant to the polymatroid intersection problem and the submodular flow problem.Mathematics Subject Classification (2000): 90C27, 05B35 相似文献
3.
We describe an O(n
4
hmin{logU,n
2logn}) capacity scaling algorithm for the minimum cost submodular flow problem. Our algorithm modifies and extends the Edmonds–Karp
capacity scaling algorithm for minimum cost flow to solve the minimum cost submodular flow problem. The modification entails
scaling a relaxation parameter δ. Capacities are relaxed by attaching a complete directed graph with uniform arc capacity
δ in each scaling phase. We then modify a feasible submodular flow by relaxing the submodular constraints, so that complementary
slackness is satisfied. This creates discrepancies between the boundary of the flow and the base polyhedron of a relaxed submodular
function. To reduce these discrepancies, we use a variant of the successive shortest path algorithm that augments flow along
minimum cost paths of residual capacity at least δ. The shortest augmenting path subroutine we use is a variant of Dijkstra’s
algorithm modified to handle exchange capacity arcs efficiently. The result is a weakly polynomial time algorithm whose running
time is better than any existing submodular flow algorithm when U is small and C is big. We also show how to use maximum mean cuts to make the algorithm strongly polynomial. The resulting algorithm is the
first capacity scaling algorithm to match the current best strongly polynomial bound for submodular flow.
Received: August 6, 1999 / Accepted: July 2001?Published online October 2, 2001 相似文献
4.
A greedy algorithm solves the problem of maximizing a linear objective function over the polyhedron (called the submodular polyhedron) determined by a submodular function on a distributive lattice or a ring family. We generalize the problem by considering a submodular function on a co-intersecting family and give an algorithm for solving it. Here, simple-minded greedy augmentations do not work any more and some complicated augmentations with multiple exchanges are required. We can find an optimal solution by at most 1/2n(n – 1) augmentations, wheren is the number of the variables and we assume a certain oracle for computing multiple exchange capacities. 相似文献
5.
《Discrete Applied Mathematics》2004,134(1-3):303-316
M-convex functions, introduced by Murota (Adv. Math. 124 (1996) 272; Math. Prog. 83 (1998) 313), enjoy various desirable properties as “discrete convex functions.” In this paper, we propose two new polynomial-time scaling algorithms for the minimization of an M-convex function. Both algorithms apply a scaling technique to a greedy algorithm for M-convex function minimization, and run as fast as the previous minimization algorithms. We also specialize our scaling algorithms for the resource allocation problem which is a special case of M-convex function minimization. 相似文献
6.
The concepts of L-convex function and M-convex function have recently been introduced by Murota as generalizations of submodular
function and base polyhedron, respectively, and discrete separation theorems are established for L-convex/concave functions
and for M-convex/concave functions as generalizations of Frank’s discrete separation theorem for submodular/supermodular set
functions and Edmonds’ matroid intersection theorem. This paper shows the equivalence between Murota’s L-convex functions
and Favati and Tardella’s submodular integrally convex functions, and also gives alternative proofs of the separation theorems
that provide a geometric insight by relating them to the ordinary separation theorem in convex analysis.
Received: November 27, 1997 / Accepted: December 16, 1999?Published online May 12, 2000 相似文献
7.
Satoru Fujishige 《Mathematical Programming》2000,88(1):217-220
U. Faigle and W. Kern have recently extended the work of their earlier paper and of M. Queyranne, F. Spieksma and F. Tardella
and have shown that a dual greedy algorithm works for a system of linear inequalities with {:0,1}-coefficients defined in
terms of antichains of an underlying poset and a submodular function on the set of ideals of the poset under some additional
condition on the submodular function.?In this note we show that Faigle and Kern’s dual greedy polyhedra belong to a class
of submodular flow polyhedra, i.e., Faigle and Kern’s problem is a special case of the submodular flow problem that can easily
be solved by their greedy algorithm.
Received: February 1999 / Accepted: December 1999?Published online February 23, 2000 相似文献
8.
Peng-Jun Wan Ding-Zhu Du Panos Pardalos Weili Wu 《Computational Optimization and Applications》2010,45(2):463-474
It is well-known that a greedy approximation with an integer-valued polymatroid potential function f is H(γ)-approximation of the minimum submodular cover problem with linear cost where γ is the maximum value of f over all singletons and H(γ) is the γ-th harmonic number. In this paper, we establish similar results for the minimum submodular cover problem with a submodular
cost (possibly nonlinear) and/or fractional submodular potential function f. 相似文献
9.
Hong Zheng Yi-Chang Chiu Pitu B. Mirchandani 《Journal of Mathematical Modelling and Algorithms》2014,13(2):169-189
This paper presents a heuristic algorithm for the earliest arrival flow problem. Existing exact algorithms, even polynomial in the output size, contain submodular function optimization as a frequently called subroutine, and thus are not practical in real-life applications. In this paper we propose an algorithm that does not involve the submodular function optimization. Although solving an EAF near-optimal, the algorithm is remarkably simple and efficient as it only involves shortest path computations on a static network. A numerical example illustrates how the algorithm works. As an application, we demonstrate the algorithm’s solution quality and computational performance by solving a real-size network. 相似文献
10.
This paper presents two fast cycle canceling algorithms
for the submodular ow problem. The rst uses an assignment
problem whose optimal solution identies most negative
node-disjoint cycles in an auxiliary network. Canceling these
cycles lexicographically makes it possible to obtain an optimal
submodular ow in O(n
4
h log(nC)) time, which almost matches the
current fastest weakly polynomial time for submodular flow
(where n is the number of
nodes, h is the time for
computing an exchange capacity, and C is the maximum absolute value of arc
costs). The second algorithm generalizes Goldbergs cycle
canceling algorithm for min cost flow to submodular flow to also
get a running time of O(n
4
h log(nC)).. We show how to modify these
algorithms to make them strongly polynomial, with running times
of O(n
6
h log n), which matches the fastest strongly
polynomial time bound for submodular flow. We also show how to
extend both algorithms to solve submodular flow with separable
convex objectives. * An extended abstract of a preliminary version of
part of this paper appeared in [22]. Research supported in part by a Grant-in-Aid of
the Ministry of Education, Science, Sports and Culture of
Japan. Research supported by an NSERC Operating Grant.
Part of this research was done during a sabbatical leave at
Cornell SORIE.§ Research supported in part by a Grant-in-Aid of
the Ministry of Education, Science, Sports and Culture of
Japan. 相似文献
11.
B. Alidaee 《Mathematical Methods of Operations Research》1992,36(5):409-416
In this note we consider two problems: (1) Schedulingn jobs non-preemptively on a single machine to minimize total weighted earliness and tardiness (WET). (2) Schedulingn jobs nonpreemptively on two parallel identical processors to minimize weighted mean flow time (WMFT). A new approach for these problems is presented. The approach is based on a problem of maximizing a submodular set function. Heuristic algorithm for the problems also is presented. 相似文献
12.
Satoru Iwata 《Mathematical Programming》1997,76(2):299-308
This paper presents a scaling scheme for submodular functions. A small but strictly submodular function is added before scaling
so that the resulting functions should be submodular. This scaling scheme leads to a weakly polynomial algorithm to solve
minimum cost integral submodular flow problems with separable convex cost functions, provided that an oracle for exchange
capacities is available. 相似文献
13.
We consider the problem of characterizing the minimum of a submodular function when the minimization is restricted to a family of subsets. We show that, for many interesting cases, there exist two elementsa andb of the groundset such that the problem is equivalent to the problem of minimizing the submodular function over the sets containinga but notb. This leads to a polynomial-time algorithm for minimizing a submodular function over these families of sets. Our results apply, for example, to the families of odd cardinality subsets or even cardinality subsets separating two given vertices, or to the complement of a lattice family of subsets. We also derive that the second smallest value of a submodular function over a lattice family can be computed in polynomial-time. These results generalize and unify several known results.Research partially supported by NSF contract 9302476-CCR, Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799. 相似文献
14.
Yusuke Kobayashi 《Discrete Applied Mathematics》2007,155(11):1471-1480
Induction (or transformation) by bipartite graphs is one of the most important operations on matroids, and it is well known that the induction of a matroid by a bipartite graph is again a matroid. As an abstract form of this fact, the induction of a matroid by a linking system is known to be a matroid.M-convex functions are quantitative extensions of matroidal structures, and they are known as discrete convex functions. As with matroids, it is known that the induction of an M-convex function by networks generates an M-convex function. As an abstract form of this fact, this paper shows that the induction of an M-convex function by linking systems generates an M-convex function. Furthermore, we show that this result also holds for M-convex functions on constant-parity jump systems. Previously known operations such as aggregation, splitting, and induction by networks can be understood as special cases of this construction. 相似文献
15.
YANGXIAOGUANG 《高校应用数学学报(英文版)》1998,13(3):341-346
In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time. 相似文献
16.
Jens Vygen 《Mathematical Methods of Operations Research》2002,56(1):101-126
We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly
polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the
capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general
problems (like submodular flow) and is likely to be more efficient in practice.
Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this
important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network
simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running
time of our algorithm by a factor of n. 相似文献
17.
A submodular polyhedron is a polyhedron associated with a submodular function. This paper presents a strongly polynomial time algorithm for line search in submodular polyhedra with the aid of a fully combinatorial algorithm for submodular function minimization. The algorithm is based on the parametric search method proposed by Megiddo. 相似文献
18.
Given a finite ground set N and a value vector ${a \in \mathbb{R}^N}$ , we consider optimization problems involving maximization of a submodular set utility function of the form ${h(S)= f \left(\sum_{i \in S} a_i \right ), S \subseteq N}$ , where f is a strictly concave, increasing, differentiable function. This utility function appears frequently in combinatorial optimization problems when modeling risk aversion and decreasing marginal preferences, for instance, in risk-averse capital budgeting under uncertainty, competitive facility location, and combinatorial auctions. These problems can be formulated as linear mixed 0-1 programs. However, the standard formulation of these problems using submodular inequalities is ineffective for their solution, except for very small instances. In this paper, we perform a polyhedral analysis of a relevant mixed-integer set and, by exploiting the structure of the utility function h, strengthen the standard submodular formulation significantly. We show the lifting problem of the submodular inequalities to be a submodular maximization problem with a special structure solvable by a greedy algorithm, which leads to an easily-computable strengthening by subadditive lifting of the inequalities. Computational experiments on expected utility maximization in capital budgeting show the effectiveness of the new formulation. 相似文献
19.
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. 相似文献
20.