Foundational ... or simply a curiosity (Guest Post by Vijay Vazirani)

(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 here and references mentioned therein; the latter are available on authors' web sites.