التفاصيل البيبلوغرافية
| العنوان: |
Polyhedral Properties of the K-median Problem on a Tree. |
| المؤلفون: |
Vries, Sven1 devries@ma.tum.de, Posner, Marc2 posner.1@kellogg.northwestern.edu, Vohra, Rakesh3 r-vohra@kellogg.northwestern.edu |
| المصدر: |
Mathematical Programming. Jul2007, Vol. 110 Issue 2, p261-285. 25p. 3 Diagrams. |
| مصطلحات موضوعية: |
*GRAPHIC methods, *INTEGER programming, POLYHEDRA, MEDIAN (Mathematics), TREE graphs, POLYTOPES |
| مستخلص: |
The polyhedral structure of the K-median problem on a tree is examined. Even for very small connected graphs, we show that additional constraints are needed to describe the integer polytope. A complete description is given of those trees for which an optimal integer LP solution is guaranteed to exist. We present a new and simpler demonstration that an LP characterization of the 2-median problem is complete. Also, we provide a simpler proof of the value of a tight worst case bound for the LP relaxation. A new class of valid inequalities is identified. These inequalities describe a subclass of facets for the K-median problem on a general graph. Also, we provide polyhedral descriptions for several types of trees. As part of this work, we summarize most known results for the K-median problem on a tree. [ABSTRACT FROM AUTHOR] |
|
Copyright of Mathematical Programming is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Business Source Index |
Full Text Finder