Accession Number:
ADA329831
Title:
Geometric Tools for Algorithms.
Descriptive Note:
Doctoral thesis,
Corporate Author:
CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE
Personal Author(s):
Report Date:
1997-08-01
Pagination or Media Count:
85.0
Abstract:
Our thesis is that a geometric perspective yields insights into the structure of fundamental problems, and thereby suggests efficient algorithms for them. As evidence we develop new geometric models and general-purpose tools for removing outliers from numeric data, reducing dimensionality, and counting combinatorial sets. Then we apply these techniques to a set of old problems to obtain polynomial-time algorithms. These include 1 learning noisy linear-threshold functions half-spaces, 2 learning the intersection of halfspaces, 3 clustering text corpora, and 4 counting lattice points in a convex body. We supplement some of our theorems with experimental studies.
Descriptors:
Subject Categories:
- Operations Research