diff options
| author | Thibaut Horel <thibaut.horel@gmail.com> | 2012-11-03 14:42:42 +0100 |
|---|---|---|
| committer | Thibaut Horel <thibaut.horel@gmail.com> | 2012-11-03 14:42:42 +0100 |
| commit | f64ff3ca389ec33c240bf6d872033a4bc6e4d9c6 (patch) | |
| tree | 140986849d8c0d25ae5de9f3c8429cee8fccb125 /intro.tex | |
| parent | 58c72935ed45da7f7dea0e28009219e5c5ba919c (diff) | |
| download | recommendation-f64ff3ca389ec33c240bf6d872033a4bc6e4d9c6.tar.gz | |
Small fixes
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}.} |