Academic
Publications
Generalized polymatroids and submodular flows

Generalized polymatroids and submodular flows,10.1007/BF01589418,Mathematical Programming,András Frank,Éva Tardos

Generalized polymatroids and submodular flows   (Citations: 69)
BibTex | RIS | RefWorks Download
Polyhedra related to matroids and sub- or supermodular functions play a central role in combinatorial optimization. The purpose of this paper is to present a unified treatment of the subject. The structure of generalized polymatroids and submodular flow systems is discussed in detail along with their close interrelation. In addition to providing several applications, we summarize many known results within this general framework.
Journal: Mathematical Programming , vol. 42, no. 1, pp. 489-563, 1988
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...For matchings it is known that two solutions are adjacent in the matching polytope if and only if their symmetric difference is an alternating cycle or path X . Analogously, two adjacent extreme points in the common basis polytope of two matroids can be characterized by a proper alternating cycle X in the corresponding exchangeability graph [8,14]...
    • ...Lemma 5 ([8,14]) Assume we have two matroids M1 = (E,F1), M2 = (E,F2) and two common bases X, Y ∈ F1 ∩ F2. Then X and Y are adjacent extreme points in the common basis polytope of M1 and M2 if and only if the following conditions hold:...

    André Bergeret al. Budgeted matching and budgeted matroid intersection via the gasoline p...

    • ...A nonempty set S RN is called a g-polymatroid [8] if S is given as...

    AKIYOSHI SHIOURA. ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION ...

    • ...For matchings it is known that two solutions are adjacent in the matching polytope if and only if their symmetric difference is an alternating cycle or path X. Analogously, two adjacent extreme points in the common basis polytope of two matroids can be characterized by a proper alternating cycle X in the corresponding exchangeability graph [4, 9]. The idea is to patch S1 according to a proper subpath X′ of X. This subpath X′ guarantees ...

    André Bergeret al. Budgeted Matching and Budgeted Matroid Intersection Via the Gasoline P...

    • ...Definition 2 (Frank and Tardos [6], p. 495) A polyhedron...
    • ...Here we refrain from giving the definition of the generalized polymatroid (or gpolymatroid); the reader is referred to [6], p. 501, or to [19], p. 845...
    • ...polymatroid, see [6], p. 507, and [19], p. 845; • maximizing a linear function over a g-polymatroid can be done by a greedy algorithm, see [6], p. 524...
    • ...polymatroid, see [6], p. 507, and [19], p. 845; • maximizing a linear function over a g-polymatroid can be done by a greedy algorithm, see [6], p. 524...

    Natalia V. Shakhlevichet al. Preemptive Scheduling on Uniform Parallel Machines with Controllable J...

    • ...Many efficient algorithms for the problem are known (e.g., [1, 10, 12])...
    • ...being recognized as a unified framework for tractable discrete optimization problems with reference to existing studies on submodular functions [6, 12, 21], generalized polymatroids [9, 10, 12], valuated matroids [4, 5, 26] and convex analysis [31]...

    Akihisa Tamura. Coordinatewise domain scaling algorithm for M-convex function minimiza...

Sort by: