Source author record

Manuel Aprile

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Discrete Mathematics math.CO math.OC

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

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 $rc(X)$ of $X$ as the least number of facets among all possible relaxations $Q$ of $X$ . The rational relaxation complexity $rc_\mathbb{Q}(X)$ restricts the definition of $rc(X)$ to rational polyhedra $Q$ . In this article, we focus on $X = Δ_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 $rc(Δ_d) \leq d$ for every $d \geq 5$ . That is, since $rc_{\mathbb{Q}}(Δ_d)=d+1$ , irrationality can reduce the minimal size of relaxations. This answers an open question posed by Kaibel and Weltge (Lower bounds on the size of integer programs without additional variables, Mathematical Programming, 154(1):407-425, 2015). Moreover, we prove the asymptotic statement $rc(Δ_d) \in O(\frac{d}{\sqrt{\log(d)}})$ , which shows that the ratio $rc(Δ_d)/rc_{\mathbb{Q}}(Δ_d)$ goes to $0$ , as $d\to \infty$ .

preprint2020arXiv

A simple 7/3-approximation algorithm for feedback vertex set in tournaments

We show that performing just one round of the Sherali-Adams hierarchy gives an easy 7/3-approximation algorithm for the Feedback Vertex Set (FVST) problem in tournaments. This matches the best deterministic approximation algorithm for FVST due to Mnich, Williams, and Végh, and is a significant simplification and runtime improvement of their approach.

preprint2020arXiv

Recognizing Cartesian products of matrices and polytopes

The 1-product of matrices $S_1 \in \mathbb{R}^{m_1 \times n_1}$ and $S_2 \in \mathbb{R}^{m_2 \times n_2}$ is the matrix in $\mathbb{R}^{(m_1+m_2) \times (n_1n_2)}$ whose columns are the concatenation of each column of $S_1$ with each column of $S_2$ . Our main result is a polynomial time algorithm for the following problem: given a matrix $S$ , is $S$ a 1-product, up to permutation of rows and columns? Our main motivation is a close link between the 1-product of matrices and the Cartesian product of polytopes, which goes through the concept of slack matrix. Determining whether a given matrix is a slack matrix is an intriguing problem whose complexity is unknown, and our algorithm reduces the problem to irreducible instances. Our algorithm is based on minimizing a symmetric submodular function that expresses mutual information in information theory. We also give a polynomial time algorithm to recognize a more complicated matrix product, called the 2-product. Finally, as a corollary of our 1-product and 2-product recognition algorithms, we obtain a polynomial time algorithm to recognize slack matrices of $2$ -level matroid base polytopes.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.