2 papers
cs.DS2021
New instances for maximum weight independent set from a vehicle routing application
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe +3
We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve…
cs.DS2018
DISPATCH: An Optimally-Competitive Algorithm for Maximum Online Perfect Bipartite Matching with i.i.d. Arrivals
Minjun Chang, Dorit S. Hochbaum, Quico Spaen +1
This work presents an optimally-competitive algorithm for the problem of maximum weighted online perfect bipartite matching with i.i.d. arrivals. In this problem, we are given a kn…