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:
• #### (no subject)

A paper on describing circuits in an agda DSL: http://www.staff.science.uu.nl/~swier004/publications/2015-types-draft.pdf

• #### (no subject)

Going more carefully now through this little tutorial on fpga programming with the iCEstick. It's in spanish, which makes it slightly more…

• #### (no subject)

Some further progress cleaning up the https://xkcd.com/1360/ -esque augean stables that is my hard drive. Tomato chicken I made a couple days ago…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic