| Presentation | 2015-12-01 [Invited Talk] Fiding a Stable Allocation in Polymatroid Intersection Satoru Iwata, Yu Yokoi, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The stable matching model of Gale and Shapley (1962) has been generalized in various directions such as matroid kernels due to Fleiner (2001) and stable allocations in bipartite networks due to Ba¨ ıou and Balinski (2002). In this talk, we introduce the concept of stable allocations in polymatroid intersection, which serves as a comprehensive framework that unifies these generalizations. We present a strongly polynomial algorithm for finding a stable allocation in polymatroid intersection. To achieve this, we utilize the augmenting path technique for polymatroid intersection. In each iteration, the algorithm searches for an augmenting path by simulating a chain of proposes and rejects in the deferred acceptance algorithm. The running time of our algorithm is $O(n^3gamma)$, where $n$ and $gamma$ respectively denote the cardinality of the ground set and the time for computing the saturation and exchange capacities. This talk is based on the authors’ paper that is to appear in Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms, January, 2016. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Stable matching / Polymatroid / Strongly polynomial algorithm |
| Paper # | COMP2015-34 |
| Date of Issue | 2015-11-24 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2015/12/1(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Koichi Wada(Hosei Univ.) |
| Vice Chair | Toshimitsu Masuzawa(Osaka Univ.) |
| Secretary | Toshimitsu Masuzawa(Hiroshima Univ.) |
| Assistant | |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | [Invited Talk] Fiding a Stable Allocation in Polymatroid Intersection |
| Sub Title (in English) | |
| Keyword(1) | Stable matching |
| Keyword(2) | Polymatroid |
| Keyword(3) | Strongly polynomial algorithm |
| 1st Author's Name | Satoru Iwata |
| 1st Author's Affiliation | Tokyo University(Univ. Tokyo) |
| 2nd Author's Name | Yu Yokoi |
| 2nd Author's Affiliation | Tokyo University(Univ. Tokyo) |
| Date | 2015-12-01 |
| Paper # | COMP2015-34 |
| Volume (vol) | vol.115 |
| Number (no) | COMP-344 |
| Page | pp.pp.25-25(COMP), |
| #Pages | 1 |
| Date of Issue | 2015-11-24 (COMP) |