Login

Publications  •  Project Statistics

Glossary  •  Schools  •  Disciplines
People Search: 
   
Title/Abstract Search: 

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