[Winter 1999 Colloquiums]
[Department Homepage]

COLLOQUIUM

DEPARTMENT OF MATHEMATICS AND STATISTICS
OAKLAND UNIVERSITY
ROCHESTER, MICHIGAN 48309

Sven de Vries
Department of Mathematics
Technical University of München

Approximating Binary Images
From Discrete X-rays

Abstract

We study the problem of approximating and reconstructing binary images that are only accessible through few evaluations of their discrete X-ray transform, i.e., through their projections counted with multiplicity along some lines. This inverse discrete problem­with important applications to the semiconductor industry­belongs to a class of generalized set partitioning problems and allows natural packing and covering relaxations. For these (in most cases NP-hard) optimization problems we present various approximation algorithms and provide tight estimates for their worst case performance. Further, we report on computational results for various variants of these algorithms. In particular, the corresponding integer programs are solved with only small absolute error for instances up to 250000 binary variables.

372 Science and Engineering Building
Tuesday, May 18,1999
3:00­4:00 P.M.

Refreshments at 2:30­3:00 PM in Room 368, Science and Engineering Building