Location: either Gates 4B lobby, or Terman 453.
Mailing list: thseminar@cs.stanford.edu. Email Qiqi to sign up.
Contact: Qiqi Yan (qiqiyan@stanford...)
Food: Wendy usually chooses the food at her discretion. But the speaker may suggest a preference to Wendy.
This meeting is the place where people sign up for talks.
As we all know, Professor Don Knuth is a famous artist. His book TAOCP convinced the world that algorithm design is an art ; his work on TeX enabled all of us to produce papers that look like pieces of art ; his excellent rendition of Bach using Organ in Rajeev's memorial service also made us wonder, if he discovered some common patterns between the musical language and the computer languages. This Thursday Don will talk about one of his recent artworks. The title of his talk is: "Dragon Curves". This mysterious title seems to suggest that Don also paints, not with common paintbrushes, but with computers and fractal constructions.
We design and analyze approximately revenue-maximizing auctions in general single-parameter settings. Bidders have publicly observable attributes, and we assume that the valuations of indistinguishable bidders are independent draws from a common distribution. Crucially, we assume all valuation distributions are a priori unknown to the seller. Despite this handicap, we show how to obtain approximately optimal expected revenue - nearly as large as what could be obtained if the distributions were known in advance - under quite general conditions.
Our most general result concerns arbitrary downward-closed single-parameter environments and valuation distributions that satisfy a standard hazard rate condition. We also assume that no bidder has a unique attribute value, which is obviously necessary with unknown and attribute-dependent valuation distributions. Here, we give an auction that, for every such environment and unknown valuation distributions, has expected revenue at least a constant factor of the expected optimal welfare (and hence revenue). A key idea in our auction is to associate each bidder with another that has the same attribute, with the second bidder's valuation acting as a reserve price for the first. Conceptually, our analysis shows that even a single sample from a distribution - the second bidder's valuation - is sufficient information to obtain near-optimal expected revenue, even in quite general settings.
This is joint work with Peerapong Dhangwatnotai and Tim Roughgarden.
In the well-studied single source buy-at-bulk network design problem we want to route flow from a designated source node to a set of demand nodes where the cost of using an edge e is given by a concave, non-decreasing function f of the flow on e times its length. I will present an algorithm that finds a distribution over trees independent of f that in expectation is within an O(1) factor of the optimum for any such f.
We want a binary representation a vector of n digits from, say,
{0,...,9} so that each digit can be accessed efficiently. We could
think of the vector as a number in base 10, and then use the
standard binary representation with ceil(log_2(10)*n) bits, but then we
would need roughly linear time to decode an individual digit. Previous
solutions used n/polylog(n) extra bits to gain constant access time.
Essentially we show that only a single extra bit is needed for constant
access time. The same result holds if the digits are from any other alphabet.
Joint work with Mihai Patrascu.
I will outline an approach for exactly solving certain NP-hard graph problems that has recently been developed in work with Ioannis Koutis. The high-level idea is: first encode a set of potential solutions of a search problem with a polynomial that can be efficiently evaluated, then evaluate this polynomial on carefully chosen points over a group algebra in such a way that we "cancel out" all non-solutions and preserve some solutions with decent probability. This basic method has led to new randomized algorithms for several fundamental problems, most notably the longest path problem.
We introduce an algorithmic framework for studying combinatorial optimization problems in the presence of multiple agents.Such a setting models the real world constraints, for instance on the internet different agents provide service on different links. Agents' cost functions are assumed to be submodular, i.e. the functions satisfy the natural properties of decreasing marginal costs. We study several fundamental convering problems (Vertex Cover, Shortest Path, Perfect Matching, and Spanning Tree) in this setting and establish tight upper and lower bounds for the approximability of each of these problems.
This talk is based on joint work with Chinmay Karande, Pushkar Tripathi and Wang Lei.
Linial, London and Rabinovich and Aumann and Rabani proved that the min-cut max-flow ratio for general maximum concurrent flow problems (when there are $k$ commodities) is $O(\log k)$. This ratio is independent of the size of the graph, and only depends on the number of commodities. Here we attempt to derive a more general theory of steiner cut and flow problems. Our structural results are motivated by the meta question: Suppose we are givan a $poly(\log n)$ approximation algorithm, integrality gap or competitive ratio for a flow or cut problem- when can we give a $poly(\log k)$ guarantee for a generalization of this problem to a Steiner cut or flow problem? Thus we require that these guarantees be independent of the size of the graph, and only depend on the number of commodities (or the number of terminal nodes in a Steiner cut problem). For many natural applications (when $k=n^(o(1)}$) this yields much stronger guarantees. We construct vertex-sparsifiers that approximately preserve the value of all terminal multicommodity flows. We prove such sparsifiers exist through zero-sum games and metric geometry, and we construct such sparsifiers through oblivious routing guarantees. These results let us reduce a broad class of multicommodity-type problems to a uniform case (on $k$ nodes) at the cost of a loss of a $poly(\log k)$ in the approximation guarantee. We then give $poly(\log k)$ approximation algorithms for a number of problems for which such results were previously unknown, such as requirement cut, I-multicut, oblivious $0$-extension, and natural generalizations of oblivious routing, min-cut linear arrangement and minimum linear arrangement.
We consider the asymmetric traveling salesman problem for costs satisfying the triangle inequality. We derive a randomized algorithm which delivers a solution within a factor O(log n/ log log n) of the optimum with high probability. Also we give the first constant factor approximation algorithm for metrics that are shortest path distances in a weighted directed graph when the underlying undirected graph has a bounded orientable genus. In this talk I will try to describe the main ideas of these algorithms specially the latter one.
Our approach for ATSP has similarities with Christofides' algorithm; we first construct a spanning tree with special properties. Then we find a minimum cost Eulerian augmentation of this tree, and finally, shortcut the resulting Eulerian walk.
Joint work with: A. Asadpour, M. Goemans, A. Madry, A. Saberi
In a cost-sharing problem, finitely many players have an unknown valuation for some service, and the task is to determine which players to serve and how to distribute the incurred cost. Incentive-compatible mechanisms are sought that elicit truthful valuations, charge prices that recover the cost, and are economically efficient in that they reasonably balance cost and valuations. Of course, cost-sharing mechanisms should also be computable in polynomial time.
I will discuss novel design techniques for cost-sharing mechanisms, their performance guarantees, and the compatibility of various desirable properties. In particular, we make intuitively "small" modifications to the assumptions on players' behavior or to certain design goals. It turns out that some of these modifications allow for very improved performance guarantees, whereas others -- somewhat counterintuitively -- do not. I will demonstrate the benefits of our new design techniques by applying them to cost-sharing problems where the costs are induced by scheduling problems.
Includes joint work with Yvonne Bleischwitz, Karsten Tiemann, and Burkhard Monien.