2 papers
cs.DS2024
Quickly Determining Who Won an Election
Lisa Hellerstein, Naifeng Liu, Kevin Schewior
This paper considers elections in which voters choose one candidate each, independently according to known probability distributions. A candidate receiving a strict majority (absol…
cs.DS2022
Two 6-approximation Algorithms for the Stochastic Score Classification Problem
Naifeng Liu
We study the arbitrary cost case of the unweighted Stochastic Score Classification (SSClass) problem. We show two constant approximation algorithms and both algorithms are 6-approx…