Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Mar
6
awarded  Yearling
Feb
3
awarded  Constituent
Jan
29
awarded  Caucus
2018
Nov
9
awarded  Good Answer
Oct
23
awarded  Enlightened
Oct
22
awarded  Nice Answer
Aug
13
reviewed Approve Is detecting “doubly” arithmetic progressions 3SUM-hard?
Mar
28
awarded  Enlightened
Mar
28
awarded  Nice Answer
Mar
6
awarded  Yearling
Mar
6
reviewed Approve Are the functions always asymptotically comparable?
2017
Nov
7
awarded  Good Answer
May
28
comment 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR
@YuvalFilmus In retrospect, sure. But that's not the easiest way to think about it.
May
28
comment 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR
This is a $3/2$-approximation in expectation. To get the high probability result required by the original question, you need to run this algorithm several times and return the best of the resulting colorings.
May
28
answered 3/2 - Approximation probabilistic algorithm for MAX-3-COLOR
Apr
24
awarded  Good Answer
Mar
29
comment Reducing max flow to bipartite matching?
This is the standard textbook reduction FROM bipartite matching TO maximum flow. The question is asking for a reduction in the opposite direction: FROM maximum flow TO bipartite matching.
Mar
6
awarded  Yearling
Feb
18
awarded  Nice Answer
Jan
25
awarded  Nice Answer