| Tartalom: |
http://real.mtak.hu/28213/ |
| Archívum: |
MTA Könyvtár |
| Gyűjtemény: |
Status = Submitted
Type = Article
|
| Cím: |
Minimizing Submodular Functions on Diamonds via Generalized Fractional Matroid Matchings
|
| Létrehozó: |
Fujishige, Satoru
Király, Tamás
Makino, Kazuhisa
Takazawa, Kenjiro
Tanigawa, Shin-ichi
|
| Dátum: |
2014
|
| Téma: |
QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
|
| Tartalmi leírás: |
In this paper we show the first polynomial-time algorithm for the problem of minimizing submodular functions on the product of diamonds. This submodular function minimization problem is reduced to the membership problem for an associated polyhedron, which is equivalent to the optimization problem over the polyhedron, based on the ellipsoid method. The latter optimization problem is solved by polynomial number of solutions of subproblems, each being a generalization of the weighted fractional matroid matching problem. We give a combinatorial polynomial-time algorithm for this optimization problem by extending the result by Gijswijt and Pap [D.~Gijswijt and G.~Pap, An algorithm for weighted fractional matroid matching, J. Combin. Theory, Ser.~B 103 (2013), 509--520].
|
| Típus: |
Article
NonPeerReviewed
|
| Formátum: |
text
|
| Azonosító: |
Fujishige, Satoru and Király, Tamás and Makino, Kazuhisa and Takazawa, Kenjiro and Tanigawa, Shin-ichi (2014) Minimizing Submodular Functions on Diamonds via Generalized Fractional Matroid Matchings. JOURNAL OF COMBINATORIAL THEORY SERIES B. ISSN 0095-8956 (Submitted)
|
| Kapcsolat: |
|
