8 citations · 30 across the 29 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.DS2013
New Approximability Results for the Robust k-Median Problem
Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn +1
We consider a robust variant of the classical -median problem, introduced by Anthony et al. \cite{AnthonyGGN10}. In the \emph{Robust -Median problem}, we are given an -ver…
cs.CC2013★ 8 cited
Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses
Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai
We present a series of almost settled inapproximability results for three fundamental problems. The first in our series is the subexponential-time inapproximability of the maximum…