diff options
| -rw-r--r-- | Makefile | 5 | ||||
| -rw-r--r-- | build.py | 53 | ||||
| -rw-r--r-- | custom.css | 20 | ||||
| -rw-r--r-- | index.jinja | 27 | ||||
| -rw-r--r-- | notes/02-12.pdf | bin | 0 -> 209455 bytes | |||
| -rw-r--r-- | notes/02-25.pdf | bin | 0 -> 188616 bytes | |||
| -rw-r--r-- | sessions.csv | 6 | ||||
| -rw-r--r-- | sub.bib | 131 |
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 Binary files differnew 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 Binary files differnew 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" @@ -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} +} |