New research a ‘breakthrough for large-scale discrete optimization’
1–10 of 21 posts
Re: New research a ‘breakthrough for large-scale discrete optimization’
#2Looks like it may be this paper:
Re: New research a ‘breakthrough for large-scale discrete optimization’
#3I skimmed through because it sounds fairly click-baity... From what I gather, they're claiming to have solved NP-complete problems to some degree with some abstract form algorithm? I'm genuinely interested, if anyone can explain what's going on...
Re: New research a ‘breakthrough for large-scale discrete optimization’
#4Looks like it may be this paper: https://arxiv.org/pdf/1804.06355
"An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation"
https://www.arxiv-vanity.com/papers/1804.06355/
The ACM STOC 2018 conference links to "The Adaptive Complexity of Maximizing a Submodular Function" http://dl.acm.org/authorize?N651970 https://scholar.harvard.edu/files/ericbalkanski/files/the-ad...
A DOI URI would be great, thanks.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#5I've seen two recent posts that mention 'exponentially faster '. Does this have a precise meaning? I could imagine it to mean making a non-exponential algorithm for a problem which only had exponential ones. Another interpretation could be making an algorithm with 2^n steps where previous ones took 2^(2n) steps making the improvement factor 2^n, but still resulting in an exponential time algorithm. Should we just accept this a la 'literally'.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#6Looks like it may be this paper: https://arxiv.org/pdf/1804.06355
Reading through that paper I'm not sure exactly what's new about it above and beyond what has been in a lot of the evolutionary algorithm literature, other than maybe formal proofs (which would be important). I'm sure I'm missing something though because this isn't my area.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#7This is specifically talking about submodular function maximization problems. A submodular set function is a function f(S) that takes a set S and returns a "score". The objective is to find the set S with the highest score. The "submodular" property means that f(S) has "diminishing returns", meaning roughly that each new element contributes less to the score as the set S gets bigger. It turns out that this is hard to maximize exactly, but the simplest possible greedy algorithm already achieves an impressive approximation ratio of 1 - 1/e. The downside is that even the fully greedy algorithm is still pretty slow if you need to find a large set S, which is what this paper is addressing with a parallelizable randomized algorithm. (It's not the first such algorithm, but it's apparently much faster than the previous state of the art.)
[disclaimer: not an expert in any of this]
Re: New research a ‘breakthrough for large-scale discrete optimization’
#8I've seen two recent posts that mention 'exponentially faster '. Does this have a precise meaning? I could imagine it to mean making a non-exponential algorithm for a problem which only had exponential ones. Another interpretation could be making an algorithm with 2^n steps where previous ones took 2^(2n) steps making the improvement factor 2^n, but still resulting in an exponential time algorithm. Should we just acc…
According to this StackExchange answer https://cs.stackexchange.com/a/50356 the speedup is best expressed as a function relating the two algorithm's run times. So if there's a constant factor of 2, then that's "twice as fast", but if the relationship isn't linear (e.g. 2^(2n) = (2^n)^2 is a quadratic function of 2^n) then the speedup is named correspondingly. So 2^(2n) -> 2^n is quadratic speedup, while 2^n -> n or n -> log n are exponential speedups.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#9This is specifically talking about submodular function maximization problems. A submodular set function is a function f(S) that takes a set S and returns a "score". The objective is to find the set S with the highest score. The "submodular" property means that f(S) has "diminishing returns", meaning roughly that each new element contributes less to the score as the set S gets bigger. It turns out that this is hard to…
Thank you! Your comment is so much better than the two pages of fluff this article is made of.
Re: New research a ‘breakthrough for large-scale discrete optimization’
#10This is specifically talking about submodular function maximization problems. A submodular set function is a function f(S) that takes a set S and returns a "score". The objective is to find the set S with the highest score. The "submodular" property means that f(S) has "diminishing returns", meaning roughly that each new element contributes less to the score as the set S gets bigger. It turns out that this is hard to…
very good point. actually, 1-1/e is only for monotone submodular function. for a general submodular function, 1/2 approximation ratio is the best you can get.