Dissertation Information for Kirk Richard Pruhs NAME: - Kirk Richard Pruhs
DEGREE:
- Ph.D.
DISCIPLINE:
- Computer Science
SCHOOL:
- University of Wisconsin, Madison (USA) (1989)
ADVISORS: - Mary Vernon
COMMITTEE MEMBERS: - None
MPACT Status: Incomplete - Not_Inspected
Title: The complexity of controlled selection
Abstract: We identify a class of problems, called controlled selection problems, and study their complexity. A controlled selection problem involves an unbiased random selection of a sample from a large set, subject to certain structural constraints on the sample. Applications of controlled selection have been studied separately in many disciplines, such as survey research methods, fair allocation of resources, combinatorial optimization, computer networks, and mathematical programming. This is a first attempt at a unified examination of these problems.
We develop techniques for determining the complexity of a controlled selection problem, given the structural constraints. We first show how to translate a controlled selection problem into a polyhedral combinatorics problem. This allows us to employ existing results, from the theory of combinatorial optimization, to develop a general method for proving that a controlled selection problem has a polynomial-time algorithm. Unfortunately, the running times of the algorithms derived by this method are polynomials of high degree. For several controlled selection problems we are able to refine these algorithms, making them efficient in practice. We also develop techniques for proving that a controlled selection problem is hard. We demonstrate the effectiveness of these techniques by applying them to applications of controlled selection from many disciplines. We are able to explain why earlier attempts to solve several survey problems were unsuccessful by proving that these problems are NP-complete.
| |
MPACT Scores for Kirk Richard Pruhs A = 0
C = 2
A+C = 2
T = 0
G = 0
W = 0
TD = 0
TA = 0
calculated 2012-07-31 12:59:13
Advisors and Advisees Graph
|