Initial commit

author: Thibaut Horel <thibaut.horel@gmail.com> 2015-02-28 20:09:43 -0500
committer: Thibaut Horel <thibaut.horel@gmail.com> 2015-02-28 20:09:43 -0500
commit: 683cc893b0ec029e5b019e936e9c83c5c6798dac (patch)
tree: 64a9a5ddce2324fb4a45ba3b17fcbe745030afe5
download: reading_group-683cc893b0ec029e5b019e936e9c83c5c6798dac.tar.gz
8 files changed, 242 insertions, 0 deletions
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..5dc38a4
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,5 @@
+build:
+	python2 build.py
+
+deploy:
+	rsync -r ./ horel.org:public_html/submodularity
diff --git a/build.py b/build.py
new file mode 100644
index 0000000..447d07b
--- /dev/null
+++ b/build.py
@@ -0,0 +1,53 @@
+from jinja2 import Template
+import csv
+from datetime import date
+import os.path as op
+import os
+from subprocess import check_output
+from itertools import chain
+from bs4 import BeautifulSoup
+
+
+def get_references(sessions):
+    keys = chain.from_iterable(session["refs"] for session in sessions)
+    with open("keys.txt", "w") as fh:
+        fh.write("\n".join(keys))
+    html_refs = check_output(["bibtex2html -nodoc -nobibsource -noheader -q "
+                              "-o - -unicode -nokeys -a -citefile keys.txt "
+                              "-s abbrv sub.bib"], shell=True)
+    os.remove("keys.txt")
+    body = BeautifulSoup(html_refs, "lxml").body
+    body.name = "ol"
+    body.hr.decompose()
+    entries = body.find_all("p")
+    entries[-1].decompose()
+    entries = entries[:-1]
+    keys = {}
+    for i, entry in enumerate(entries):
+        entry.name = "li"
+        entry["id"] = entry.a["name"]
+        entry.a.decompose()
+        keys[entry["id"]] = i + 1
+    return unicode(body), keys
+
+
+def clean(session):
+    month, day = map(int, session["date"].split("/"))
+    session_date = date(2015, month, day)
+    session["date"] = session_date.strftime("%a %m/%d")
+    session["refs"] = session["refs"].split(",")
+    fname = op.join("notes", session_date.strftime("%m-%d.pdf"))
+    if op.isfile(fname):
+        session["notes"] = fname
+    return session
+
+
+def build(sessions, refs, keys):
+    template = Template(open("index.jinja").read().decode("utf8"))
+    with open("index.html", "w") as fh:
+        fh.write(template.render(sessions=sessions,
+                                 refs=refs, keys=keys).encode("utf8"))
+
+sessions = [clean(session) for session in csv.DictReader(open("sessions.csv"))]
+refs, keys = get_references(sessions)
+build(sessions, refs, keys)
diff --git a/custom.css b/custom.css
new file mode 100644
index 0000000..0400e59
--- /dev/null
+++ b/custom.css
@@ -0,0 +1,20 @@
+body {
+    font-family: "Source Sans Pro", "Verdana", "Helvetica", sans-serif;
+    color: #333;
+    font-size: 13pt;
+    width: 700px;
+    margin: 0 auto;
+}
+
+.subtext {
+    font-size: 80%;
+    font-weight: normal;
+}
+
+a { text-decoration: none; color: #428BCA}
+a:hover {text-decoration: underline; color: #2A6496}
+h1 { text-align: center }
+h2 { border-bottom: 1px solid #EEE; }
+ul { padding-left: 0; list-style-position: inside }
+ol { padding-left: 1.5em; }
+li + li { margin-top: 0.5em}
diff --git a/index.jinja b/index.jinja
new file mode 100644
index 0000000..8ffda73
--- /dev/null
+++ b/index.jinja
@@ -0,0 +1,27 @@
+<!DOCTYPE html>
+<html lang="en">
+    <head>
+        <meta charset="utf-8">
+        <title>Submodularity Reading Group</title>
+        <link rel="stylesheet" href="custom.css">
+    </head>
+    <body>
+        <h1>Submodular Optimization Reading Group<br>
+            <span class="subtext">Spring 2015</span></h1>
+        <h2>Sessions</h2>
+        <ul>
+            {% for session in sessions -%}
+            <li>{{session.date}} ({{session.speaker}}): {{session.summary}}. [
+                {%- set pipe = joiner(", ") %}
+                {%- for ref in session.refs -%}
+                {{pipe()}}<a href="#{{ref}}">{{keys[ref]}}</a>
+                {%- endfor -%}] {% if session.notes -%}
+                [<a href="{{session.notes}}">notes</a>]
+                {%- endif -%}
+            </li>
+            {% endfor -%}
+        </ul>
+        <h2>References</h2>
+        {{refs}}
+    </body>
+</html>
diff --git a/notes/02-12.pdf b/notes/02-12.pdf
new file mode 100644
index 0000000..a7e32c0
--- /dev/null
+++ b/notes/02-12.pdf
diff --git a/notes/02-25.pdf b/notes/02-25.pdf
new file mode 100644
index 0000000..74ec70b
--- /dev/null
+++ b/notes/02-25.pdf
diff --git a/sessions.csv b/sessions.csv
new file mode 100644
index 0000000..a6ac9fe
--- /dev/null
+++ b/sessions.csv
@@ -0,0 +1,6 @@
+date,speaker,refs,summary
+02/12,Thibaut,"nemhauser1978,khuller1999,sviridenko2004","greedy algorithms for submodular maximization under cardinality, knapsack and matroid constraints"
+02/17,Jean,"ageev2004","pipage rounding"
+02/24,Jean,"calinescu2007","extensions (multilinear, concave closure), Poisson clocks, maximizing sum of weighted rank functions under matroid constraint"
+02/25,Eric,"calinescu2011","continuous greedy algorithm, maximizing monotone submodular function under matroid constraint"
+03/03,Bo,"vondrak2011","contention resolution schemes"
diff --git a/sub.bib b/sub.bib
new file mode 100644
index 0000000..4990ddb
--- /dev/null
+++ b/sub.bib
@@ -0,0 +1,131 @@
+@book{fisher1978,
+  title={An analysis of approximations for maximizing submodular set functions—II},
+  author={Fisher, Marshall L and Nemhauser, George L and Wolsey, Laurence A},
+  year={1978},
+  publisher={Springer}
+}
+
+@article{nemhauser1978,
+  title={An analysis of approximations for maximizing submodular set functions--I},
+  author={Nemhauser, George L and Wolsey, Laurence A and Fisher, Marshall L},
+  journal={Mathematical Programming},
+  volume={14},
+  number={1},
+  pages={265--294},
+  year={1978},
+  publisher={Springer}
+}
+
+@article{edmonds1971,
+  title={Matroids and the greedy algorithm},
+  author={Edmonds, Jack},
+  journal={Mathematical programming},
+  volume={1},
+  number={1},
+  pages={127--136},
+  year={1971},
+  publisher={Springer}
+}
+
+@article{feige1998,
+  title={A threshold of ln n for approximating set cover},
+  author={Feige, Uriel},
+  journal={Journal of the ACM (JACM)},
+  volume={45},
+  number={4},
+  pages={634--652},
+  year={1998},
+  publisher={ACM}
+}
+
+@article{khuller1999,
+  title={The budgeted maximum coverage problem},
+  author={Khuller, Samir and Moss, Anna and Naor, Joseph Seffi},
+  journal={Information Processing Letters},
+  volume={70},
+  number={1},
+  pages={39--45},
+  year={1999},
+  publisher={Elsevier}
+}
+
+@article{sviridenko2004,
+  title={A note on maximizing a submodular set function subject to a knapsack constraint},
+  author={Sviridenko, Maxim},
+  journal={Operations Research Letters},
+  volume={32},
+  number={1},
+  pages={41--43},
+  year={2004},
+  publisher={Elsevier}
+}
+
+@incollection{calinescu2007,
+  title={Maximizing a submodular set function subject to a matroid constraint},
+  author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan},
+  booktitle={Integer programming and combinatorial optimization},
+  pages={182--196},
+  year={2007},
+  publisher={Springer}
+}
+
+@inproceedings{filmus2012,
+  title={A tight combinatorial algorithm for submodular maximization subject to a matroid constraint},
+  author={Filmus, Yuval and Ward, Justin},
+  booktitle={Foundations of Computer Science (FOCS)},
+  pages={659--668},
+  year={2012},
+  organization={IEEE}
+}
+
+@inproceedings{vondrak2011,
+  title={Submodular function maximization via the multilinear relaxation and contention resolution schemes},
+  author={Vondr{\'a}k, Jan and Chekuri, Chandra and Zenklusen, Rico},
+  booktitle={Proceedings of the forty-third annual ACM symposium on Theory of computing},
+  pages={783--792},
+  year={2011},
+  organization={ACM}
+}
+
+@inproceedings{lin2010,
+  title={Multi-document summarization via budgeted maximization of submodular functions},
+  author={Lin, Hui and Bilmes, Jeff},
+  booktitle={Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
+  pages={912--920},
+  year={2010},
+  organization={Association for Computational Linguistics}
+}
+
+@book{schrijver2003,
+  title={Combinatorial optimization: polyhedra and efficiency},
+  author={Schrijver, Alexander},
+  volume={24},
+  year={2003},
+  publisher={Springer}
+}
+
+@article{calinescu2011,
+  title={Maximizing a monotone submodular function subject to a matroid constraint},
+  author={Calinescu, Gruia and Chekuri, Chandra and P{\'a}l, Martin and Vondr{\'a}k, Jan},
+  journal={SIAM Journal on Computing},
+  volume={40},
+  number={6},
+  pages={1740--1766},
+  year={2011},
+  publisher={SIAM}
+}
+
+@article{ageev2004,
+  author    = {Alexander A. Ageev and
+               Maxim Sviridenko},
+  title     = {Pipage Rounding: {A} New Method of Constructing Algorithms with Proven
+               Performance Guarantee},
+  journal   = {J. Comb. Optim.},
+  volume    = {8},
+  number    = {3},
+  pages     = {307--328},
+  year      = {2004},
+  timestamp = {Sun, 15 Nov 4434325 05:30:56 +},
+  biburl    = {http://dblp.uni-trier.de/rec/bib/journals/jco/AgeevS04},
+  bibsource = {dblp computer science bibliography, http://dblp.org}
+}
author	Thibaut Horel <thibaut.horel@gmail.com>	2015-02-28 20:09:43 -0500
committer	Thibaut Horel <thibaut.horel@gmail.com>	2015-02-28 20:09:43 -0500
commit	683cc893b0ec029e5b019e936e9c83c5c6798dac (patch)
tree	64a9a5ddce2324fb4a45ba3b17fcbe745030afe5
download	reading_group-683cc893b0ec029e5b019e936e9c83c5c6798dac.tar.gz