|
|
|
|
|
|
|
|
|
|
|
Publications - The complexity of the Kth largest subset problem and related problems
|
|
|
|
|
Reference:
Christoph Haase and Stefan Kiefer. The complexity of the th largest subset problem and related problems. Information Processing Letters (IPL), 116(2):111–115, 2016.
Abstract:
We show that the th largest subset problem and the th largest -tuple problem are in PP and hard for PP under polynomial-time Turing reductions. Several problems from the literature were previously shown NP-hard via reductions from those two problems, and by our main result they become PP-hard as well. We also provide complementary PP-upper bounds for some of them.
Suggested BibTeX entry:
@article{16HK-IPL,
author = {Christoph Haase and Stefan Kiefer},
journal = {Information Processing Letters (IPL)},
number = {2},
pages = {111--115},
publisher = {Elsevier},
title = {The complexity of the ${K}$th largest subset problem and related problems},
volume = {116},
year = {2016}
}
|
|
|
|
|
|
|
|
|
|