Strongly Polynomial Algorithm for the Intersection of a Line with a Polymatroid

Jean Fonlupt () and Alexandre Skoda ()
Additional contact information
Jean Fonlupt: CNRS et Université Pierre et Marie Curie (Paris 6), Equipe Combinatoire et Optimisation
Alexandre Skoda: CNRS et Université Pierre et Marie Curie (Paris 6), Equipe Combinatoire et Optimisation

Chapter 5 in Research Trends in Combinatorial Optimization, 2009, pp 69-85 from Springer

Abstract: Summary We present a new algorithm for the problem of determining the intersection of a half-line $\Delta_{u}=\{x\in \mathbb{R}^{N}\:|\:x=\lambda u\;\mathrm {for}\;\lambda \geq 0\}$ with a polymatroid. We then propose a second algorithm which generalizes the first algorithm and solves a parametric linear program. We prove that these two algorithms are strongly polynomial and that their running time is O(n 8+γ n 7) where γ is the time for an oracle call. The second algorithm gives a polynomial algorithm to solve the submodular function minimization problem and to compute simultaneously the strength of a network with complexity bound O(n 8+γ n 7).

Date: 2009
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-540-76796-1_5

Ordering information: This item can be ordered from
http://www.springer.com/9783540767961

DOI: 10.1007/978-3-540-76796-1_5

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().