no. 4
Bounded-degree rooted tree and TDI-ness
RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2181-2201

This paper contributes to the polyhedral aspect of the Maximum-Weight Bounded-Degree Rooted Tree Problem, where only edge-indexed variables are considered. An initial formulation is given, followed by an analysis of the dimension and a facial study for the polytope. Several families of new valid inequalities are proposed, which enables us to characterize the polytope on trees and cycles with a totally dual integral system.

DOI : 10.1051/ro/2022101
Classification : 05C85, 52B05, 68R05, 68W01
Keywords: Bounded-Degree Rooted Tree, polytope, facets, Total Dual Integrality 
@article{RO_2022__56_4_2181_0,
     author = {Kerivin, Herve L. M. and Zhao, Jinhua},
     title = {Bounded-degree rooted tree and {TDI-ness}},
     journal = {RAIRO. Operations Research},
     pages = {2181--2201},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {4},
     doi = {10.1051/ro/2022101},
     mrnumber = {4454166},
     zbl = {1497.05039},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022101/}
}
TY  - JOUR
AU  - Kerivin, Herve L. M.
AU  - Zhao, Jinhua
TI  - Bounded-degree rooted tree and TDI-ness
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 2181
EP  - 2201
VL  - 56
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022101/
DO  - 10.1051/ro/2022101
LA  - en
ID  - RO_2022__56_4_2181_0
ER  - 
%0 Journal Article
%A Kerivin, Herve L. M.
%A Zhao, Jinhua
%T Bounded-degree rooted tree and TDI-ness
%J RAIRO. Operations Research
%D 2022
%P 2181-2201
%V 56
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022101/
%R 10.1051/ro/2022101
%G en
%F RO_2022__56_4_2181_0
Kerivin, Herve L. M.; Zhao, Jinhua. Bounded-degree rooted tree and TDI-ness. RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2181-2201. doi: 10.1051/ro/2022101

[1] J. Chakareski, P. Frossard, H. Kerivin, J. Leblet and G. Simon, A note on the data-driven capacity of p2p networks. Technical Report EPFL-LTS-2009-008, École Polytechnique Fédérale de Lausanne, Switzerland (2009).

[2] M. Conforti, G. Cornuéjols and G. Zambelli, Extended formulations in combinatorial optimization. 4OR-Q J Oper. Res. 8 (2010) 1–48. | MR | Zbl | DOI

[3] G. B. Dantzig, D. R. Fulkerson and S. M. Johnson, Solution of a large-scale traveling salesman problem. Oper. Res. 2 (1954) 393–410. | MR | Zbl

[4] M. Didi Biha, H. Kerivin and A. R. Mahjoub, Steiner trees and polyhedra. Discrete Appl. Math. 112 (2001) 101–120. | MR | Zbl | DOI

[5] M. Didi Biha, H. L. M. Kerivin and P. H. Ng, Polyhedral study of the connected sugbraph problem. Discrete Math. 338 (2015) 80–92. | MR | Zbl | DOI

[6] R. Diestel, Graph Theory, 3rd edition. Springer-Verlag, Berlin Heidelberg (2006). | Zbl

[7] J. Edmonds and R. Giles, A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1 (1977) 185–204. | MR | Zbl | DOI

[8] M. Fürer and B. Raghavachari, Approximating the minimum-degree Steiner tree problem to within one of optimal. J. Algorithms 17 (1994) 409–423. | MR | Zbl | DOI

[9] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Company, New York (1979). | MR | Zbl

[10] M. X. Goemans, The Steiner tree polytope and related polyhedra. Math. Prog. 63 (1994) 157–182. | MR | Zbl | DOI

[11] K. Jain, A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica 21 (2001) 39–60. | MR | Zbl | DOI

[12] H. Kerivin and A. R. Mahjoub, Design of survivable networks: a survey. Networks 46 (2005) 1–21. | MR | Zbl | DOI

[13] H. Kerivin and J. Zhao, A computational study on the maximum-weight bounded-degree rooted tree problem. Appl. Math. Comput. 413 (2022) 126623. | MR | Zbl

[14] H. Kerivin, J. Leblet, G. Simon and F. Zhou, Maximum bounded rooted-tree packing problem. Preprint (2011). | arXiv

[15] T. Király, L. C. Lau and M. Singh, Degree bounded matroids and submodular flows. Combinatorica 32 (2012) 703–720. | MR | Zbl | DOI

[16] G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization. Wiley-Interscience, New York (1988). | MR | Zbl | DOI

[17] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, Berlin Heidelberg (2003). | MR | Zbl

[18] M. Singh and L. C. Lau, Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC) (2007) 661–670. | MR | Zbl

[19] C. Vinhas De Lima, Le Problème du Packing Borné Maximal de r-Arbre: Etude polyédrale pour le cas du graphe étoile avec 2 arbres. Master’s thesis, Institut Supérieur d’Informatique, de Modélisation et de leurs Applications (ISIMA) (2016).

[20] J. Zhao, Maximum bounded rooted-tree problem: algorithms and polyhedra. Ph.D. thesis, LIMOS, Université Clermont Auvergne (2017).

Cité par Sources :