File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/s10878-017-0132-2
- Scopus: eid_2-s2.0-85018266893
- WOS: WOS:000412680800008
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: On the Langberg–Médard multiple unicast conjecture
Title | On the Langberg–Médard multiple unicast conjecture |
---|---|
Authors | |
Keywords | Multiple commodity flow Multiple unicast conjecture Nonsmooth optimization |
Issue Date | 2017 |
Publisher | Springer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905 |
Citation | Journal of Combinatorial Optimization, 2017, v. 34 n. 4, p. 1114-1132 How to Cite? |
Abstract | A version of the multiple unicast conjecture, proposed by Langberg and Médard (in: Proceedings of 47th annual Allerton, 2009), says that, there exists an undirected fractional multi-commodity flow, or simply, multi-flow, with rate (1,1,…,1) for strongly reachable networks. In this paper, we propose a nonsmooth matrix optimization problem to attack this conjecture: By giving upper and lower bounds on the objective value, we prove that there exists a multi-flow with rate at least (8/9,8/9,…,8/9) for such networks; on the other hand though, we show that the rate of any multi-flow constructed using this framework cannot exceed (1,1,…,1). |
Persistent Identifier | http://hdl.handle.net/10722/245055 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.370 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cai, K | - |
dc.contributor.author | Han, G | - |
dc.date.accessioned | 2017-09-18T02:03:49Z | - |
dc.date.available | 2017-09-18T02:03:49Z | - |
dc.date.issued | 2017 | - |
dc.identifier.citation | Journal of Combinatorial Optimization, 2017, v. 34 n. 4, p. 1114-1132 | - |
dc.identifier.issn | 1382-6905 | - |
dc.identifier.uri | http://hdl.handle.net/10722/245055 | - |
dc.description.abstract | A version of the multiple unicast conjecture, proposed by Langberg and Médard (in: Proceedings of 47th annual Allerton, 2009), says that, there exists an undirected fractional multi-commodity flow, or simply, multi-flow, with rate (1,1,…,1) for strongly reachable networks. In this paper, we propose a nonsmooth matrix optimization problem to attack this conjecture: By giving upper and lower bounds on the objective value, we prove that there exists a multi-flow with rate at least (8/9,8/9,…,8/9) for such networks; on the other hand though, we show that the rate of any multi-flow constructed using this framework cannot exceed (1,1,…,1). | - |
dc.language | eng | - |
dc.publisher | Springer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905 | - |
dc.relation.ispartof | Journal of Combinatorial Optimization | - |
dc.rights | The final publication is available at Springer via http://dx.doi.org/10.1007/s10878-017-0132-2 | - |
dc.subject | Multiple commodity flow | - |
dc.subject | Multiple unicast conjecture | - |
dc.subject | Nonsmooth optimization | - |
dc.title | On the Langberg–Médard multiple unicast conjecture | - |
dc.type | Article | - |
dc.identifier.email | Cai, K: kcai@hku.hk | - |
dc.identifier.email | Han, G: ghan@hku.hk | - |
dc.identifier.authority | Han, G=rp00702 | - |
dc.description.nature | postprint | - |
dc.identifier.doi | 10.1007/s10878-017-0132-2 | - |
dc.identifier.scopus | eid_2-s2.0-85018266893 | - |
dc.identifier.hkuros | 277982 | - |
dc.identifier.volume | 34 | - |
dc.identifier.issue | 4 | - |
dc.identifier.spage | 1114 | - |
dc.identifier.epage | 1132 | - |
dc.identifier.isi | WOS:000412680800008 | - |
dc.publisher.place | Netherlands | - |
dc.identifier.issnl | 1382-6905 | - |