From f64ff3ca389ec33c240bf6d872033a4bc6e4d9c6 Mon Sep 17 00:00:00 2001
From: Thibaut Horel <thibaut.horel@gmail.com>
Date: Sat, 3 Nov 2012 14:42:42 +0100
Subject: Small fixes

---
 intro.tex | 3 +++
 1 file changed, 3 insertions(+)

(limited to 'intro.tex')

diff --git a/intro.tex b/intro.tex
index ba46534..0b5b70f 100644
--- a/intro.tex
+++ b/intro.tex
@@ -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}.}
-- 
cgit v1.2.3-70-g09d2