Marco Molinaro
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Marco Molinaro has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Eduardo Laber
PUC-Rio Brazil
3 shared publications - Ferdinando Cicalese
Department of Computer Science, University of Verona, Verona, Italy
3 shared publications - Gérard Cornuéjols
Carnegie Mellon University
2 shared publications - Tobias Jacobs
NEC Laboratories Europe
2 shared publications - Amitabh Basu
Department of Mathematics Davis University of California
1 shared publication - Eduardo Laber
PUC-Rio
1 shared publication
Latest Publications
- 1 September 2013
- Published by Elsevier in Operations Research Letters
- Vol. 41 (5) , 442-444
Cutting planes from two-term disjunctions
- 1 September 2013
- Published by Elsevier in Operations Research Letters
- Vol. 41 (5) , 442-444
Cutting planes from two-term disjunctions
- 1 March 2013
- Published by Elsevier in Operations Research Letters
- Vol. 41 (2) , 142-146
Lifting Gomory cuts with bounded variables
- 1 March 2013
- Published by Elsevier in Operations Research Letters
- Vol. 41 (2) , 142-146
Lifting Gomory cuts with bounded variables
- 16 November 2012
- Published by Springer Nature in Algorithmica
- Vol. 68 (4) , 1045-1074
Improved Approximation Algorithms for the Average-Case Tree Searching Problem
- 16 November 2012
- Published by Springer Nature in Algorithmica
- Vol. 68 (4) , 1045-1074
Improved Approximation Algorithms for the Average-Case Tree Searching Problem
- 12 June 2012
- Published by Springer Nature in Mathematical Programming
- Vol. 142 (1-2) , 83-105
A 3-Slope Theorem for the infinite relaxation in the plane
- 12 June 2012
- Published by Springer Nature in Mathematical Programming
- Vol. 142 (1-2) , 83-105
A 3-Slope Theorem for the infinite relaxation in the plane
- 25 November 2011
- Published by Elsevier in Theoretical Computer Science
- Vol. 412 (50) , 6879-6896
On the complexity of searching in trees and partially ordered structures
- 25 November 2011
- Published by Elsevier in Theoretical Computer Science
- Vol. 412 (50) , 6879-6896
On the complexity of searching in trees and partially ordered structures
- Open Access
The Query-commit Problem
In the query-commit problem we are given a graph where edges have distinct probabilities of existing. It is possible to query the edges of the graph, and if the queried edge exists then its endpoints are irrevocably matched. The goal is to find a querying strategy which maximizes the expected size of the matching obtained. This stochastic matching setup is motivated by applications in kidney exchanges and online dating. In this paper we address the query-commit problem from both theoretical and experimental perspectives. First, we show that a simple class of edges can be queried without compromising the optimality of the strategy. This property is then used to obtain in polynomial time an optimal querying strategy when the input graph is sparse. Next we turn our attentions to the kidney exchange application, focusing on instances modeled over real data from existing exchange programs. We prove that, as the number of nodes grows, almost every instance admits a strategy which matches almost all nodes. This result supports the intuition that more exchanges are possible on a larger pool of patient/donors and gives theoretical justification for unifying the existing exchange programs. Finally, we evaluate experimentally different querying strategies over kidney exchange instances. We show that even very simple heuristics perform fairly well, being within 1.5% of an optimal clairvoyant strategy, that knows in advance the edges in the graph. In such a time-sensitive application, this result motivates the use of committing strategies.
Open AccessThe Query-commit Problem
In the query-commit problem we are given a graph where edges have distinct probabilities of existing. It is possible to query the edges of the graph, and if the queried edge exists then its endpoints are irrevocably matched. The goal is to find a querying strategy which maximizes the expected size of the matching obtained. This stochastic matching setup is motivated by applications in kidney exchanges and online dating. In this paper we address the query-commit problem from both theoretical and experimental perspectives. First, we show that a simple class of edges can be queried without compromising the optimality of the strategy. This property is then used to obtain in polynomial time an optimal querying strategy when the input graph is sparse. Next we turn our attentions to the kidney exchange application, focusing on instances modeled over real data from existing exchange programs. We prove that, as the number of nodes grows, almost every instance admits a strategy which matches almost all nodes. This result supports the intuition that more exchanges are possible on a larger pool of patient/donors and gives theoretical justification for unifying the existing exchange programs. Finally, we evaluate experimentally different querying strategies over kidney exchange instances. We show that even very simple heuristics perform fairly well, being within 1.5% of an optimal clairvoyant strategy, that knows in advance the edges in the graph. In such a time-sensitive application, this result motivates the use of committing strategies.
- Open Access
A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.
Open AccessA (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation
We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.
- Open Access
On the Complexity of Searching in Trees: Average-case Minimization
We focus on the average-case analysis: A function w : V -> Z+ is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the expected number of queries. Prior to this paper, very little was known about this natural question and the complexity of the problem had remained so far an open question. We close this question and prove that the above tree search problem is NP-complete even for the class of trees with diameter at most 4. This results in a complete characterization of the complexity of the problem with respect to the diameter size. In fact, for diameter not larger than 3 the problem can be shown to be polynomially solvable using a dynamic programming approach. In addition we prove that the problem is NP-complete even for the class of trees of maximum degree at most 16. To the best of our knowledge, the only known result in this direction is that the tree search problem is solvable in O(|V| log|V|) time for trees with degree at most 2 (paths). We match the above complexity results with a tight algorithmic analysis. We first show that a natural greedy algorithm attains a 2-approximation. Furthermore, for the bounded degree instances, we show that any optimal strategy (i.e., one that minimizes the expected number of queries) performs at most O(\Delta(T) (log |V| + log w(T))) queries in the worst case, where w(T) is the sum of the likelihoods of the nodes of T and \Delta(T) is the maximum degree of T. We combine this result with a non-trivial exponential time algorithm to provide an FPTAS for trees with bounded degree.
Open AccessOn the Complexity of Searching in Trees: Average-case Minimization
We focus on the average-case analysis: A function w : V -> Z+ is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the expected number of queries. Prior to this paper, very little was known about this natural question and the complexity of the problem had remained so far an open question. We close this question and prove that the above tree search problem is NP-complete even for the class of trees with diameter at most 4. This results in a complete characterization of the complexity of the problem with respect to the diameter size. In fact, for diameter not larger than 3 the problem can be shown to be polynomially solvable using a dynamic programming approach. In addition we prove that the problem is NP-complete even for the class of trees of maximum degree at most 16. To the best of our knowledge, the only known result in this direction is that the tree search problem is solvable in O(|V| log|V|) time for trees with degree at most 2 (paths). We match the above complexity results with a tight algorithmic analysis. We first show that a natural greedy algorithm attains a 2-approximation. Furthermore, for the bounded degree instances, we show that any optimal strategy (i.e., one that minimizes the expected number of queries) performs at most O(\Delta(T) (log |V| + log w(T))) queries in the worst case, where w(T) is the sum of the likelihoods of the nodes of T and \Delta(T) is the maximum degree of T. We combine this result with a non-trivial exponential time algorithm to provide an FPTAS for trees with bounded degree.
- 20 May 2009
- Published by Springer Nature in Algorithmica
- Vol. 59 (4) , 601-620
An Approximation Algorithm for Binary Searching in Trees
- 20 May 2009
- Published by Springer Nature in Algorithmica
- Vol. 59 (4) , 601-620
An Approximation Algorithm for Binary Searching in Trees