Hacker News Reader

Comment by Peaker | Hacker News Reader

The set of all possible costs is the set of sums of all N-sized subsets of the edges.

You only need to binary search that set, not the real numbers' axis. The set's size is exponential to N, but binary searching is logarithmic, so it becomes polynomial in N.

View on HN

But how do you do your binary search on a set without enumerating/sorting it? For example, if at one step, you know that 28.3 is too small and 42 is too big, how do pick the number between them that will split your set in two?

Self balancing btrees will keep your set split roughly in half. So basically, you just insert elements and let the tree worry about remaining balanced.

This isn't a question of data structures: What bmichel is saying is that enumerating a nonpolynomial number of items isn't something you can do as a step in a polynomial reduction.

Maybe you can do something like:

A) Sort edges (descending).

B) Have a total order between N-sized subsets by treating each edge as a binary digit (1 if it is in, or 0 if it is not). I believe this guarantees that the total order between the binary numbers that correspond to edge selections is the same total order as the one between the sums of those selections.

C) Start with some first guess (e.g: 111...111000000...)

D) Binary search on the number, by adjusting each next guess to be the nearest number with N digits enabled.

I am not entirely sure, I just made this up, but I think it might work?

Reply on news.ycombinator.com