Skip to main content
MathOverflow

Return to Answer

added 5 characters in body
Source Link
R B
R B
  • 618
  • 3
  • 18

Not only a PTAS is known for this problem.

It is also possible to compute a PTAS, even without seeing the entire adjacency matrix !

In 2011, Ailon has showed that by a smart choice of queries you can compute a $1+\epsilon$$(1+\epsilon)$-approximation while reading only $O(\epsilon^{-6}\cdot n\cdot log^5n)$ entries (while having the entire matrix means making $O(n^2)$ queries) fromof the weight matrix $W$ (which becomes the adjacency matrix for unweighted instances),.

Not only a PTAS is known for this problem.

It is also possible to compute a PTAS, without seeing the entire adjacency matrix !

In 2011, Ailon has showed that by a smart choice of queries you can compute a $1+\epsilon$-approximation while reading only $O(\epsilon^{-6}\cdot n\cdot log^5n)$ entries (while having the entire matrix means making $O(n^2)$ queries) from the weight matrix $W$ (which becomes the adjacency matrix for unweighted instances),.

Not only a PTAS is known for this problem.

It is also possible to compute a PTAS, even without seeing the entire adjacency matrix !

In 2011, Ailon has showed that by a smart choice of queries you can compute a $(1+\epsilon)$-approximation while reading only $O(\epsilon^{-6}\cdot n\cdot log^5n)$ entries (while having the entire matrix means making $O(n^2)$ queries) of the weight matrix $W$ (which becomes the adjacency matrix for unweighted instances),.

Source Link
R B
R B
  • 618
  • 3
  • 18

Not only a PTAS is known for this problem.

It is also possible to compute a PTAS, without seeing the entire adjacency matrix !

In 2011, Ailon has showed that by a smart choice of queries you can compute a $1+\epsilon$-approximation while reading only $O(\epsilon^{-6}\cdot n\cdot log^5n)$ entries (while having the entire matrix means making $O(n^2)$ queries) from the weight matrix $W$ (which becomes the adjacency matrix for unweighted instances),.