(Guest Post by Vijay Vazirani)
Foundational ... or Simply a Curiosity?
Conventional wisdom has it that whereas linear programs have
rational solutions, nonlinear programs have irrational ones.
The discovery, in recent years, of increasing numbers of nonlinear
convex programs that always admit rational solutions is challenging
this long-held viewpoint. Furthermore, these convex programs
capture the solutions to some fundamental problems in mathematical
economics and game theory, e.g., market equilibrium under linear utilities.
As if that were not enough, these convex programs also admit
combinatorial polynomial time algorithms for computing their
(exact) optimal solutions; very recently, even strongly polynomial
algorithms have been found. I am writing this guest post at the
suggestion of several people who were not aware of these developments.
The main question that arises is: Is this phenomenon simply a curiosity or is it indicative of a grand, new chapter
in the theory of algorithms? Let me put forth some reasons to believe that the latter may be the case.
Most of us are familiar with the notion of integral LP's -- LP's that behave like integer programs, in that they always
admit integral optimal solutions -- and the key role they played in the birth and blossoming of combinatorial optimization.
Indeed, some of the most elegant and foundational algorithms (e.g., for matching and max-flow) and algorithmic ideas
(including the notion of polynomial time solvability) were discovered within this field.
Of course, not every combinatorial optimization problem admits such an LP; in particular, none of the NP-hard ones do.
The latter were tackled via LP's that admit near-optimal integral solutions; their study lies at the core of the
field of approximation algorithms. Again, it is remarkable that for many fundamental problems, their hardness of
approximation is captured exactly as the integrality gap of such an LP (or SDP).
In view of this larger picture, and the clean, canonical and elaborate structure that was exploited in obtaining the
combinatorial algorithms, the discovery of rational convex programs seems more than a curiosity, though only time will tell.
However, rational convex programs are not likely to be found for more than a couple of handfuls of problems, as was the case
for integral LP's. If so, where does this take us?
My best guess at present is that we need to seek combinatorial algorithms for finding near-optimal rational solutions
to nonlinear convex programs; the motivation being that as always, we expect such algorithms to yield a wealth of
valuable insights. In the past, such insights were crucially used for advancing the theories mentioned above. Once again,
only time will tell if this is the right way of building on rational convex programs -- and of course, we should not
forget that mathematics has its own agenda and its own ways of throwing surprises at us!
For further information, please see the introduction to the following paper
and references mentioned therein; the latter are available on authors' web sites.