diff options
Diffstat (limited to 'intro.tex')
| -rw-r--r-- | intro.tex | 3 |
1 files changed, 3 insertions, 0 deletions
@@ -63,3 +63,6 @@ $O(\log n)$-competitive algorithm. In the bidding model $O(1)$-competitive algorithm. \stratis{What is known about the maximization of logdet in the non-strategic case? Is it NP hard? Approximation ratios?} +\thibaut{Knapsack reduces to our problem in dimension 1, hence maximizing log +det is NP-hard. The approximation ratio is at least (1-1/e) by applying the +general approximation algorithm from Sviridenko \cite{sviridenko-submodular}.} |