4 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…
Reverse Split Rank
Michele Conforti, Alberto Del Pia, Marco Di Summa +1
The reverse split rank of an integral polyhedron P is defined as the supremum of the split ranks of all rational polyhedra whose integer hull is P. Already in R^3 there exist polyh…
On largest volume simplices and sub-determinants
Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza +1
We show that the problem of finding the simplex of largest volume in the convex hull of points in can be approximated with a factor of in polyn…