8 citations · 18 across the 4 of their papers we have counts for
4 papers · 1 filter
Improved Approximation Algorithms for Stochastic Matching
Marek Adamczyk, Fabrizio Grandoni, Joydeep Mukherjee
In this paper we consider the Stochastic Matching problem, which is motivated by applications in kidney exchange and online dating. We are given an undirected graph in which every…
On Min-Power Steiner Tree
Fabrizio Grandoni
In the classical (min-cost) Steiner tree problem, we are given an edge-weighted undirected graph and a set of terminal nodes. The goal is to compute a min-cost tree S which spans a…
Prizing on Paths: A PTAS for the Highway Problem
Fabrizio Grandoni, Thomas Rothvoss
In the highway problem, we are given an n-edge line graph (the highway), and a set of paths (the drivers), each one with its own budget. For a given assignment of edge weights (the…
Optimization with More than One Budget
Fabrizio Grandoni, Rico Zenklusen
A natural way to deal with multiple, partially conflicting objectives is turning all the objectives but one into budget constraints. Some classical polynomial-time optimization pro…