Manuel Aprile
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Manuel Aprile has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Samuel Fiorini
Universite Libre de Bruxelles
5 shared publications - Tony Huynh
School of Mathematics, Monash University, Melbourne, Australia
5 shared publications Matthew Drescher
3 shared publications- Gwenaël Joret
Computer Science Department Université libre de Bruxelles Brussels Belgium
2 shared publications - Marco Di Summa
Dipartimento di Matematica “Tullio Levi-Civita”, Università degli Studi di Padova, Padua, Italy
2 shared publications - Michele Conforti
Dipartimento di Matematica “Tullio Levi-Civita”, Università degli Studi Padova, Padova, Italy
2 shared publications
Latest Publications
- 9 June 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Integer Programs with Nearly Totally Unimodular Matrices: The Cographic Case
It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant [ ] in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix. Our approach focuses on the case in which A arises from M after removing k rows only and k is a constant. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory. First, we derive a strong proximity result for the case in which A is a general totally unimodular matrix: given an optimal solution of the linear programming relaxation, an optimal solution to the IP can be obtained by finding a constant number of augmentations by circuits of [ ]. Second, for the case in which A is the transpose of a network matrix, we reformulate the problem as a maximum constrained integer potential problem on a graph G. We observe that, if G is two-connected, then it has no rooted [ ]-minor for [ ]. We leverage this to obtain a tree-decomposition of G into highly structured graphs for which we can solve the problem locally. This allows us to solve the global problem via dynamic programming. Funding: M. Aprile and S. Fiorini acknowledge funding from Fonds de la Recherche Scientifique (FNRS) through research project BD-DELTA [Grant PDR 20222190, 2021–24]. S. Fiorini was also funded by the King Baudouin Foundation through project BD-DELTA-2 (convention 2023-F2150080-233051, 2023–26). G. Joret and M. Seweryn acknowledge funding from FNRS (PDR “Product structure of planar graphs”). S. Kober and S. Weltge were supported by the Deutsche Forschungsgemeinschaft (German Research Foundation) [Grants 277991500/GRK2201 and 451026932, respectively]. Y. Yuditsky was supported by FNRS as a postdoctoral researcher.
- 9 June 2026
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
Integer Programs with Nearly Totally Unimodular Matrices: The Cographic Case
It is a notorious open question whether integer programs (IPs) with an integer coefficient matrix M whose subdeterminants are all bounded by a constant [ ] in absolute value can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains a submatrix A that is the transpose of a network matrix. Our approach focuses on the case in which A arises from M after removing k rows only and k is a constant. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory. First, we derive a strong proximity result for the case in which A is a general totally unimodular matrix: given an optimal solution of the linear programming relaxation, an optimal solution to the IP can be obtained by finding a constant number of augmentations by circuits of [ ]. Second, for the case in which A is the transpose of a network matrix, we reformulate the problem as a maximum constrained integer potential problem on a graph G. We observe that, if G is two-connected, then it has no rooted [ ]-minor for [ ]. We leverage this to obtain a tree-decomposition of G into highly structured graphs for which we can solve the problem locally. This allows us to solve the global problem via dynamic programming. Funding: M. Aprile and S. Fiorini acknowledge funding from Fonds de la Recherche Scientifique (FNRS) through research project BD-DELTA [Grant PDR 20222190, 2021–24]. S. Fiorini was also funded by the King Baudouin Foundation through project BD-DELTA-2 (convention 2023-F2150080-233051, 2023–26). G. Joret and M. Seweryn acknowledge funding from FNRS (PDR “Product structure of planar graphs”). S. Kober and S. Weltge were supported by the Deutsche Forschungsgemeinschaft (German Research Foundation) [Grants 277991500/GRK2201 and 451026932, respectively]. Y. Yuditsky was supported by FNRS as a postdoctoral researcher.
- 1 August 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (3) , 1566-1581
Binary Extended Formulations and Sequential Convexification
- 1 August 2024
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 49 (3) , 1566-1581
Binary Extended Formulations and Sequential Convexification
- 23 February 2024
- Published by Springer Nature
- p. 29-40
Exact Approaches for the Connected Vertex Cover Problem
- 23 February 2024
- Published by Springer Nature
- p. 29-40
Exact Approaches for the Connected Vertex Cover Problem
- Open Access
- 13 July 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 205 (1-2) , 745-771
The role of rationality in integer-programming relaxations
For a finite set $$X \subset \mathbb {Z}^d$$ that can be represented as $$X = Q \cap \mathbb {Z}^d$$ for some polyhedron Q, we call Q a relaxation of X and define the relaxation complexity $${\text {rc}}(X)$$ of X as the least number of facets among all possible relaxations Q of X. The rational relaxation complexity $${\text {rc}}_\mathbb {Q}(X)$$ restricts the definition of $${\text {rc}}(X)$$ to rational polyhedra Q. In this article, we focus on $$X = \Delta _d$$ , the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in $$\mathbb {R}^d$$ . We show that $${\text {rc}}(\Delta _d) \le d$$ for every $$d \ge 5$$ . That is, since $${\text {rc}}_\mathbb {Q}(\Delta _d)=d+1$$ , irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Math Program 154(1):407–425, 2015). Moreover, we prove the asymptotic statement $${\text {rc}}(\Delta _d) \in O(\nicefrac {d}{\sqrt{\log (d)}})$$ , which shows that the ratio $$\nicefrac {{\text {rc}}(\Delta _d)}{{\text {rc}}_\mathbb {Q}(\Delta _d)}$$ goes to 0, as $$d \rightarrow \infty $$ .- 13 July 2023
- Published by Springer Nature in Mathematical Programming
- Vol. 205 (1-2) , 745-771
Open AccessThe role of rationality in integer-programming relaxations
For a finite set $$X \subset \mathbb {Z}^d$$ that can be represented as $$X = Q \cap \mathbb {Z}^d$$ for some polyhedron Q, we call Q a relaxation of X and define the relaxation complexity $${\text {rc}}(X)$$ of X as the least number of facets among all possible relaxations Q of X. The rational relaxation complexity $${\text {rc}}_\mathbb {Q}(X)$$ restricts the definition of $${\text {rc}}(X)$$ to rational polyhedra Q. In this article, we focus on $$X = \Delta _d$$ , the vertex set of the standard simplex, which consists of the null vector and the standard unit vectors in $$\mathbb {R}^d$$ . We show that $${\text {rc}}(\Delta _d) \le d$$ for every $$d \ge 5$$ . That is, since $${\text {rc}}_\mathbb {Q}(\Delta _d)=d+1$$ , irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Math Program 154(1):407–425, 2015). Moreover, we prove the asymptotic statement $${\text {rc}}(\Delta _d) \in O(\nicefrac {d}{\sqrt{\log (d)}})$$ , which shows that the ratio $$\nicefrac {{\text {rc}}(\Delta _d)}{{\text {rc}}_\mathbb {Q}(\Delta _d)}$$ goes to 0, as $$d \rightarrow \infty $$ . - Open Access
- 19 May 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 337, 149-160
A -approximation algorithm for feedback vertex set in tournaments via Sherali–Adams- 19 May 2023
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 337, 149-160
Open AccessA -approximation algorithm for feedback vertex set in tournaments via Sherali–Adams - Open Access
Exact approaches for the Connected Vertex Cover problem
Given a graph $G$, the Connected Vertex Cover problem (CVC) asks to find a minimum cardinality vertex cover of $G$ that induces a connected subgraph. In this paper we describe some approaches to solve the CVC problem exactly. First, we give compact mixed-integer extended formulations for CVC: these are the first formulations proposed for this problem, and can be easily adapted to variations of the problem such as Tree Cover. Second, we describe a simple branch and bound algorithm for the CVC problem. Finally, we implement our algorithm and compare its performance against our best formulation: contrary to what usually happens for the classical Vertex Cover problem, our formulation outperforms the branch and bound algorithm.Open AccessExact approaches for the Connected Vertex Cover problem
Given a graph $G$, the Connected Vertex Cover problem (CVC) asks to find a minimum cardinality vertex cover of $G$ that induces a connected subgraph. In this paper we describe some approaches to solve the CVC problem exactly. First, we give compact mixed-integer extended formulations for CVC: these are the first formulations proposed for this problem, and can be easily adapted to variations of the problem such as Tree Cover. Second, we describe a simple branch and bound algorithm for the CVC problem. Finally, we implement our algorithm and compare its performance against our best formulation: contrary to what usually happens for the classical Vertex Cover problem, our formulation outperforms the branch and bound algorithm. - 23 August 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 354, 199-213
Slack matrices, -products, and 2-level polytopes- 23 August 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 354, 199-213
Slack matrices, -products, and 2-level polytopes- 1 February 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 540-559
Regular Matroids Have Polynomial Extension Complexity
We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n6). Past results of Wong and Martin on extended formulations of the spanning tree po...
- 1 February 2022
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 47 (1) , 540-559
Regular Matroids Have Polynomial Extension Complexity
We prove that the extension complexity of the independence polytope of every regular matroid on n elements is O(n6). Past results of Wong and Martin on extended formulations of the spanning tree po...
- 29 January 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (2) , 145-149
Extended formulations for matroid polytopes through randomized protocols
- 29 January 2022
- Published by Elsevier in Operations Research Letters
- Vol. 50 (2) , 145-149
Extended formulations for matroid polytopes through randomized protocols
- 7 January 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1069-1091
A tight approximation algorithm for the cluster vertex deletion problem
- 7 January 2022
- Published by Springer Nature in Mathematical Programming
- Vol. 197 (2) , 1069-1091
A tight approximation algorithm for the cluster vertex deletion problem