At the first conference (at DIMACS), it became clear that linear, or convex, programming is going to play a key role in the algorithmics of "discrete tomography", where one attempts to reconstruct a finite subset, $S$, of the integer lattice, $Z^2$, or $Z^3$, from its line sums in a few directions obtained via transmission electron microscopy. The usual convolution-back-projection algorithms for continuous tomography are useless for this new application to crystal microscopy because only very few directions are available for which the line sums are measured. Since the problem of determining a subset $S$ with the given line sums is an integer programming problem the standard convexification of the problem reduces it to linear programming (Peter Fishburn, Peter Schwander, Robert Vanderbei, The Discrete Radon Transform and its Approximate Inversion via Linear programming, Discrete Applied Math., 1997, to appear). This showed that $S$ may be "effectively" reconstructed in the sense that the method of finding a feasible interior point in the convex hull of what is called "fuzzy sets", ie a function, $0 \le f(z) \le 1$ for all $z \in Z^2$, or $Z^3$, "typically" produces a reasonablly satisfactory reconstruction on simulated phantoms. Thus the situation is more or less analogous to conventional medical CT scanning, where even though one cannot hope to uniquely reconstruct a function, $f(x,y)$ from its line integrals in a finite number of fixed directions (even if the line integrals are noiseless) the usual algoorithms are seen to work well, as demonstrated via simulations.
In the above paper written over a year ago, available by request at
fish@research.att.com, the method is made clear. Here however I have a
different goal: several disparate problems in applied mathematics can be
solved via non-trivial use of infinite linear programming and I thought
that I would share these with the audience in order to illustrate the scope
and the power of linear programming and to bring the ideas to wider view,
after first trying to set into perspective the application of linear
programming to discrete tomography via a review.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-67.ps.gz
DIMACS Home Page