[ps5] Add code to compute integrality gap

1 files changed, 11 insertions, 0 deletions

diff --git a/ps5/gap.py b/ps5/gap.py
new file mode 100644
index 0000000..45925ba
--- /dev/null
+++ b/ps5/gap.py
@@ -0,0 +1,11 @@
+from math import cos, pi
+
+
+def gap(n):
+    qp = n - 1
+    sdp = n * (1 - cos(2 * pi / n * (n / 2))) / 2.
+    return qp / sdp
+
+
+for i in xrange(3, 1000, 2):
+    print "{0:3}: {1}".format(i, gap(i))