23. SODA 2012:
(Ed.): Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012.
, Xi Wu
: Weak compositions and their applications to polynomial lower bounds for kernelization.
: Co-nondeterminism in compositions: a kernelization lower bound for a Ramsey-type problem.
: Structural and logical approaches to the graph isomorphism problem.
: Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs.
: A new approach to the orientation of random hypergraphs.
: A simple algorithm for random colouring G(n, d/n) using (2 + ε)d colours.
: The entropy rounding method in approximation algorithms.
: Constant factor approximation algorithm for the knapsack median problem.
: A universally-truthful approximation scheme for multi-unit auctions.
Vijay V. Vazirani
: The notion of a rational convex program, and an algorithm for the Arrow-Debreu Nash bargaining game.
, Jan Kyncl
: Tight bounds on the maximum size of a set of permutations with bounded VC-dimension.
, Hsin-Hao Su
: A scaling algorithm for maximum weight matching in bipartite graphs.
, Santosh Vempala
: Deterministic construction of an approximate M-ellipsoid and its applications to derandomizing lattice algorithms.
François Le Gall
: Improved output-sensitive quantum algorithms for Boolean matrix multiplication.
: Matroidal degree-bounded minimum spanning trees.