共查询到20条相似文献,搜索用时 31 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
Submodular flow problems, introduced by Edmonds and Giles [2], generalize network flow problems. Many algorithms for solving
network flow problems have been generalized to submodular flow problems (cf. references in Fujishige [4]), e.g. the cycle
canceling method of Klein [9]. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan [6], and
the choice of minimum-ratio cycles in Wallacher [12] lead to polynomial cycle canceling methods. For submodular flow problems,
Cui and Fujishige [1] show finiteness for the minimum-mean cycle method while Zimmermann [16] develops a pseudo-polynomial
minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining
both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems.
Received July 22, 1994 / Revised version received July 18, 1997? Published online May 28, 1999 相似文献
4.
Discrete convex analysis 总被引:6,自引:0,他引:6
Kazuo Murota 《Mathematical Programming》1998,83(1-3):313-371
A theory of “discrete convex analysis” is developed for integer-valued functions defined on integer lattice points. The theory
parallels the ordinary convex analysis, covering discrete analogues of the fundamental concepts such as conjugacy, subgradients,
the Fenchel min-max duality, separation theorems and the Lagrange duality framework for convex/nonconvex optimization. The
technical development is based on matroid-theoretic concepts, in particular, submodular functions and exchange axioms. Sections
1–4 extend the conjugacy relationship between submodularity and exchange ability, deepening our understanding of the relationship
between convexity and submodularity investigated in the eighties by A. Frank, S. Fujishige, L. Lovász and others. Sections
5 and 6 establish duality theorems for M- and L-convex functions, namely, the Fenchel min-max duality and separation theorems.
These are the generalizations of the discrete separation theorem for submodular functions due to A. Frank and the optimality
criteria for the submodular flow problem due to M. Iri-N. Tomizawa, S. Fujishige, and A. Frank. A novel Lagrange duality framework
is also developed in integer programming. We follow Rockafellar’s conjugate duality approach to convex/nonconvex programs
in nonlinear optimization, while technically relying on the fundamental theorems of matroid-theoretic nature. 相似文献
5.
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 相似文献
6.
We present a preprocessing algorithm to make certain polynomial time algorithms strongly polynomial time. The running time
of some of the known combinatorial optimization algorithms depends on the size of the objective functionw. Our preprocessing algorithm replacesw by an integral valued-w whose size is polynomially bounded in the size of the combinatorial structure and which yields the same set of optimal solutions
asw.
As applications we show how existing polynomial time algorithms for finding the maximum weight clique in a perfect graph and
for the minimum cost submodular flow problem can be made strongly polynomial.
Further we apply the preprocessing technique to make H. W. Lenstra’s and R. Kannan’s Integer Linear Programming algorithms
run in polynomial space. This also reduces the number of arithmetic operations used.
The method relies on simultaneous Diophantine approximation.
This research was done while the authors were visiting the Institute for Operations Research, University of Bonn, West Germany
(1984–85), and while the second author was visiting MSRI, Berkeley. Her research was supported in part by NSF Grant 8120790. 相似文献
7.
Reuven Rubinstein 《Methodology and Computing in Applied Probability》2009,11(4):491-549
We present a randomized algorithm, called the cloning algorithm, for approximating the solutions of quite general NP-hard
combinatorial optimization problems, counting, rare-event estimation and uniform sampling on complex regions. Similar to the
algorithms of Diaconis–Holmes–Ross and Botev–Kroese the cloning algorithm is based on the MCMC (Gibbs) sampler equipped with
an importance sampling pdf and, as usual for randomized algorithms, it uses a sequential sampling plan to decompose a “difficult”
problem into a sequence of “easy” ones. The cloning algorithm combines the best features of the Diaconis–Holmes–Ross and the
Botev–Kroese. In addition to some other enhancements, it has a special mechanism, called the “cloning” device, which makes
the cloning algorithm, also called the Gibbs cloner fast and accurate. We believe that it is the fastest and the most accurate randomized algorithm for counting known so far.
In addition it is well suited for solving problems associated with the Boltzmann distribution, like estimating the partition
functions in an Ising model. We also present a combined version of the cloning and cross-entropy (CE) algorithms. We prove
the polynomial complexity of a particular version of the Gibbs cloner for counting. We finally present efficient numerical
results with the Gibbs cloner and the combined version, while solving quite general integer and combinatorial optimization
problems as well as counting ones, like SAT. 相似文献
8.
Rade T. Živaljević 《Discrete and Computational Geometry》2009,41(1):135-161
This paper lays the foundation for a theory of combinatorial groupoids that allows us to use concepts like “holonomy”, “parallel transport”, “bundles”, “combinatorial curvature”, etc. in the context
of simplicial (polyhedral) complexes, posets, graphs, polytopes and other combinatorial objects. We introduce a new, holonomy-type
invariant for cubical complexes, leading to a combinatorial “Theorema Egregium” for cubical complexes that are non-embeddable
into cubical lattices. Parallel transport of Hom-complexes and maps is used as a tool to extend Babson–Kozlov–Lovász graph coloring results to more general statements about
nondegenerate maps (colorings) of simplicial complexes and graphs.
The author was supported by grants 144014 and 144026 of the Serbian Ministry of Science and Technology. 相似文献
9.
In this paper, we study the inverse problem of submodular functions on digraphs. Given a feasible solution x* for a linear program generated by a submodular function defined on digraphs, we try to modify the coefficient vector c of the objective function, optimally and within bounds, such that x* becomes an optimal solution of the linear program. It is shown that the problem can be formulated as a combinatorial linear program and can be transformed further into a minimum cost circulation problem. Hence, it can be solved in strongly polynomial time. We also give a necessary and sufficient condition for the feasibility of the problem. Finally, we extend the discussion to the version of the inverse problem with multiple feasible solutions. 相似文献
10.
Endre Boros Peter L. Hammer Toshihide Ibaraki Alexander Kogan 《Mathematical Programming》1997,79(1-3):163-190
“Logical analysis of data” (LAD) is a methodology developed since the late eighties, aimed at discovering hidden structural
information in data sets. LAD was originally developed for analyzing binary data by using the theory of partially defined
Boolean functions. An extension of LAD for the analysis of numerical data sets is achieved through the process of “binarization”
consisting in the replacement of each numerical variable by binary “indicator” variables, each showing whether the value of
the original variable is above or below a certain level. Binarization was successfully applied to the analysis of a variety
of real life data sets. This paper develops the theoretical foundations of the binarization process studying the combinatorial
optimization problems related to the minimization of the number of binary variables. To provide an algorithmic framework for
the practical solution of such problems, we construct compact linear integer programming formulations of them. We develop
polynomial time algorithms for some of these minimization problems, and prove NP-hardness of others.
The authors gratefully acknowledge the partial support by the Office of Naval Research (grants N00014-92-J1375 and N00014-92-J4083). 相似文献
11.
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. 相似文献
12.
L. G. Khachiyan recently published a polynomial algorithm to check feasibility of a system of linear inequalities. The method
is an adaptation of an algorithm proposed by Shor for non-linear optimization problems. In this paper we show that the method
also yields interesting results in combinatorial optimization. Thus it yields polynomial algorithms for vertex packing in
perfect graphs; for the matching and matroid intersection problems; for optimum covering of directed cuts of a digraph; for
the minimum value of a submodular set function; and for other important combinatorial problems. On the negative side, it yields
a proof that weighted fractional chromatic number is NP-hard.
Research by the third author was supported by the Netherlands Organisation for the Advancement of Pure Research (Z.W.O.). 相似文献
13.
We describe a simple algorithm to obtain a catalogue of 3-bridge links by computer, depending upon 6-tuples of positive integers.
This permits us to represent the genus two 3-manifolds by standardly constructed graphs with colored edges. Finally, we prove
some results about the topological structure of these manifolds and extend the combinatorial representation ton-bridge links
This work was performed under the auspices of the GNSAGA of the CNR (National Research Council) of Italy and financially supported
by the Ministero della Universitá e della Ricerca Scientifica e Tecnologica of Italy within the project “Geometria Reale e
Complessa”. 相似文献
14.
This paper presents a faster algorithm for the M-convex submodular flow problem, which is a generalization of the minimum-cost flow problem with an M-convex cost function for the flow-boundary, where an M-convex function is a nonlinear nonseparable discrete convex function on integer points. The algorithm extends the capacity scaling approach for the submodular flow problem by Fleischer, Iwata and McCormick (2002) with the aid of a novel technique of changing the potential by solving maximum submodular flow problems.Mathematics Subject Classification (1991): 90C27A preliminary version of this paper has appeared in Proceedings of the Tenth International Conference on Integer Programming and Combinatorial Optimization (IPCO X), LNCS 3064, Springer-Verlag, 2004, pp. 352–367. 相似文献
15.
On submodular function minimization 总被引:8,自引:0,他引:8
William H. Cunningham 《Combinatorica》1985,5(3):185-192
Earlier work of Bixby, Cunningham, and Topkis is extended to give a combinatorial algorithm for the problem of minimizing
a submodular function, for which the amount of work is bounded by a polynomial in the size of the underlying set and the largest
function value (not its length).
Research partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada. 相似文献
16.
Satoru Iwata 《Combinatorica》1995,15(4):515-532
This paper discusses the principal structure of submodular systems due to S. Fujishige. It is shown that the principal structure is the coarsest decomposition that is finer than any decomposition induced by the principal partition with respect to a minimal nonnegative superbase. The concept of Hitchcock-type independent flow is introduced so that previously known results on the principal structures for bipartite matchings, layered mixed matrices and independent matchings can be understood as applications of the present result. 相似文献
17.
Anatoly Libgober 《manuscripta mathematica》2009,128(1):1-31
We show that closures of families of unitary local systems on quasiprojective varieties for which the dimension of a graded
component of Hodge filtration has a constant value can be identified with a finite union of polytopes. We also present a local
version of this theorem. This yields the “Hodge decomposition” of the set of unitary local systems with a non-vanishing cohomology
extending Hodge decomposition of characteristic varieties of links of plane curves studied by the author earlier. We consider
a twisted version of the characteristic varieties generalizing the twisted Alexander polynomials. Several explicit calculations
for complements to arrangements are made.
A. Libgober was supported by National Science Foundation grant. 相似文献
18.
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. 相似文献
19.
Global Rank Axioms for Poset Matroids 总被引:2,自引:0,他引:2
ShuChaoLI YanQinFENG 《数学学报(英文版)》2004,20(3):507-514
An excellent introduction to the topic of poset matroids is due to Barnabei, Nicoletti and Pezzoli. In this paper, we investigate the rank axioms for poset matroids; thereby we can characterize poset matroids in a “global” version and a “pseudo-global” version. Some corresponding properties of combinatorial schemes are also obtained. 相似文献
20.
J.-Y. Lin S. Schaible R.-L. Sheu 《Journal of Optimization Theory and Applications》2010,146(3):581-601
In this paper, we introduce a class of minimization problems whose objective function is the composite of an isotonic function
and finitely many ratios. Examples of an isotonic function include the max-operator, summation, and many others, so it implies
a much wider class than the classical fractional programming containing the minimax fractional program as well as the sum-of-ratios
problem. Our intention is to develop a generic “Dinkelbach-like” algorithm suitable for all fractional programs of this type.
Such an attempt has never been successful before, including an early effort for the sum-of-ratios problem. The difficulty
is now overcome by extending the cutting plane method of Barros and Frenk (in J. Optim. Theory Appl. 87:103–120, 1995). Based on different isotonic operators, various cuts can be created respectively to either render a Dinkelbach-like approach
for the sum-of-ratios problem or recover the classical Dinkelbach-type algorithm for the min-max fractional programming. 相似文献