Showing cs.DSShow all
2 papers · 1 filter
cs.DS2026
Settling the Approximability of Submodular Facility Location
Adam N. Elmachtoub, Bento Natura, Meike Neuwohner
In submodular facility location (SFL), introduced by Svitkina and Tardos (SODA 2006), clients in a metric space are assigned to facilities . A facility serving a s…
cs.DS2020
An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
Daniel Dadush, Zhuan Khye Koh, Bento Natura +1
We present an accelerated, or 'look-ahead' version of the Newton-Dinkelbach method, a well-known technique for solving fractional and parametric optimization problems. This acceler…