Jason (jcreed) wrote,

Here's another algorithm puzzle that I think is essentially the same as the last, but dressed up in more formal clothes:

Suppose you have n variables and O(n) (strict) inequalities in those variables. Presume that the inequalities, taken all together, are consistent. Find a fast way of generating "small" solution sets in the integers in the sense that the assignments to the variables have absolute value < O(n).

My guts tell me: something like O(n lg2 n) or O(n lg n lg lg n) is very likely, O(n lg n) wouldn't surprise me, but O(n) would. To be equivalent to the old problem you'd need to be able to spit out partial solutions (that still satisfied the absolute-value bound) at any point while the equations were being fed to the algorithm online.


Wait. This is just "topological sort", isn't it? I thought it seemed familiar. I doesn't seem like I can use off-the-shelf solutions since I want online generation of a compact represenation of the sort in the integers, but it's good to know that I remember something from undergrad algo four years ago.


Gonna read this paper. Looks like it may actually have the answer I want, or nearly it.


Nope, it's not applicable, but this paper by Sleator and Dietz looks much closer to what I want. The first algorithm assumes a circular size-O(n2) space of indices to work with. I definitely want non-circular and would prefer O(n), but there's a few more sections in the paper I haven't got to yet.


Even closer! Pushing even farther back into the early 1980s, I found this paper by Willard that seems to require only O(n lg n) keyspace, but the paper is difficult going.
Tags: algorithms, papers

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded