Tuesday, June 22, 2010

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.


  1. What is a "combinatorial" algorithm? This seems like a silly distinction.

  2. Which field do you work in?
    If TCS, maybe your license needs to be revoked.

  3. Why do some convex programs have rational solutions? There must be some fundamental reason behind them.

    Geometrically, if there is a rational solution then one can find it (exactly) in polynomial time, so combinatorial algo should give some further insight.

    More broadly, is there a syntactic class of convex programs which have rational solutions, just like there are known classes of linear programs with integer solutions (e.g., totally unimodular matrices etc).

    In general, my guess is that whether a convex program is equivalent to a linear program should itself be a hard problem.

  4. How come so many people (me included) were
    unaware of this important development?

  5. How come so many people (me included) were
    unaware of this important development?

    Perhaps you are too mainstream? ;-)

    The blog post is an update/summary of a speech V. Vazirani gave at the end of ICS 2010, to encourage the audience to pursue this line of research. I didn't mention it in my guest blog posts here about ICS because I didn't (and still don't) really understand what's at stake. I got the impression that some thought the larger community was incorrectly rejecting work in this area. I imagine the "larger community" might think the rejections were justified. If, in fact, the research direction is both important and "unknown," it provides evidence toward the importance of publicizing a broader scope of theoretical results than is currently being done through STOC and FOCS.

  6. Some of Vijay's work here has actually appeared in STOC/FOCS, and if there are any important results, this is exactly the sort of thing STOC/FOCS would be interested in. I think not everyone is convinced this is a promising research direction. But they will be easily convinced by theorems, so anyone who thinks this is an important direction should pursue it.

  7. STOC & FOCS gained prominence by accurately evaluating the potential behind computational ideas and hence becoming trend setters. As their role diminishes to that of trend followers, their luster is rapidly eroding. Perhaps the most effective trend setter today is the Internet.

  8. Hi.
    Dear Vazirani, Please help me.
    I have a question. I'm confusing.
    Chen at "complexity of single minded auction" proved that deciding about existence of walrasian equilibrium where customers are single minded is NP complete. But we know Walrasian equilibrium exists if and only if the efficient allocation and its linear programming relaxation has equal answers. Checking whether the solution of a linear program relaxation is integer or not could be done in polynomial time. I can not resolve this contradition.
    please post your answer to: