73 citations · 104 across the 30 of their papers we have counts for
32 papers
The Incremental Knapsack Problem with Monotone Submodular All-or-Nothing Profits
Federico D'Onofrio, Yuri Faenza, Lingyi Zhang
We study incremental knapsack problems with profits given by a special class of monotone submodular functions, that we dub all-or-nothing. We show that these problems are not harde…
Scarf's algorithm and stable marriages
Yuri Faenza, Chengyue He, Jay Sethuraman
Scarf's algorithm gives a pivoting procedure to find a special vertex -- a dominating vertex -- in down-monotone polytopes. This paper studies the behavior of Scarf's algorithm whe…
The Total Matching Polytope of Complete Bipartite Graphs
Yuri Faenza, Luca Ferrarini
The total matching polytope generalizes the stable set polytope and the matching polytope. In this paper, we first propose new facet-defining inequalities for the total matching po…
The Power of Greedy for Online Minimum Cost Matching on the Line
Eric Balkanski, Yuri Faenza, Noemie Perivier
We consider the online minimum cost matching problem on the line, in which there are servers and, at each of time steps, a request arrives and must be irrevocably matched t…
Discovering Opportunities in New York City's Discovery Program: Disadvantaged Students in Highly Competitive Markets
Yuri Faenza, Swati Gupta, Xuan Zhang
Discovery program (DISC) is a policy used by the New York City Department of Education (NYC DOE) to increase the number of admissions of students from low socio-economic background…
Slack matrices, -products, and -level polytopes
Manuel Aprile, Michele Conforti, Yuri Faenza +3
In this paper, we study algorithmic questions concerning products of matrices and their consequences for recognition algorithms for polyhedra. The 1-product of matrices , $S_2…