A set function f on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any two subsets S \subseteq T \subseteq E and an element x outside T, we have f(T + x) - f(T) \leq f(S+x) - f(S).

Abstract:  We present a general framework, applicable to both truthful and non-truthful auctions, for designing approximately revenue-optimal mechanisms for multi-item additive auctions.

Abstract:  How should one divide $m$ goods between $n$ agents, given the utility each agent has when allocated a subset of goods?

Abstract: Given an edge weighted graph and a spanning tree, $T$, the {\em tree augmentation problem} is to pick a minimum weight set of edges, $F$, such that $T\cup F$ is 2-edge connected. Williamson et.al.

Abstract: Consider the following 2-respecting min-cut problem: Given a weighted graph G and its spanning tree T, find the minimum cut among the cuts that contain at most two edges in T.