4 ms·

Could this be used for maximum cut? Maximum cut at one point was an important concept in IIT which is a somewhat debunked but still interesting theory of consc

Could this be used for maximum cut? Maximum cut at one point was an important concept in IIT which is a somewhat debunked but still interesting theory of consciousness

Tryk 2y ago
Invert all edge weights.
- fuglede_ 2y ago
  This would prove P = NP. The catch being that only positive weights are allowed.
  - deleted 2y ago
    [deleted]
CountHackulus 2y ago
I remember learning an amazing randomized algorithm for max cut. If you pick edges at random 50/50 to be cut, you get a 2-approximation to the optimal solution. That is it's no more than twice as bad. Really not bad for "just guess".
- karmakurtisaani 2y ago
  The first approximation algorithm, invented by Erdős. The best known by Goemans and Williamson achieves about 0.868 (IIRC) approximation, and is a thing of beauty as well.
  - akoboldfrying 2y ago
    A rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.
anticensor 2y ago
No, maximum cut is a significantly harder problem. Minimum cut, on the other hand, is equivalent to maximum flow: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem
akoboldfrying 2y ago
No -- as another commenter pointed out, max-cut is (almost certainly) a much harder problem. Specifically, there are algorithms that guarantee to solve every min-cut problem instance in time polynomial in the size of the problem (CS theorists call such algorithms "efficient"), while max-cut is an NP-complete problem. All NP-complete problems are "as hard as each other", and while no one has yet proven that they all take exponential time to solve, the brightest minds in CS have been searching for a faster algorithm for 40 years without success so far. Most people take that lack of progress as evidence that these problems really are hard. The most famous NP-complete problem is probably the Travelling Salesman Problem. Another interesting one (because it seems like it "shouldn't be that hard") is Partition: Given a set of integers, can you partition them into two halves with equal sum?

Could this be used for maximum cut? Maximum cut at one point was an important concept in IIT which is a somewhat debunked but still interesting theory of consciousness

Tryk 2y ago

Invert all edge weights.

fuglede_ 2y ago
This would prove P = NP. The catch being that only positive weights are allowed.
- deleted 2y ago
  [deleted]

CountHackulus 2y ago

I remember learning an amazing randomized algorithm for max cut. If you pick edges at random 50/50 to be cut, you get a 2-approximation to the optimal solution. That is it's no more than twice as bad. Really not bad for "just guess".

karmakurtisaani 2y ago
The first approximation algorithm, invented by Erdős. The best known by Goemans and Williamson achieves about 0.868 (IIRC) approximation, and is a thing of beauty as well.
- akoboldfrying 2y ago
  A rare example of a constant-factor approximation algorithm with a constant that's... actually useful in practice.

anticensor 2y ago

No, maximum cut is a significantly harder problem. Minimum cut, on the other hand, is equivalent to maximum flow: https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem https://en.wikipedia.org/wiki/Max-flow_min-cut_theorem

akoboldfrying 2y ago

No -- as another commenter pointed out, max-cut is (almost certainly) a much harder problem. Specifically, there are algorithms that guarantee to solve every min-cut problem instance in time polynomial in the size of the problem (CS theorists call such algorithms "efficient"), while max-cut is an NP-complete problem. All NP-complete problems are "as hard as each other", and while no one has yet proven that they all take exponential time to solve, the brightest minds in CS have been searching for a faster algorithm for 40 years without success so far. Most people take that lack of progress as evidence that these problems really are hard. The most famous NP-complete problem is probably the Travelling Salesman Problem. Another interesting one (because it seems like it "shouldn't be that hard") is Partition: Given a set of integers, can you partition them into two halves with equal sum?