Towards Combinatorial Min-Max Relations from Extended Linear Programming Formulations
Resumo
We study the concept of extended total dual integrality and the combinatorial min-max relations that can be derived from this notion. In this work, we prove the extended total dual integrality property for compact extended linear programming formulations for the minimum-cost r-arborescence problem and the maximum-weight perfectly matchable subset problem. From this, we derive dual integer programming problems and show how to solve each pair of primal-dual problems algorithmically and efficiently by adapting classical methods. We also provide a combinatorial interpretation to the dual problem of the minimum-cost r-arborescence problem as a distance splitting problem.Referências
Balas, E. and Pulleyblank, W. (1983). The perfectly matchable subgraph polytope of a bipartite graph. In Proceedings of the symposium on the matching problem: theory, algorithms, and applications (Gaithersburg, Md., 1981), volume 13, pages 495–516.
de Carli Silva, M. K. and Tunçel, L. (2020). A notion of total dual integrality for convex, semidefinite, and extended formulations. SIAM J. Discrete Math., 34(1):470–496.
Edmonds, J. (1973). Edge-disjoint branchings. In Combinatorial algorithms (Courant Comput. Sci. Sympos. 9, New York Univ., New York, 1972), pages 91–96. Algorithmics Press, New York.
Edmonds, J. and Giles, R. (1977). A min-max relation for submodular functions on graphs. In Studies in integer programming (Proc. Workshop, Bonn, 1975), Ann. Discrete Math., Vol. 1, pages 185–204. North-Holland.
Maculan, N. (1986). A new linear programming formulation for the shortest s-directed spanning tree problem. J. Combin. Inform. System Sci., 11(2-4):53–56.
Martin, R. K. (1991). Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett., 10(3):119–128.
Schrijver, A. (2003). Combinatorial optimization. Polyhedra and efficiency, volume 24 of Algorithms and Combinatorics. Springer-Verlag, Berlin.
Wong, R. T. (1984). A dual ascent approach for Steiner tree problems on a directed graph. Math. Program., 28(3):271–287.
de Carli Silva, M. K. and Tunçel, L. (2020). A notion of total dual integrality for convex, semidefinite, and extended formulations. SIAM J. Discrete Math., 34(1):470–496.
Edmonds, J. (1973). Edge-disjoint branchings. In Combinatorial algorithms (Courant Comput. Sci. Sympos. 9, New York Univ., New York, 1972), pages 91–96. Algorithmics Press, New York.
Edmonds, J. and Giles, R. (1977). A min-max relation for submodular functions on graphs. In Studies in integer programming (Proc. Workshop, Bonn, 1975), Ann. Discrete Math., Vol. 1, pages 185–204. North-Holland.
Maculan, N. (1986). A new linear programming formulation for the shortest s-directed spanning tree problem. J. Combin. Inform. System Sci., 11(2-4):53–56.
Martin, R. K. (1991). Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett., 10(3):119–128.
Schrijver, A. (2003). Combinatorial optimization. Polyhedra and efficiency, volume 24 of Algorithms and Combinatorics. Springer-Verlag, Berlin.
Wong, R. T. (1984). A dual ascent approach for Steiner tree problems on a directed graph. Math. Program., 28(3):271–287.
Publicado
20/07/2025
Como Citar
SILVA, Marcel K. de Carli; LESTON-REY, Mario; OLIVEIRA, Henri M. F.; SATO, Cristiane M..
Towards Combinatorial Min-Max Relations from Extended Linear Programming Formulations. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 10. , 2025, Maceió/AL.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2025
.
p. 36-40.
ISSN 2595-6116.
DOI: https://doi.org/10.5753/etc.2025.8198.
