1)SODA 2009 Invited speakers
2)SODA 2009 Accepted papers, without abstracts (by order of submission)
3)SODA 2009 Accepted papers, with abstracts (by order of submission)
------------------------------------------
SODA 2009 Invited speakers
--------------------------
Michael I. Jordan, University of California at Berkeley:
Combinatorial stochastic processes and nonparametric Bayesian modeling
Yuval Peres, Microsoft Research
The unreasonable effectiveness of Martingales (beyond concentration).
Abstract: I will illustrate the effectiveness of Martingales and stopping times with four examples, involving waiting times for
patterns in coin tossing, random graphs, mixing of random walks, and metric space embedding. A common theme is the way stopping
time arguments often circumvent the wasteful "union bound" (bounding of the probability of a union by the sum of the individual
probabilities.)
Volker Strassen, University of Konstanz, Germany:
Probability, Algorithms and Complexity.
Abstract: The talk will be a little sightseeing tour through some areas of mathematics
and theoretical computer science that I found and find fascinating.
The tour may touch on the development of a gamblers fortune,
the multiplication of numbers and of matrices, probabilistic tests of
primality and the complexity of continued fractions.
SODA 2009 Accepted papers, without abstracts
---------------------------------------------
Jeff Edmonds and Kirk Pruhs. Scalably Scheduling Processes with Arbitrary Speedup Curves
Zdenek Dvorak, Ken-ichi Kawarabayashi and Robin Thomas. Three-coloring triangle-free planar graphs in linear time
Amin Coja-Oghlan, Colin Cooper and Alan Frieze. An Efficient Sparse Regularity Concept
Toniann Pitassi and Nathan Segerlind. Exponential Lower Bounds and Integrality Gaps for Lovasz-Schrijver Procedures
Uriel Feige and Noga Alon. On the power of two, three and four probes
Siu-Wing Cheng and Man-Kwun Chiu. Dimension detection via slivers
Ioannis Caragiannis, Jason Covey, Michal Feldman, Christopher Homan, Christos Kaklamanis, Nikos Karanikolas, Ariel Procaccia and Jeffrey Rosenschein. On the Approximability of Dodgson and Young Elections
David Eppstein and Elena Mumford. Self-overlapping Curves Revisited
Jiri Matousek, Martin Tancer and Uli Wagner. Hardness of embedding simplicial complexes in R^d
MohammadTaghi Hajiaghayi and Mohammad H. Bateni. The Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location
Sudipto Guha, Kamesh Munagala and Peng Shi. Approximation Algorithms for Restless Bandit Problems
Vida Dujmovic, John Howat and Pat Morin. Biased Range Trees
Zeev Nutov. An almost O(log k)-approximation for k-connected subgraphs
David Eppstein, Michael Goodrich and Darren Strash. Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings
Moran Feldman, Guy Kortsarz and Zeev Nutov. Improved Approximating Algorithms for Directed Steiner Forest
Haim Kaplan, Natan Rubin and Micha Sharir. Line Transversals of Convex Polyhedra in S^3
Mikkel Thorup. String Hashing for Linear Probing
Anthony Man-Cho So. Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints
Ken-ichi Kawarabayashi and Yusuke Kobayashi. Algorithms for Finding an Induced Cycle in Planar Graphs
Stephan Thomasse. A quadratic kernel for feedback vertex set
Martin Dietzfelbinger and Ulf Schellbach. On risks of using cuckoo hashing with simple universal hash classes
Michael Molloy and Bruce Reed. Asymptotically optimal frugal colouring
Omid Amini, Louis Esperet and Jan van den Heuvel. A Unified Approach to Distance-Two Colouring of Planar Graphs
Nikhil Bansal and Ho-Leung Chan. Weighted flow time does not admit O(1)-competitive algorithms
Paolo Ferragina, Igor Nitto and Rossano Venturini. On the bit-complexity of Lempel-Ziv compression
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. Testing Halfspaces
Ke Yi and Qin Zhang. Multi-Dimensional Online Tracking
Krishnendu Chatterjee, Luca de Alfaro and Thomas Henzinger. Termination Criteria for Solving Concurrent Safety and Reachability Games
Philip Klein, Shay Mozes and Oren Weimann. Shortest Paths in Directed Planar Graphs with Negative Lengths: a linear-space O(n log^2 n)-time algorithm
Ioannis Caragiannis. Efficient coordination mechanisms for unrelated machine scheduling
Daniel Marx. Approximating fractional hypertree width
Bodo Manthey and Heiko Roeglin. Improved Smoothed Analysis of the k-Means Method
Christos Boutsidis, Michael Mahoney and Petros Drineas. An Improved Approximation Algorithm for the Column Subset Selection Problem
Michael Drmota and Wojciech Szpankowski. (Un)Expected Behavior of Digital Search Tree Profile
Nikhil Bansal, Zachary Friggstad, Rohit Khandekar and Mohammad Salavatipour. A logarithmic approximation for the unsplittable flow on line graphs
Edith Cohen, Nick Duffield, Haim Kaplan, Carsten Lund and Mikkel Thorup. Variance-optimal sampling-based estimation of subset sums
Sergio Cabello. Finding shortest contractible cycles in embedded graphs
Khaled Elbassioni, Rajiv Raman, Saurabh Ray and Rene Sitters. On the approximability of the maximum feasible subsystem problem with 0/1-coefficients
S. Charles Brubaker. Clustering on Noisy Mixtures
Ashish Goel, Michael Kapralov and Sanjeev Khanna. Perfect matchings via uniform sampling in regular bipartite graphs
David Karger and Debmalya Panigrahi. An tilde{O}(m) algorithm for constructing a cactus of an undirected graph
Joel Tropp. Efficient Algorithms for Column Subset Selection
Gabriel Nivasch. Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
Gabor Tardos and Ehsan Amiri. High rate fingerprinting codes and the fi ngerprinting capacity
Yury Person and Mathias Schacht. Almost all hypergraphs without Fano planes are bipartite
Amr Elmasry. Pairing Heaps with O(loglog n}) decrease Cost
Haim Kaplan and Uri Zwick. A simpler implementation and analysis of Chazelle's Soft Heaps
Mikkel Thorup, Uri Zwick and Omid Madani. Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths
Alon Shalita and Uri Zwick. Efficient algorithms for the 2-gathering problem
david cohen-steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov. Persistent Homology for Kernels, Images, and Cokernels
Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh. Clique-width: On the Price of Generality
Parinya Chalermsook and Julia Chuzhoy. Maximum Independent Set of Rectangles
Brendan Nagle, Annika Poerschke, Vojtech Rödl and Mathias Schacht. On Algorithmic Hypergraph Regularity
Robi Krauthgamer, Seffi Naor and Roy Schwartz. Partitioning Graphs into Balanced Components
Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs. Speed Scaling with an Arbitrary Power Function
Zdenek Dvorak, Daniel Kral and Robin Thomas. Coloring triangle-free graphs on surfaces
Amitabh Basu, Pierre Bonami, gerard cornuejols and Francois Margot. On the Relative Strength of Split, Triangle and Quadrilateral Cuts (Extended Abstract)
Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild. From coding theory to efficient pattern matching
Ramesh Hariharan and Anand Bhalgat. Fast Edge Orientation for Unweighted Graphs
Viswanath Nagarajan and Maxim Sviridenko. On the Maximum Quadratic Assignment Problem
Bernard Chazelle. Natural Algorithms
Timothy M. Chan. Comparison-Based, Time-Space Lower Bounds for Selection
Peyman Afshani and Timothy M. Chan. Optimal Halfspace Range Reporting in Three Dimensions
Justin Salez and Devavrat Shah. Optimality of Belief Propagation for Random Assignment Problem
Ping Li. Compressed Counting
Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu. The Geometry of Binary Search Trees
Satoru Iwata and James Orlin. A Simple Combinatorial Algorithm for Submodular Function Minimization
Prasad Raghavendra and David Steurer. Towards Computing the Grothendieck Constant
Mordecai J. Golin, Xiaoming Xu and Jiajin Yu. A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding
Ken-ichi Kawarabayashi, Erik Demaine and Mohammad Taghi Haijaghayi. Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs
Ken-ichi Kawarabayashi and Bruce Reed. A Nearly Linear Time Algorithm For The Half Integral Parity Disjoint Paths Packing Problem
Michel Goemans, Nicholas J.A. Harvey, Satoru Iwata and Vahab Mirrokni. Approximating Submodular Functions Everywhere
Baharak Rastegari, Anne Condon and Kevin Leyton-Brown. Stepwise Randomized Combinatorial Auctions Achieve Revenue Monotonicity
Ilia Binder and Mark Braverman. The complexity of simulating Brownian Motion
Prosenjit Bose, Eric Chen, Meng He, Anil Maheshwari and Pat Morin. Succinct Geometric Indexes Supporting Point Location Queries
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh and Sebastiano Vigna. Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses
Alexandr Andoni, Piotr Indyk, Robi Krauthgamer and Huy Nguyen. Approximate Nearest Neighbors for Affine Subspaces Queries
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, ?ukasz Je? and Grzegorz Stachowiak. Collecting Weighted Items from a Dynamic Queue
Boaz Barak, Moritz Hardt and Satyen Kale. The Uniform Hardcore Lemma via Approximate Bregman Projections
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David Woodruff. Transitive-Closure Spanners
Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant. On the Complexity of Nash Equilibria of Action-Graph Games
Alexandr Andoni, Piotr Indyk and Robi Krauthgamer. Overcoming the L_1 Non-Embeddability Barrier: Algorithms for Product Metrics
Parikshit Gopalan and Jaikumar Radhakrishnan. Finding repeats in a data-stream
James Aspnes and Keren Censor. Approximate Shared-Memory Counting Despite a Strong Adversary
Ittai Abraham, Yair Bartal and Ofer Neiman. On Low Dimensional Local Embeddings
Michael Bender, Jeremy Fineman and Seth Gilbert. Online Topological Ordering
William Johnson and Assaf Naor. The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem
Markus Chimani, Carsten Gutwenger, Petra Mutzel and Christian Wolf. Inserting a Vertex into a Planar Graph
Spyros Angelopoulos and Pascal Schweitzer. Paging and List Update under Bijective Analysis
Adrian Dumitrescu, Csaba Toth and G Xu. On stars and Steiner stars. II
Benjamin Aminof, Orna Kupferman and Robby Lampert. Reasoning about Online Algorithms with Weighted Automata
Amin Coja-Oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich and Dan Vilenchik. On smoothed k-CNF formulas and the Walksat algorithm
Elad Hazan and Robi Krauthgamer. How hard is it to approximate the best Nash equilibrium?
Ashish Goel, Sanjeev Khanna and Brad Null. The Ratio Index for Budgeted Learning, with Applications
Serge Gaspers and Gregory Sorkin. A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
Greg Aloupis, Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden and Pedro Ramos. Decomposition of Multiple Coverings into More Parts
Edith Elkind and Dmitrii Pasechnik. Computing the nucleolus of weighted voting games
Konstantinos Panagiotou and Angelika Steger. Maximum Biconnected Subgraphs of Random Planar Graphs
Ken-ichi Kawarabayashi and Bojan Mohar. List-Color-Critical Graphs on a Fixed Surface
Ariel Kulik, Hadas Shachnai and Tami Tamir. Maximizing Submodular Set Functions Subject to Multiple Linear Constraints
Marcel R. Ackermann and Johannes Blömer. Coresets and Approximate Clustering for Bregman Divergences
Benjamin Moseley and Chandra Chekuri. Online Scheduling to Minimize the Maximum Delay Factor
Maria-Florina Balcan, Avrim Blum and Anupam Gupta. Approximate Clustering without the Approximation
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica and Kunal Talwar. Secretary Problems: Weights and Discounts
Maria-Florina Balcan, Avrim Blum and Yishay Mansour. Improved Equilibria via Public Service Advertising
Yusu Wang, Kevin Buchin and Maike Buchin. Exact Algorithm for Partial Curve Matching via the Frechet Distance
Pankaj K Agarwal, R Sharathkumar and Hai Yu. Approximate Euclidean Shortest Path amid convex obstacles
Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin. Sorting and Selection in Posets
Sergi Elizalde and Peter Winkler. Sorting by Placement and Shift
Ryan O'Donnell and Yi Wu. 3-Bit Dictator Testing: 1 vs. 5/8
Siddharth Barman and Shuchi Chawla. Packing multiway cuts in graphs
Frederic Chazal, Leonidas Guibas, Steve Oudot and Primoz Skraba. Analysis of Scalar Fields over Point Cloud Data
Frederic Magniez, Ashwin Nayak, Peter Richter and Miklos Santha. On the hitting times of quantum versus random walks
Elad Hazan and Satyen Kale. Better Algorithms for Benign Bandits
Florin Constantin, Jon Feldman, S Muthukrishnan and Martin Pal. An Online Mechanism for Ad Slot Reservations with Cancellations
Colin Cooper and Alan Frieze. The cover time of random geometric graphs
Lorenz Minder and Alistair Sinclair. The extended k-tree algorithm
Misha Belkin, jian sun and Yusu Wang. Constructing Laplace operators from Point Clouds
Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh and Prabhakar Raghavan. Online story scheduling for web advertising
Mohsen Bayati, Andrea Montanari and Amin Saberi. Generating Random Graphs with Large Girth
Florian Diedrich and Klaus Jansen. Improved Approximation Algorithms for Scheduling with Fixed Jobs
Aurore Amaudruz and Christina Fragouli. Combinatorial Algorithms for Wireless Information Flow
Ran Duan and Seth Pettie. Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths
Mehmet Begen and Maurice Queyranne. Appointment Scheduling with Discrete Random Durations
Navin Goyal, Luis Rademacher and Santosh Vempala. Expanders via Random Spanning Trees
Aaron Williams. Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts
Ran Duan and Seth Pettie. Dual-Failure Distance and Connectivity Oracles
david gamarnik and Dimitry Katz. Sequential cavity method for computing limits of the log-partition function for
Alexander Golynski. Lower Bounds for Succinct Data Structures
Umang Bhaskar, Lisa Fleischer, Darrell Hoy and Chien-Chung Huang. Equilibria of Collusive Flow Games are not Unique
Sam Greenberg, Amanda Pascoe and Dana Randall. Sampling Biased Lattice Configurations using Exponential Metrics
Benoît Hudson, Gary Miller, Todd Phillips and Don Sheehy. Size Complexity of Volume Meshes vs. Surface Meshes
Yury Lifshits and Shengyu Zhang. Combinatorial Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design.
SODA 2009 Accepted papers, with abstracts
------------------------------------------
Jeff Edmonds and Kirk Pruhs. Scalably Scheduling Processes with Arbitrary Speedup Curves
Abstract: We give a scalable ($(1+\epsilon)$-speed $O(1)$-competitive) nonclairvoyant
algorithm for scheduling jobs with sublinear nondecreasing speed-up curves on multiple processors with the objective of average response time.
------------------------------------------
Zdenek Dvorak, Ken-ichi Kawarabayashi and Robin Thomas. Three-coloring triangle-free planar graphs in linear time
Abstract: Gr\"otzsch's theorem states that every triangle-free planar graph is $3$-colorable, and several relatively simple proofs of this fact were provided by Thomassen and other authors. It is easy to convert these proofs into quadratic-time algorithms to find a $3$-coloring, but it is not clear how to find such a coloring in linear time (Kowalik used a nontrivial data structure to construct an $O(n \log n)$ algorithm).
We design a linear-time algorithm to find a $3$-coloring of a given
triangle-free planar graph. The algorithm avoids using any complex data structures, which makes it easy to implement. As a by-product we give another simple proof of Gr\"otzsch's theorem.
------------------------------------------
Amin Coja-Oghlan, Colin Cooper and Alan Frieze. An Efficient Sparse Regularity Concept
Abstract: Let $\A$ be a $0/1$ matrix of size $m\times n$, and let $p$ be the density of $\A$ (i.e.,
the number of ones divided by $m\cdot n$).
We show that $\A$ can be approximated in the cut norm within $\eps\cdot mnp$ by
a sum of cut matrices (of rank $1$), where the number of summands is independent of the
size $m\cdot n$ of $\A$, provided that $\A$ satisfies a certain boundedness condition.
This decomposition can be computed in polynomial time.
This result extends the work of Frieze and Kannan~\cite{FK} to \emph{sparse} matrices.
As an application, we obtain efficient $1-\eps$ approximation algorithms
for ``bounded'' instances of MAX CSP problems.
------------------------------------------
Toniann Pitassi and Nathan Segerlind. Exponential Lower Bounds and Integrality Gaps for Lovasz-Schrijver Procedures
Abstract: The matrix cuts of Lovasz and Shrijver are methods for tightening linear relaxations of zero-one programs by the addition of new linear inequalities. We address the question of how many new inequalities are necessary to approximate certain combinatorial problems and to solve certain instances of Boolean satisfiability.
Our first result is a size/rank tradeoff for tree-like LS+ refutations, showing that any refutation that has small size also has small rank. This allows us to immediately derive exponential size lower bounds for tree-like LS+ derivations of many unsatisfiable systems of inequalities where prior to our work, only rank lower bounds were known.
Unfortunately we show that this tradeoff does not hold more generally for derivations of arbitrary inequalities. We give a simple example showing that derivations can be very small but nonetheless require maximal rank. This rules out a generic argument for obtaining size-based integrality gaps from rank-based gaps. Our second contribution is to show that a modified argument can often be used to prove size-based gaps from rank-based gaps. We illustrate this method by proving size-based integrality gaps for several prominent problems, where again prior to our work only rank-based integrality gaps were known.
Our third contribution is to prove new separation results between proof systems. Using our machinery for converting rank-based lower bounds and integrality gaps into size-based lower bounds, we show that tree-like LS+ cannot polynomially simulate tree-like Cutting Planes. We also show that tree-like LS+ cannot simulate Resolution, and in particular, low rank LS+ cannot simulate Resolution.
We conclude by examining size/rank tradeoffs behond the LS systems. We show that for Sherali-Adams and Lassere systems, size/rank tradeoffs continue to hold, even in the general (non-tree) case.
------------------------------------------
Uriel Feige and Noga Alon. On the power of two, three and four probes
Abstract: An adaptive $(n,m,s,t)$-scheme is a deterministic scheme for
encoding a vector $X$ of $m$ bits with at most $n$ ones by a
vector $Y$ of $s$ bits, so that any bit of $X$ can be determined
by $t$ adaptive probes to $Y$. A non-adaptive $(n,m,s,t)$-scheme
is defined analogously. The study of such schemes arises in the
investigation of the static membership problem in the bitprobe
model. Answering a question of Buhrman, Miltersen, Radhakrishnan
and Venkatesh [SICOMP 2002] we present adaptive $(n,m,s,2)$
schemes with $s2 (even if k is not considered fixed).
We observe that the celebrated result of Novikov on the algorithmic
unsolvability of recognizing the 5-sphere
implies that EMBED(d,d) and EMBED(d-1,d) are undecidable for any d>4.
Our main result is NP-hardness of EMBED(2,4) and, more generally,
of EMBED(k,d) for all k and d with d>3 and d\geq k \geq (2d-2)/3.
These dimensions fall outside the so-called metastable range of
a theorem of Haefliger and Weber, which characterizes
embeddability using the deleted product obstruction. Our
reductions are based on examples, due to Segal, Spiez,
Freedman, Krushkal, Teichner, and Skopenkov, showing
that outside the metastable range the deleted product obstruction
is not sufficient to characterize embeddability.
------------------------------------------
MohammadTaghi Hajiaghayi and Mohammad H. Bateni. The Assignment Problem in Content Distribution Networks: Unsplittable Hard-Capacitated Facility Location
Abstract: In a Content Distribution Network (CDN), there are $m$ servers storing
the data; each of them has a specific bandwidth. All the requests from
a particular client should be assigned to one server, because of the
routing protocols used. The goal is to minimize the total cost of
these assignments --- which is proportional to the distance as well
as the request size --- while the load on each server is kept below
its bandwidth constraint. When each server also has a setup cost,
this is an \emph{unsplittable hard-capacitated facility location
problem}. As much attention as facility location problems have
received, there has been no nontrivial approximation algorithm when we
have hard capacities (i.e., there can only be one copy of each facility
whose capacity cannot be violated) and demands are unsplittable (i.e.,
all the demand from a client has to be assigned to a single facility).
We observe it is NP-hard to approximate the cost to within any bounded
factor. Thus, we relax the capacities to a $1+\epsilon$ factor. For
the case where capacities are almost uniform, we give a bicriteria
$O(\log n, 1+\epsilon)$-approximation algorithm for general metrics and
a $(1+\epsilon, 1+\epsilon)$-approximation algorithm for tree metrics.
We can get the same guarantee for non-uniform capacities if we allow
quasipolynomial running time. A bicriteria (\alpha, \beta)-approximation
algorithm produces a solution of cost at most \alpha times the optimum, while violating the capacities by no more than a \beta factor. In our algorithm, some clients guess the
facility they are assigned to, and facilities decide the size of
clients they serve. A straight-forward approach results in exponential
running time. Handling this in (quasi-)polynomial time is also of
independent interest. When costs do not satisfy metricity, we show
that a $1.5$ violation of capacities is necessary to obtain any
approximation.
It is worth noting that our results generalizes bin packing (zero cost
matrix and facility costs equal to one), knapsack (single facility with
all costs being zero), minimum makespan scheduling for related machines
(all costs being zero) and facility location problems.
------------------------------------------
Sudipto Guha, Kamesh Munagala and Peng Shi. Approximation Algorithms for Restless Bandit Problems
Abstract: In this paper, we consider the restless bandit problem, which is
one of the most well-studied generalizations of the celebrated
stochastic multi-armed bandit problem in decision theory. In its
ultimate generality, the restless bandit problem is known to be
PSPACE-Hard to approximate to any non-trivial factor, and little
progress has been made on this problem despite its significance in
modeling activity allocation under uncertainty. We make progress on this
problem by showing that for an interesting and general
subclass that we term Monotone bandits, a surprisingly simple and
intuitive greedy policy yields a factor 2 approximation. Such greedy
policies are termed index policies, and are popular due to their
simplicity and their optimality for the stochastic multi-armed bandit
problem. The Monotone bandit problem strictly generalizes the
stochastic multi-armed bandit problem, and naturally models
multi-project scheduling where the state of a project becomes
increasingly uncertain when the project is not scheduled. As a consequence we are able to significantly improve previous results on special cases, as well
as provide algorithms for generalizations. It is
worth noting that the previous algorithm(s) do not apply to
Monotone bandits and a new analysis was essential to this progess.
The notion of Monotone bandits is similar to (but not quite the same as) the notion of a Partially Observable Markov Decision Process (POMDP). This and
related restless bandit problems serve as models for wireless
scheduling, unmanned aerial vehicle (UAV) routing, and machine
replenishment, among others.
We develop several novel techniques in the design and analysis of the
index policy. Our algorithm proceeds by introducing a novel "balance"
constraint to the dual of a well-known LP relaxation to the restless bandit problem. This is followed by a structural characterization of the optimal solution by
using both the exact primal as well as dual complementary slackness
conditions. This yields an interpretation of the dual variables as
potential functions from which we derive the index policy and the
associated analysis. In addition, our techniques are general are of
independent interest in other stochastic optimization contexts, and we
provide one such example.
------------------------------------------
Vida Dujmovic, John Howat and Pat Morin. Biased Range Trees
Abstract: A data structure, called a \emph{biased range tree}, is presented that
preprocesses a set S of n points in R^2 and a query
distribution D for 2-sided orthogonal range counting queries. The
expected query time for this data structure, when queries are drawn
according to D, matches, to within a constant factor, that of the
optimal comparison tree for S and D. The memory and preprocessing
requirements of the data structure are O(n\log n).
------------------------------------------
Zeev Nutov. An almost $O(\log k)$-approximation for $k$-connected subgraphs
Abstract: We give an $O(\log k \cdot \log \frac{n}{n-k})$-approximation algorithm for the
$k$-Connected Subgraph problem, that seeks to find a directed/undirected
$k$-connected spanning subgraph of minimum cost. Our ratio is $O(\log k)$,
unless $k=n-o(n)$. Previously, the best known approximation guarantees for this
problem were $O(\log^2 k)$ for directed/undirected graphs
[Fakcharoenphol and Laekhanukit, STOC 2008], and $O(\log k)$ for undirected
graphs with $k \leq \sqrt{n/2}$ [Cheriyan, Vempala, and Vetta, STOC 2002].
As in previous work, we consider the augmentation problem of increasing at minimum
cost the connectivity of a given graph $J$ by $1$ (a $\rho$-approximation for it
is used to derive an $O(\rho \cdot \log k)$-approximation for $k$-Connected Subgraph). Fakcharoenphol and Laekhanukit showed that this
augmentation problem admits an $O(\log t)$-approximation algorithm,
where $t$ is the number of minimal ''violated'' sets in $J$.
However, we may have $t=\Theta(n)$, so this gives only an $O(\log n)$-approximation.
We show that a modification of the primal-dual algorithm of Ravi and Williamson
can be used to add an edge set of cost $\leq {\opt}$ to get $t \leq \frac{2n}{n-k}$.
Combined with the algorithm of Fakcharoenphol and Laekhanukit,
this gives the ratio $O(\log \frac{n}{n-k})$ for the augmentation problem,
which is $O(1)$, unless $k=n-o(n)$.
------------------------------------------
David Eppstein, Michael Goodrich and Darren Strash. Linear-Time Algorithms for Geometric Graphs with Sublinearly Many Crossings
Abstract: We provide linear-time algorithms
for geometric graphs with sublinearly many crossings.
That is, we provide algorithms running in $O(n)$ time
on connected geometric graphs having $n$ vertices and $k$ crossings, where $k$
is smaller than $n$ by an iterated logarithmic factor.
Specific problems we study include Voronoi diagrams and single-source
shortest paths.
Our algorithms all run in linear
time in the standard comparison-based computational model;
hence, we make no assumptions about the distribution or bit
complexities of edge weights, nor do we utilize unusual bit-level
operations on memory words.
Instead, our algorithms are based on
a \emph{planarization} method that ``zeroes in'' on edge crossings, together
with methods for extending planar separator decompositions
to geometric graphs with sublinearly many crossings.
Incidentally, our planarization algorithm also
solves an open computational geometry
problem of Chazelle for triangulating a self-intersecting polygonal
chain having $n$ segments and $k$ crossings
in linear time, for the case when $k$ is
sublinear in $n$ by an iterated logarithmic factor.
------------------------------------------
Moran Feldman, Guy Kortsarz and Zeev Nutov. Improved Approximating Algorithms for Directed Steiner Forest
Abstract: We consider the $k$-Directed Steiner Forest ($k$-DSF) problem:
given a directed graph $G=(V,E)$ with edge costs, a collection
$D \subseteq V \times V$ of ordered node pairs, and an integer $k \leq |D|$,
find a minimum cost subgraph $H$ of $G$ that contains an $st$-path for (at least)
$k$ pairs $(s,t) \in D$. When $k=|D|$, we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are:
$\tilde{O}(k^{2/3})$ for $k$-DSF by Charikar et~al. \cite{CCC}, and
$O(k^{1/2 + \ee})$ for DSF by Chekuri et~al. \cite{CEGS}.
We improve these approximation ratios as follows.
For DSF we give an $O(n^\ee \cdot \min\{n^{4/5},m^{2/3}\})$-approximation scheme
using a novel LP-relaxation that seeks to connect pairs with ''cheap'' paths.
This is the first sub-linear (in terms of $n=|V|$) approximation ratio for the
problem; all previous algorithm had ratio $\Omega(n^{1+\ee})$.
For $k$-DSF we give a simple greedy $O(k^{1/2 + \ee})$-approximation algorithm.
This improves the best known ratio $\tilde{O}(k^{2/3})$ by Charikar et~al.
\cite{CCC}, and (almost) matches in terms of $k$ the best ratio known for the
undirected variant \cite{GHNR}.
Even when used for the particular case of DSF, our algorithm favorably compares
to the one of \cite{CEGS}, which repeatedly solves linear programs
and uses complex space and time consuming transformations.
Our algorithm is much simpler and faster, since it essentially reduces $k$-DSF
to a variant of the Directed Steiner Tree problem.
The simplification is due to a new notion of ``junction star-tree'' -- a union
of an in-star and an out-branching having the same root,
which is of independent interest.
------------------------------------------
Haim Kaplan, Natan Rubin and Micha Sharir. Line Transversals of Convex Polyhedra in \reals^3
Abstract: We establish a bound of $O(n^2k^{1+\eps})$, for any $\eps>0$, on the
combinatorial complexity of the set $\T$ of line transversals of a
collection $\P$ of $k$ convex polyhedra in $\reals^3$ with a total
of $n$ facets, and present a randomized algorithm which computes the
boundary of $\T$ in comparable expected time. Thus, when $k\ll n$,
the new bounds on the complexity (and construction cost) of $\T$
improve upon the previously best known bounds, which are nearly
cubic in $n$.
To obtain the above result, we study the set $\TL$ of line
transversals which emanate from a fixed line $\ell_0$, establish an
almost tight bound of $O(nk^{1+\eps})$ on the complexity of $\TL$,
and provide a randomized algorithm which computes $\TL$ in
comparable expected time. Slightly improved combinatorial bounds for
the complexity of $\TL$, and comparable improvements in the cost of
constructing this set, are established for two special cases, both
assuming that the polyhedra of $\P$ are pairwise disjoint: the case
where $\ell_0$ is disjoint from the polyhedra of $\P$, and the case
where the polyhedra of $\P$ are unbounded in a direction parallel to
$\ell_0$.
------------------------------------------
Mikkel Thorup. String Hashing for Linear Probing
Abstract: Hash tables for strings and other complex objects are central to the
analysis of data, and they are directly built into high level
programming languages such as python, and perl.
Linear probing is one of the most popular implementations of hash
tables in practice. We store all keys in a single array. A new key is
hashed. If a different key is in the position hashed to, we scan next
positions sequentially until either the key is found, or we hit an
empty spot concluding that the key is new. This is compact and it is
fast because we typically get all positions considered in single
cache-line, and that also holds for deletions. However, linear probing
has been known to be a bit unreliable in practice. Analyzing the
performance of linear probing with universal hash functions was raised
as an open problem by Carter and Wegman in 1979.
At STOC'07, Pagh et al.~studied the expected number of
linear probes with worst-case data sets. They showed that with the standard
implementation of 2-universal hashing, the expected number of
probes could be $\Omega(\log n)$. A worst-case is one or two
intervals --- something that could very well appear in practice,
possibly explaining the experienced unreliability. On the positive
side, they showed that with 5-universal hashing, the expected number
of probes is constant.
Unfortunately, we do not have 5-universal hashing for, say, variable
length strings. When we want to do such complicated hashing on a
complicated domain, the generic standard solution is that we first do
collision free hashing (w.h.p.) into a simpler intermediate domain,
and second do the complicted hash function on this intermediate
domain.
Our contribution is that for an expected constant number of linear probes, it
is suffices that each key has $O(1)$ expected collisions with the
first hash function, as long as the second hash function is
5-universal. This means that the intermediate domain can be $n$ times
smaller. Such a smaller intermediate domain typically means that
the both the first and the second hash function run at least twice as fast.
This doubling of hashing speed follows not just for variable length strings,
but for most domains bigger than 32-bit integers, e.g., fixed length strings
and even 64-bit integers.
------------------------------------------
Anthony Man-Cho So. Improved Approximation Bound for Quadratic Optimization Problems with Orthogonality Constraints
Abstract: In this paper we consider approximation algorithms for a class of quadratic optimization problems that contain orthogonality constraints, i.e. constraints of the form $X^TX=I$, where $X\in\R^{m\times n}$ is the optimization variable. This class of problems, which we denote by (QP-OC), is quite general and captures several well-studied problems in the literature as special cases. In a recent work, Nemirovski [Math. Prog. 109:283--317, 2007] gave the first non-trivial approximation algorithm for (QP-OC). His algorithm is based on semidefinite programming and has an approximation guarantee of $O\left((m+n)^{1/3}\right)$. We improve upon this result by providing the first logarithmic approximation guarantee for (QP-OC). Specifically, we show that (QP-OC) can be approximated to within a factor of $O\left(\ln\left(\max\{m,n\}\right)\right)$. The main technical tool used in the analysis is a concentration inequality for the spectral norm of a Rademacher sum of matrices, which we develop using tools from functional analysis. As a by-product, we resolve in the affirmative a conjecture of Nemirovski concerning the typical spectral norm of a sum of certain random matrices. The aforementioned concentration inequality also has ramifications in the design of so-called safe tractable approximations of chance constrained optimization problems. In particular, we use it to simplify and improve a recent result of Ben-Tal and Nemirovski [Manuscript, 2007] concerning certain chance constrained linear matrix inequality systems.
------------------------------------------
Ken-ichi Kawarabayashi and Yusuke KOBAYASHI. Algorithms for Finding an Induced Cycle in Planar Graphs
Abstract: In this paper, we consider the problem for finding an induced cycle passing through $k$ given vertices, which we call the induced cycle problem. The significance of finding induced cycles stems from the fact that precise characterization of perfect graphs would require structures of graphs without an odd induced cycle, and its complement. There has been huge progress in the recent years, especially, the Strong Perfect Graph Conjecture was solved by Chudnovsky, Robertson, Seymour and Thomas. Concerning recognition of perfect graphs, there had been a long-standing open problem for detecting an odd hole and its complement, and finally this was solved by Chudnovsky, Cornu\'ejols, Liu, Seymour and Vuskovic.
Unfortunately, the problem of finding an induced cycle passing through two given vertices is NP-complete in a general graph. However, if the input graph is constrained to be planar and $k$ is fixed, then the induced cycle problem can be solved in polynomial time.
In particular, an $O(n^2)$ time algorithm is given for the case $k=2$ by McDiarmid, Reed, Schrijver and Shepherd, where $n$ is the number of vertices of the input graph.
Our main results in this paper are to improve their result in the following sense.
(1) The number of vertices $k$ is allowed to be non-trivially super constant number, up to $k = o((\frac{\log n}{\log \log n})^{\frac{2}{3}})$. More precisely, when $k = o((\frac{\log n}{\log \log n})^{\frac{2}{3}})$, then the ICP in planar graphs can be solved in $O (n^{2 + \varepsilon})$ time for any $\varepsilon > 0$.
(2) The time complexity is linear if the given graph is planar and $k$ is fixed.
(3) The above results are extended to graphs embedded in a fixed surface.
We note that the linear time algorithm (the second result) is independent from the first result. Let us observe that if $k$ is as a part of the input, then the problem is still NP-complete. So we need to impose some condition on $k$.
Our proofs of the above results basically follow the same line of the proof of the disjoint paths problem by Robertson and Seymour, together with Reed, Robertson, Schrijver, Seymour's result, which improves the time complexity of the algorithm of the disjoint paths by Robertson and Seymour ($O(n^3)$ time algorithm) to linear time when an input graph is planar. However, our cycle must be induced, so some of arguments must be extended to induced paths, which needs much more involved arguments. In addition, we are also interested in the case when $k$ is as a part of the input. Therefore, we need to sharpen the function of $k$. This needs nontrivial amount of work, since both Robertson-Seymour's proof and Reed, Robertson, Schrijver, Seymour's proof do not care much about sharpening the hidden constant of $k$. These proofs just guarantee the existence of the function of $k$, therefore, it is highly expensive, and nonpractical. Our proofs, though, give fairly small function of $k$. Therefore, we believe that this result may be viewed as a much more practical result. Price to pay is to need to analyze the structure of planar graphs and graphs embedded in a fixed surface more closely.
------------------------------------------
Stephan Thomasse. A quadratic kernel for feedback vertex set
Abstract: We prove that given an undirected graph $G$ on $n$ vertices and an integer
$k$, one can compute in polynomial time in $n$ a graph $G'$ with at most
$5k^2+k$ vertices and an integer $k'$ such that $G$ has a
feedback vertex set of size at most $k$ iff $G'$ has a
feedback vertex set of size at most $k'$. This result improves
a previous $O(k^{11})$ kernel of Burrage et al.~\cite{MF}, and a more
recent cubic kernel of Bodlaender~\cite{HL2}.
This problem was communicated by Fellows in~\cite{MF}.
------------------------------------------
Martin Dietzfelbinger and Ulf Schellbach. On risks of using cuckoo hashing with simple universal hash classes
Abstract: Background:
Cuckoo hashing, introduced by Pagh and Rodler (``Cuckoo hashing'', ESA 2001 and J.
Algorithms 51, 2004), is a strategy for maintaining hash tables for keys from $U$,
$|U|=N$, so that lookups take constant time in the worst case. The data structure
consists of two tables of size $m$ each, and it uses two hash functions $h_1,
h_2\colon U\to [m]$. For the scheme to work it is necessary and sufficient that
$m \ge (1+\eps)n$ for an arbitrary constant $\eps>0$, where $n$ is the number
of keys stored.
Pagh and Rodler's analysis establishes expected amortized constant time for
insertion; for the analysis to work it is required that the hash functions are
$c \log n$-wise independent. In experiments, cuckoo hashing works very
well with weaker hash function classes. However, Pagh and Rodler report on
experimental results that indicate that cuckoo hashing might not work well
in combination with the ``multiplicative class'' (which consists of functions
$h_a: [2^k]\to[2^l]$ of the form $h_a(x)=((a x)\bmod 2^k)\div 2^{k-l}$,
for $0 N^{1-\gamma}$
for some constant $\gamma>0$. On the one hand, this explains the experimental
results obtained by Pagh and Rodler and justifies a warning against using this
simple class, on the other hand, it shows that one of the ``further technical
conditions'' of the Mitzenmacher/Vadhan result, namely the requirement that key
sets must be relatively sparse in $U$, is really necessary for their result to
be true.
2) We show that cuckoo hashing with a standard almost 2-wise independent class
of hash functions (functions of the form $h_{a,b}=((ax+b)\bmod p)\bmod m$,
$p \ge |U|$ a prime number) exhibits a similar behavior as the class in 1),
again in the case where the key set is relatively dense in $U$. This is true
even in the case when the two hash functions use different prime moduli.
Further related work:
Cohen and Kane (``Bounds on the independence required for cuckoo hashing'',
unpublished manuscript, 2005, http://web.mit.edu/dankane/www/Independence%20Bounds.pdf) construct
$2$-, $3$-, and even $5$-wise independent hash families, for which cuckoo
hashing has high failure probability. However, these families are quite
contrived and far from being common.
------------------------------------------
Michael Molloy and Bruce Reed. Asymptotically optimal frugal colouring
Abstract: We prove that every graph with maximum degree D can be properly (D+1)-coloured
so that no colour appears more than O(log D/log log D) times in the neighbourhood
of any vertex. This is best possible up to the constant factor in the O(-) term.
We also provide an efficient algorithm to produce such a colouring.
------------------------------------------
Omid Amini, Louis Esperet and Jan van den Heuvel. A Unified Approach to Distance-Two Colouring of Planar Graphs
Abstract: In this paper we introduce the notion of $(A,B)$-colouring of a graph: For given vertex sets $A,B$, this is a colouring of the vertices in $B$ so that both adjacent vertices and vertices with a common neighbour in $A$ receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of plane graphs. We prove a general result which implies asymptotic versions of Wegner's and Borodin's Conjecture on these two colourings. Using a recent approach of Havet \emph{et al.}, we reduce the problem to edge-colouring of multigraphs and then use Kahn's result that the list chromatic index is close from the fractional chromatic index.
Our results are based on a strong structural lemma for planar graphs which also implies that the size of a clique in the square of a planar graph of maximum degree~$\Delta$ is at most $\frac32\,\Delta$ plus a constant.
------------------------------------------
Nikhil Bansal and Ho-Leung Chan. Weighted flow time does not admit O(1)-competitive algorithms
Abstract: We consider the classic online scheduling problem of minimizing the total weighted
flow time on a single machine with preemptions. Here, each job $j$ has an arbitrary arrival time $r_j$, weight $w_j$ and size $p_j$, and given a schedule its
flow time is defined as the duration of time since its arrival until it completes its service requirement. The first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently,
and it was widely believed that the problem admits a constant factor competitive algorithm. In this paper, we show an $\omega(1)$ lower bound on the competitive ratio of any deterministic online algorithm.
Our result is based on a novel gap amplification technique for online algorithms.
Starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly.
------------------------------------------
Paolo Ferragina, Igor Nitto and Rossano Venturini. On the bit-complexity of Lempel-Ziv compression
Abstract: One of the most famous and investigated lossless data-compression schemes is the one introduced by Lempel and Ziv about 30 years ago. This compression scheme is known as ``dictionary-based compressor'' and consists of squeezing an input string by replacing some of its substrings with (shorter) codewords which are actually pointers to a dictionary of phrases built as the string is processed. Surprisingly enough, although many fundamental results are nowadays known about the speed and effectiveness of this compression process, ``we are not aware of any parsing scheme that achieves optimality when the LZ-dictionary is in use under any constraint on the codewords other than being of equal length'' [N. Rajpoot and C. Sahinalp. Handbook of Lossless Data Compression, chapter Dictionary-based data compression. Academic Press, 2002. pag. 159]. Here optimality means to achieve the minimum number of bits in compressing each individual input string, without any assumption on its generating source.
In this paper we investigate three issues pertaining to the bit-complexity of LZ-based compressors, and we design algorithms which achieve bit-optimality in the compressed output size by taking efficient/optimal time and optimal space. These theoretical results will be sustained by some experiments that will compare our novel LZ-based compressors against the most popular compression tools
(like Gzip, Bzip) and state-of-the-art compressors (like the Compression Booster [Ferragina-Giancarlo-Manzini-Sciortino, J.ACM 52(4), 2005]).
------------------------------------------
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld and Rocco Servedio. Testing Halfspaces
Abstract: This paper addresses the problem of testing whether a Boolean-valued function $f$ is a halfspace, i.e. a function of the form $f(x)=\sgn(w \cdot x - \theta).$ We consider halfspaces over the continuous domain $\R^n$ (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube $\{-1,1\}^n$ (endowed with the uniform distribution). In both cases we give an algorithm that distinguishes halfspaces from functions that are $\epsilon$-far from any halfspace using only $\poly(\frac{1}{\epsilon})$ queries, independent of the dimension $n$.
Two simple structural results about halfspaces are at the heart of our approach for the Gaussian distribution: the first gives an exact relationship between the expected value of a halfspace $f$ and the sum of the squares of $f$'s degree-1 Hermite coefficients, and the second shows that any function that approximately satisfies this relationship is close to a halfspace. We prove analogous results for the Boolean cube $\{-1,1\}^n$ (with Fourier coefficients in place of Hermite coefficients) for balanced halfspaces in which all degree-1 Fourier coefficients are small. Dealing with general halfspaces over $\bits^n$ poses significant additional complications and requires other ingredients. These include ``cross-consistency'' versions of the results mentioned above for pairs of halfspaces with the same weights but different thresholds; new structural results relating the largest degree-1 Fourier coefficient and the largest weight in unbalanced halfspaces; and algorithmic techniques from recent work on testing juntas \cite{FKR+:02}.
------------------------------------------
Ke Yi and Qin Zhang. Multi-Dimensional Online Tracking
Abstract: We propose and study a new class of online problems, which we call {\em online tracking}. Suppose an {\em observer}, say Alice, observes a multi-valued function $f : \mathbb{Z}^+ \rightarrow \mathbb{Z}^d$ over time in an online fashion, i.e., she only sees $f(t)$ for $t\le\tnow$ where $\tnow$ is the current time. She would like to keep a {\em tracker}, say Bob, informed of the current value of $f$ at all times. Under this setting, Alice could send new values of $f$ to Bob from time to time, so that the current value of $f$ is always within a distance of $\Delta$ to the last value received by Bob. We give competitive online algorithms whose communication costs are compared with the optimal offline algorithm that knows the entire $f$ in advance. We also consider variations of the problem where Alice is allowed to send ``predictions'' to Bob, to further reduce communication for well-behaved functions. These online tracking problems have a variety of application ranging from sensor monitoring, location-based services, to publish/subscribe systems.
------------------------------------------
Krishnendu Chatterjee, Luca de Alfaro and Thomas Henzinger. Termination Criteria for Solving Concurrent Safety and Reachability Games
Abstract: We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. We present in this paper a strategy improvement algorithm for computing the value of a concurrent safety game, that is, the maximal probability with which player 1 can enforce the safety objective. The algorithm yields a sequence of player-1 strategies which ensure probabilities of winning that converge monotonically to the value of the safety game.
Our result is significant because the strategy improvement algorithm provides, for the first time, a way to approximate the value of a concurrent safety game from below. Since a value iteration algorithm, or a strategy improvement algorithm for reachability games, can be used to approximate the same value from above, the combination of both algorithms yields a method for computing a converging sequence of upper and lower bounds for the values of concurrent reachability and safety games. Previous methods could approximate the values of these games only from one
direction, and as no rates of convergence are known, they did not provide a practical way to solve these games.
------------------------------------------
Philip Klein, Shay Mozes and Oren Weimann. Shortest Paths in Directed Planar Graphs with Negative Lengths: a linear-space O(n log^2 n)-time algorithm
Abstract: We give an $O(n \log^2 n)$-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths and no negative-length cycles, and given a node s, finds the distances from s to all nodes. The best previously known algorithm requires $O(n \log^3 n)$ time and $O(n \log n)$ space.
------------------------------------------
Ioannis Caragiannis. Efficient coordination mechanisms for unrelated machine scheduling
Abstract: We present three new coordination mechanisms for scheduling $n$ selfish jobs on $m$ unrelated machines. A coordination mechanisms aims to mitigate the impact of selfishness of jobs on the efficiency of schedules by defining a local scheduling policy on each machine. The scheduling policies induce a game among the jobs and each job prefers to be scheduled on a machine so that its completion time is minimum
given the assignments of the other jobs. We consider the maximum completion time among all jobs as the measure of the efficiency of schedules. The approximation ratio of a coordination mechanism quantifies the efficiency of pure Nash equilibria (price of anarchy) of the induced game.
Our mechanisms are deterministic, local, and preemptive in the sense that the scheduling policy does not necessarily process the jobs in an uninterrupted way and may introduce some idle time. Our first coordination mechanism has approximation ratio $O(\log m)$ and always guarantees that the induced game has pure Nash equilibria to which the system converges in at most $n$ rounds. This result improves a recent bound of $O(\log^2 m)$ due to Azar, Jain, and Mirrokni and, similarly to their mechanism, our mechanism uses a global ordering of the jobs according to their distinct IDs. Next we study the intriguing scenario where jobs are anonymous, i.e., they have no IDs. In this case, coordination mechanisms can only distinguish between jobs that have different load characteristics. Our second mechanism handles anonymous jobs and has approximation ratio $O\left(\frac{\log m}{\log \log m}\right)$ although the game induced is not a potential game and, hence, the existence of pure Nash equilibria is not guaranteed by potential function arguments. However, it provides evidence that the known lower bounds for non-preemptive coordination mechanisms could be beaten using preemptive scheduling policies. Our third coordination mechanism also handles anonymous jobs and has a nice ``cost-revealing'' potential function. Besides in proving the existence of equilibria, we use this potential function in order to upper-bound the price of stability of the induced game by $O(\log m)$, the price of anarchy by $O(\log^2m)$, and the convergence time to $O(\log^2m)$-approximate assignments by a polynomial number of best-response moves. Our third coordination mechanism is the first that handles anonymous jobs and simultaneously guarantees that the induced game is a potential game and has bounded price of anarchy.
------------------------------------------
Daniel Marx. Approximating fractional hypertree width
Abstract: Fractional hypertree width is a hypergraph measure similar to tree
width and hypertree width. Its algorithmic importance comes from the
fact that, as shown in previous work \cite{grohe-marx}, constraint
satisfaction problems (CSP) and various problems in database theory
are polynomial-time solvable if the input contains a bounded-width
fractional hypertree decomposition of the hypergraph of the
constraints. In this paper, we show that for every $w\ge 0$, there
is a polynomial-time algorithm that, given a hypergraph $H$ with
fractional hypertree width at most $w$, computes a fractional
hypertree decomposition of width $O(w^3)$ for $H$. This means that
polynomial-time algorithms relying on bounded-width fractional
hypertree decompositions no longer need to be given a decomposition
explicitly in the input, since an appropriate decomposition can be
computed in polynomial time. Therefore, if ${\mathcal H}$ is a class of
hypergraphs with bounded fractional hypertree width, then constraint
satisfaction restricted to instances whose structure is in ${\mathcal H}$ is
polynomial-time solvable. This makes bounded fractional hypertree
width the most general known hypergraph property that makes CSP
polynomial-time solvable.
------------------------------------------
Bodo Manthey and Heiko Roeglin. Improved Smoothed Analysis of the k-Means Method
Abstract: The k-means method is a widely used clustering algorithm. One of its distinguished features is its speed in practice. Its worst-case running-time, however, is exponential, leaving a gap between practical and theoretical performance. Arthur and Vassilvitskii (FOCS 2006) aimed at closing this gap, and they proved a bound of $poly(n^k, 1/\sigma)$ on the smoothed running-time of the k-means method, where n is the number of data points and \sigma is the standard deviation of the Gaussian perturbation. This bound, though better than the worst-case bound, is still much larger than the running-time observed in practice.
We improve the smoothed analysis of the k-means method by showing two upper bounds on the expected running-time of k-means. First, we prove that the expected running-time is bounded by a polynomial in $n^{\sqrt k}$ and $1/\sigma$. Second, we prove an upper bound of $k^{kd} \poly(n, 1/\sigma)$, where d is the dimension of the data space. The polynomial is independent of k and d, and we obtain a polynomial bound for the expected running-time for $k, d \in O(\sqrt{\log n/\log \log n})$.
Finally, we show that k-means runs in smoothed polynomial time for one-dimensional instances.
------------------------------------------
Christos Boutsidis, Michael Mahoney and Petros Drineas. An Improved Approximation Algorithm for the Column Subset Selection Problem
Abstract: We consider the problem of selecting the ``best'' subset of
\emph{exactly $k$ columns} from an $m \times n$ matrix $A$. In
particular, we present and analyze a novel two-stage algorithm that
runs in $O(\min\{mn^2,m^2n\})$ time and returns as output an $m
\times k$ matrix $C$ consisting of exactly $k$ columns of $A$. In
the first stage (the \textit{randomized} stage), the algorithm
randomly selects $O(k \log k)$ columns according to a
judiciously-chosen probability distribution that depends on
information in the top-$k$ right singular subspace of $A$. In the
second stage (the \textit{deterministic} stage), the algorithm
applies a deterministic column-selection procedure to select and
return exactly $k$ columns from the set of columns selected in the
first stage. Let $C$ be the $m \times k$ matrix containing those $k$
columns, let $P_C$ denote the projection matrix onto the span of
those columns, and let $A_k$ denote the ``best'' rank-$k$
approximation to the matrix $A$ as computed with the singular value
decomposition. Then, we prove that
$$
\TNorm{A - P_CA}
\leq O\left(k^{\frac 3 4}\log^{\frac 1 2}(k)\left(n-k\right)^{\frac 1 4}\right)\TNorm{A-A_k},
$$
with probability at least $0.7$. This spectral norm bound improves
upon the best previously-existing result (of Gu and
Eisenstat~\cite{GE96}) for the spectral norm version of this Column
Subset Selection Problem. We also prove that
$$
\FNorm{A - P_CA} \leq O\left(k \sqrt{\log k}\right) \FNorm{A-A_k},
$$
with the same probability. This Frobenius norm bound is only a
factor of $\sqrt{k \log k}$ worse than the best previously existing
existential result and is roughly $O(\sqrt{k!})$ better than the
best previous algorithmic result (both of Deshpande et
al.~\cite{DRVW06}) for the Frobenius norm version of this Column
Subset Selection Problem.
------------------------------------------
Michael Drmota and Wojciech Szpankowski. (Un)Expected Behavior of Digital Search Tree Profile
Abstract: A digital search tree (DST) -- one of the most
fundamental data structure on words -- is a digital tree in which keys
(strings, words) are stored directly in (internal) nodes. Such trees
find myriad of applications from the popular Lemepl-Ziv'78 data
compression scheme to distributed hash tables. The profile of a DST
measures the number of nodes at the same distance from the root; it is
a function of the number of stored strings and the distance from the
root. Most parameters of DST (e.g., height, fill-up, shortest path) can
be expressed in terms of the profile. However, from the inception of
DST analysis of the profile has been elusive and it has become a prominent
open problem in the area of analysis of algorithms. We make here the
first, but decisive step, towards solving this problem. We present a
precise analysis of the average profile when stored strings are
generated by a biased memoryless source. The main technical difficulty of
analyzing the profile lies in solving a sophisticated recurrence equation.
We present such a solution for the Poissonized version of the problem
(i.e., when the number of stored strings is generated by a Poisson
distribution) in the Mellin transform domain. To accomplish it, we introduce
a novel functional operator that allows us to express the solution in an
explicit form, and then using analytic algorithmics tools we
extract asymptotic behavior of the profile as a function of the
number of stored strings and the distance from the root. This analysis
is surprisingly demanding but once it is carried out it reveals
unusually intriguing and interesting behavior. The average profile
undergoes several phase transitions when moving from the root to the
longest path. It first resembles a full tree until it abruptly starts
growing polynomially. Furthermore, the expected profile is oscillating
in a range where profile grows polynomially. Such a behavior is quite
unexpected for most shape parameters of random trees, except recently
analyzed profiles of tries which are another incarnations of digital
trees. Our results are derived by methods of analytic algorithmics
such as generating functions, Mellin transform, Poissonization and
de-Poissonization, the saddle-point method, singularity analysis and
uniform asymptotic analysis.
------------------------------------------
Nikhil Bansal, Zachary Friggstad, Rohit Khandekar and Mohammad Salavatipour. A logarithmic approximation for the unsplittable flow on line graphs
Abstract: We consider the unsplittable flow problem on a line. In this problem, we are given a set of $n$ tasks, each specified by a start time $s_i$, and end time $t_i$, a demand $d_i>0$, and a profit $p_i>0$. A task, if accepted, requires $d_i$ units of ``bandwidth'' from time $s_i$ to $t_i$ and accrues a profit of $p_i$. For every time $t$, we are also specified the available bandwidth $c_t$, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints.
We present the first polynomial-time $O(\log n)$-approximation algorithm for this problem. This significantly advances the state-of-the-art, as no polynomial-time $o(n)$-approximation was known previously. Previous results for this problem were known only in more restrictive settings. In particular, either if instance satisfies the so-called ``no-bottleneck'' assumption: $\max_i d_i \leq \min_t c_t$, or else if the ratio of both the maximum to the minimum demands and the maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in $n$.
Our result, on the other hand, does not require any of these assumptions.
Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an $\Omega(n)$ integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.
------------------------------------------
Edith Cohen, Nick Duffield, Haim Kaplan, Carsten Lund and Mikkel Thorup. Variance-optimal sampling-based estimation of subset sums
Abstract: From a high volume stream of weighted items, we want to maintain a
generic sample of a certain limited size k that we can later use to
estimate the total weight of arbitrary subsets. This is the classic
context of on-line reservoir sampling, thinking of the generic sample
as a reservoir. We present an efficient reservoir sampling scheme, VarOpt_k,
that dominates all previous schemes in terms of estimation quality.
VarOpt_k provides variance optimal unbiased
estimation of subset sums. More precisely, if we have seen n items
of the stream, then for any subset size m, our scheme based on k
samples minimizes the average variance over all subsets of size
m. In fact, it is the first online scheme with this property and the
optimality is against any off-line sampling scheme tailored for the
concrete set of items seen: no off-line scheme based on k samples
can perform better than our on-line scheme when it comes to average
variance over any subset size. In addition to optimal average
variance, our scheme provides tighter worst-case bounds on the
variance of particular subsets than previously possible, even by
an offline scheme. It is efficient, handling each new item of
the stream in O(log k) time, which is optimal even on the word RAM.
Finally, it is particularly well suited for combination of samples
from different streams in a distributed setting.
------------------------------------------
Sergio Cabello. Finding shortest contractible cycles in embedded graphs
Abstract: We give a polynomial-time algorithm to find
a shortest contractible cycle (i.e. a closed walk without repeated vertices)
in a graph embedded in a surface.
This answers a question posed by Mohar and Thomassen.
In contrast, we show that finding a shortest contractible cycle
through a given vertex is NP-hard.
We also show that finding a shortest separating cycle
in an embedded graph is NP-hard.
------------------------------------------
Khaled Elbassioni, Rajiv Raman, Saurabh Ray and Rene Sitters. On the approximability of the maximum feasible subsystem problem with 0/1-coefficients
Abstract: Given a system of inequalities $\ell_i\leq a_i^Tx\le u_i$, where $a_i\in\{0,1\}^n$, and $\ell_i,u_i\in \RR_+$, for $i=1,\ldots, m$, we consider the problem of finding the largest subsystem for which there exists a feasible solution $x\geq 0$. We give several approximability and inapproximability results, parameterized by the value of $L=\max\{\ell_1,\ldots,\ell_m\}$. In particular, we show that, under reasonable complexity assumptions, the problem cannot be approximated within a factor of
$O(\log ^{\mu} n)$, for some positive $\mu$, even when $\ell_i=u_i=1$ for all $i$, and within a factor of $O(n^{1/3-\epsilon})$, for an arbitrarily small $\epsilon>0$, if $L$ is arbitrarily large. On the way, we also obtain an $\Omega(n^{1/3-\epsilon})$-inapproximability threshold for the {\it maximum induced matching problem} on bipartite graphs.
On the positive side, we consider $(\alpha,\beta)$-approximations, i.e., of finding a subsystem with size at least $|\OPT|/\alpha$, which has a feasible solution violating the right-hand side by a factor of at most $\beta$. For general $0/1$-coefficient matrices, we give a polynomial-time $(O(\log(nm)),1+\epsilon)$-approximation for the case when $L=\poly(n,m)$. For interval matrices, we give a quasi-polynomial time $(1,1+\epsilon)$-approximation when $L=\poly(n,m)$ and a polynomial time $(O(\log^2n\log\log (nL)),1+\epsilon)$- approximation in the general case, and complement the first result by showing that, when no violation is allowed, the problem is APX-hard. Clearly all the above results apply to systems of equations ($l_i=u_i$) with $0/1$-coefficients. As further applications, we show how these results apply to a recently-studied profit-maximizing pricing problem, and to the problem of drawing interval graphs given length constraints on the intervals.
------------------------------------------
S. Charles Brubaker. Clustering on Noisy Mixtures
Abstract: This paper presents a polynomial algorithm for learning mixtures of log-concave distributions in R^n in the presence of malicious noise points. That is, each sample is corrupted with some small probability and replaced by a point about which we can make no assumptions. A key element of the algorithm is Robust Principle Components Analysis (PCA), which is less susceptible to corruption by noisy points. Where noise may cause standard PCA to collapse well-separated mixture components so that they are indistinguishable, Robust PCA preserves the distance between the some of the components, making a partition possible. It then recurses on each half of the mixture until every component is isolated. The success of this algorithm requires only a O(log n) factor increase in the required separation between components of the mixture compared to the noiseless case.
------------------------------------------
Ashish Goel, Michael Kapralov and Sanjeev Khanna. Perfect matchings via uniform sampling in regular bipartite graphs
Abstract: Regular bipartite graphs occur in many real life applications, including
scheduling, routing, and task assignment. In particular, finding a perfect
matching in a regular bipartite graph is a well-studied problem. The first
non-trivial algorithm, with running time $O(mn)$, dates back to K\"{o}nig's
work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ the
number of vertices, and $d$ the degree of each node). The currently most
efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and
Schirra. In this paper, we further improve this running time to
$O(\min\{m,n^{1.75}\ln n\})$. We obtain this improvement by proving a uniform
sampling theorem: if we sample each edge in a $d$-regular bipartite graph
independently with a probability $p = O(\frac{n\ln n}{d^2})$ then the
resulting graph has a perfect matching with high probability. The proof
involves a sequential decomposition procedure combined with an application
of Karger's sampling theorem in each piece. Running the $O(m\sqrt{n})$
algorithm (due to Hopcroft and Karp) for finding maximum matchings in
bipartite graphs on the sampled graph yields the stated running time. We
provide an infinite family of instances to show that the sampling result is
tight up to polylogarithmic factors. Thus any super-polylogarithmic
improvements to our running time must either employ a different sampling
procedure or improve the Hopcroft-Karp algorithm for the case of nearly
regular bipartite graphs.
------------------------------------------
David Karger and Debmalya Panigrahi. An $\tilde{O}(m)$ algorithm for constructing a cactus of an undirected graph
Abstract: We present an $\tilde{O}(m)$ algorithm for constructing the {\em cactus} data structure of an undirected graph, which captures all the global minimum edge cuts in the graph in $O(n)$ space. This represents a fundamental improvement over the previous best time bounds ($\tilde{O}(n^2)$ due to Karger and Stein) since the number of mincuts in an undirected graph can be $\tilde{\omega}(m)$, but has to be $O(n^2)$. Thus, unlike earlier algorithms, our algorithm cannot afford to spend even $O(1)$ time per mincut. Further, our result closes the gap between the time required for finding a single mincut ($\tilde{O}(m)$ due to Karger) and that for (implicitly) finding all the mincuts. Similar to the previous best algorithm, our algorithm is Monte-Carlo, ie gives the correct answer with high probability but does not give a certificate for checking correctness.
------------------------------------------
Joel Tropp. Efficient Algorithms for Column Subset Selection
Abstract: Given a fixed matrix, the problem of column subset selection requests a column submatrix that has favorable spectral properties. Most research from the algorithms and numerical linear algebra communities focuses on a variant called rank-revealing {\sf QR}, which seeks a well-conditioned collection of columns that spans the (numerical) range of the matrix. The functional analysis literature contains another strand of work on column selection whose algorithmic implications have not been explored. In particular, a celebrated result of Bourgain and Tzafriri demonstrates that each matrix with normalized columns contains a large column submatrix that is exceptionally well conditioned. Unfortunately, standard proofs of this result cannot be regarded as algorithmic.
This paper presents a randomized, polynomial-time algorithm that produces the submatrix promised by Bourgain and Tzafriri. The method involves random sampling of columns, followed by a matrix factorization that exposes the well-conditioned subset of columns. This factorization, which is due to Grothendieck, is regarded as a central tool in modern functional analysis. The primary novelty in this work is an algorithm, based on eigenvalue minimization, for constructing the Grothendieck factorization. These ideas also result in a novel approximation algorithm for the $(\infty, 1)$ norm of a matrix, which is generally {\sf NP}-hard to compute exactly. As an added bonus, this work reveals a surprising connection between matrix factorization and the famous {\sc maxcut} semidefinite program.
------------------------------------------
Gabriel Nivasch. Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
Abstract: We present several new results regarding lambda_s(n), the maximum length of a Davenport-Schinzel sequence of order s on n distinct symbols.
First, we prove that lambda_s(n) <= n * 2^{1/t! alpha(n)^t + O(alpha(n)^{t-1})} for s>=4 even, and lambda_s(n) <= n * 2^{1/t! alpha(n)^t log_2 alpha(n) + O(alpha(n)^t)} for s>=3 odd, where t = floor((s-2)/2), and alpha(n) denotes the inverse Ackermann function. This constitutes an improvement for s>=6, since the previous bounds, by Agarwal, Sharir, and Shor (1989), had a leading coefficient of 1 instead of 1/t! in the exponent. The bounds for even s>=6 are now tight up to lower-order terms in the exponent. These new bounds result from a small improvement on the technique of Agarwal et al.
More importantly, we also present a new technique for deriving upper bounds for lambda_s(n). This new technique is based on some recurrences very similar to the ones used by the author, together with Alon, Kaplan, Sharir, and Smorodinsky (SODA 2008), for the problem of stabbing interval chains with j-tuples. With this new technique we: (1) re-derive the upper bound of lambda_3(n) <= 2n alpha(n) + O(n sqrt alpha(n)) (first shown by Klazar, 1999); (2) re-derive our own new upper bounds for general s; and (3) obtain improved upper bounds for the generalized Davenport-Schinzel sequences considered by Adamec, Klazar, and Valtr (1992).
Regarding lower bounds, we show that lambda_3(n) >= 2n alpha(n) - O(n) (the previous lower bound (Sharir and Agarwal, 1995) had a coefficient of 1/2), so the coefficient 2 is tight. We also present a simpler variant of the construction of Agarwal, Sharir, and Shor that achieves the known lower bounds of lambda_s(n) >= n * 2^{1/t! alpha(n)^t - O(alpha(n)^{t-1})} for s>=4 even.
------------------------------------------
Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP
Abstract: Sets of permutations play an important role in the design of some efficient algorithms. In this paper we design two algorithms that manipulate sets of permutations. Both algorithms, each solving a different problem, use fast matrix multiplication techniques to achieve a significant improvement in the running time over the naive solutions.
A set of permutations $P \subset S_n$ is {\em expanding} if the product of any two elements of $P$ yields a distinct permutation. Stated otherwise, $|P^2|=|P|^2$ where $P^2 \subset S_n$ is the set of products of two elements of $P$.
Our first result is a randomized algorithm that computes $|P^2|$ and hence decides if $P$ is expanding. The algorithm also produces a table that, for any $\sigma_1,\sigma_2,\sigma_3,\sigma_4 \in P$, answers the query
$\sigma_1\sigma_2 = \sigma_3\sigma_4$ in $\tilde{O}(1)$ time.
The algorithm uses, among other ingredients, a combination of fast matrix multiplication and polynomial identity testing.
In particular, for $|P|=n$ our algorithm runs in $O(n^\omega)$ time
where $\omega < 2.376$ is the matrix multiplication exponent. We note that the naive deterministic solution for this
problem requires $\Theta(n^3)$ time.
For a set of permutations $P \subset S_n$ we say that $i$ $k$-dominates $j$ if
the number of permutations $\pi \in P$ for which $\pi(i) < \pi(j)$ is $k$.
The {\em dominance matrix} of $P$ is the $n \times n$ matrix
$D_P$ where $D_P(i,j)=k$ if and only if $i$ $k$-dominates $j$.
We give an efficient algorithm for computing $D_P$ using fast {\em rectangular} matrix multiplication. In particular, when $|P|=n$ our
algorithm runs in $O(n^{2.684})$ time. Computing the dominance matrix of permutations is computationally equivalent to the dominance
problem in computational geometry. In particular,
our algorithm slightly improves upon a well-known $O(n^{(\omega+3)/2})$ time algorithm of Matousek for the dominance problem.
Permutation dominance is used, together with a few other ingredients, to obtain a
truly sub-cubic algorithm for the {\em All Pairs Shortest Paths} (APSP)
problem in real-weighted directed graphs, where the number of distinct weights emanating from each vertex is $O(n^{0.338})$.
A very special case of this algorithm implies an $O(n^{2.842})$ time algorithm for real vertex-weighted APSP, which slightly improves a
recent result of Chan [STOC-07].
------------------------------------------
Gabor Tardos and Ehsan Amiri. High rate fingerprinting codes and the fi ngerprinting capacity
Abstract: Including a unique code in each copy of a distributed document is an effective
way of fighting intellectual piracy. Codes designed for this purpose that are
secure against collusion attacks are called fingerprinting codes.
In this paper we consider fingerprinting with the marking assumption and
design codes that achieve much higher rates than previous
constructions. We conjecture that these codes attain the maximum possible
rate (the fingerprinting capacity) for any fixed number of pirates.
We prove new upper bounds for the fingerprinting capacity that are not far
from the rate of our codes.
We introduce the novel model of weak fingerprinting codes where one
pirate should be caught only if the identity of all other pirates are
revealed. We construct fingerprinting codes in this model with improved rates
but our upper bound on the rate still applies. In fact, these improved
codes achieve the fingerprinting capacity of the weak model by a recent upper
bound.
Using analytic techniques we compare the rates of our codes in the standard
model and the rates of the optimal codes in the weak model. To our surprise
these rates asymptotically agree, that is, their ratio tends to $1$ as $t$
goes to infinity. Although we cannot prove that each one of our codes in the
standard model achieves the fingerprinting capacity, this proves that
asymptotically they do.
------------------------------------------
Yury Person and Mathias Schacht. Almost all hypergraphs without Fano planes are bipartite
Abstract: The hypergraph of the Fano plane is the unique hypergraph with $7$ triples on $7$ vertices in which every pair of vertices is contained in a unique triple. It is not $2$-colorable, but becomes so on deleting any hyperedge. We show that taking uniformly at random a $3$-uniform hypergraph $H$ on $n$ vertices not containing the Fano plane, $H$ turns out to be bipartite (or $2$-colorable) with probability at least $1-2^{-\Omega(n^2)}$. To prove this result we will study structural properties of Fano plane-free hypergraphs. In particulary, we prove that only with exponentially small probability ($2^{-\Omega(n^3)}$) they are $\eps$-far from being bipartite.
These results seem to be interesting in the light of the well-known fact, that to decide whether a given $3$-uniform hypergraph is bipartite is $NP$-complete. On the other hand, the property of being bipartite is known to be testable. We hope that understanding better the structure of (hyper-)graph properties might be useful for average case analysis of running time of coloring algorithms on restricted hypergraph classes, and also advantageous in developing efficient property testers.
------------------------------------------
Amr Elmasry. Pairing Heaps with $O(\log{\log{n}})$ {\it decrease} Cost
Abstract: We give a variation of the pairing heaps for which the time bounds for all the operations match the lower bound proved by Fredman for a family of similar self-adjusting heaps.
Namely, our heap structure requires $O(1)$ for insert and find-min, $O(\log{n})$ for delete-min, and $O(\log\log{n})$ for decrease-key and meld (all the bounds are in the amortized sense except for find-min).
------------------------------------------
Haim Kaplan and Uri Zwick. A simpler implementation and analysis of Chazelle's Soft Heaps
Abstract: Chazelle (JACM 47(6), 2000) devised an approximate meldable
priority queue data structure, called SOFT HEAPS, and used it
to obtain the fastest known deterministic comparison-based algorithm
for computing minimum spanning trees, as well as some new algorithms
for selection and approximate sorting problems. If $n$ elements are
inserted into a collection of soft heaps, then up to $\epsilon n$ of the elements
still contained in these heaps, for a given \emph{error
parameter} $\epsilon$, may be CORRUPTED, i.e., have their keys
artificially increased. In exchange for allowing these corruptions,
each soft heap operation is performed in $O(\log\frac{1}{\eps})$
amortized time.
Chazelle's soft heaps are derived from the BINOMIAL HEAPS
data structure in which each priority queue is composed of a collection of
BINOMIAL TREES. We describe a simpler and more direct
implementation of soft heaps in which each priority queue is composed of a
collection of standard BINARY trees. Our implementation has
the advantage that no CLEAN-UP operations similar to the ones
used in Chazelle's implementation are required. We also present a
concise and unified potential-based amortized analysis of the new
implementation.
------------------------------------------
Mikkel Thorup, Uri Zwick and Omid Madani. Discounted Deterministic Markov Decision Processes and Discounted All-Pairs Shortest Paths
Abstract: We present an $O(mn+n^2\log n)$-time algorithm for finding optimal
strategies for discounted, infinite-horizon, Deterministic Markov
Decision Processes (DMDP), where $n$ is the number of vertices (or
states) and $m$ is the number of edges (or actions). This improves a
recent $O(mn^2)$-time algorithm of Andersson and Vorobyov.
We also present algorithms for finding discounted all-pairs shortest paths.
------------------------------------------
Alon Shalita and Uri Zwick. Efficient algorithms for the 2-gathering problem
Abstract: Pebbles are placed on some vertices of a directed graph. Is it possible
to move each pebble along at most one edge of the graph so that in
the final configuration no pebble is left alone? We give an $O(mn)$-time
algorithm for solving this problem, which we call the 2-GATHERING
problem, where $n$ is the number of vertices and $m$ is the number
of edges of the graph. If such a 2-gathering is not possible, the
algorithm finds a solution that minimizes the number of `lonely' pebbles.
The 2-gathering problem forms a non-trivial generalization of the
non-bipartite matching problem and it is solved by extending the augmenting
paths technique used to solve matching problems.
Polynomial time algorithms for the 2-gathering problem can be
obtained via reductions to the \{K_{2},K_{3}\}-packing problem
studied by Hell and Kirkpatrick, the general factor problem studied
by Cornue'jols, and to the simplex matching problem studied recently
by Anshelevich and Karagiozova. The resulting algorithms, however,
are much slower than the new algorithm presented.
------------------------------------------
david cohen-steiner, Herbert Edelsbrunner, John Harer and Dmitriy Morozov. Persistent Homology for Kernels, Images, and Cokernels
Abstract: Motivated by the measurement of local homology and of functions on noisy domains, we extend the notion of persistent homology to sequences of kernels, images, and cokernels of maps induced by inclusions in a filtration of pairs of spaces. Specifically, we note that persistence in this context is well defined, we prove that the persistence diagrams are stable, and we explain how to compute them.
------------------------------------------
Fedor Fomin, Petr Golovach, Daniel Lokshtanov and Saket Saurabh. Clique-width: On the Price of Generality
Abstract: Many hard problems can be solved efficiently when the input is restricted to graphs
of bounded treewidth. By the celebrated result of Courcelle, every decision problem
expressible in monadic second order logic is fixed parameter tractable when parameterized by the treewidth of the input graph. Moreover, for every fixed k ? 0, such problems can be solved in linear time on graphs of treewidth at most k. In particular, this implies that basic problems like Dominating Set, Graph Coloring, Clique, and Hamiltonian Cycle are solvable in linear time on graphs of bounded treewidth.
A significant amount of research in graph algorithms has been devoted to extending this result to larger classes of graphs. It was shown that some of the algorithmic meta-theorems for treewidth can be carried over to graphs of bounded clique-width. Courcelle, Makowsky, and Rotics proved that the analogue of Courcelle?s result holds for graphs of bounded clique-width when the logical formulas do not use edge set quantifications. Despite of its generality, this does not resolve the parameterized complexity of many basic problems concerning edge subsets (like Edge Dominating Set), vertex partitioning (like Graph Coloring), or global connectivity (like Hamiltonian Cycle). There are various algorithms solving some of these problems in polynomial time on graphs of clique-width at most k. However, these are not fixed parameter tractable algorithms and have typical running times O(n^f(k)), where n is the input length and f is some function.
It was an open problem, explicitly mentioned in several papers, whether any of these problems is fixed parameter tractable when parameterized by the clique-width, i.e. solv-able in time O(g(k)·n^c), for some function g and a constant c not depending on k. In this paper we resolve this problem by showing that Edge Dominating Set, Hamiltonian Cycle, and Graph Coloring are W[1]-hard parameterized by clique-width. This shows that the running time O(n^f(k)) of many clique-width based algorithms is essentially the best we can hope for (up to a widely believed assumption from parameterized complexity, namely FPT != W[1])?the price we pay for generality.
------------------------------------------
Parinya Chalermsook and Julia Chuzhoy. Maximum Independent Set of Rectangles
Abstract: We study the Maximum Independent Set of Rectangles problem (MISR): given a collection R of n axis-parallel rectangles, find a maximum-cardinality subset of disjoint rectangles. MISR is a special case of the classical Maximum
Independent Set problem, where the input is restricted to intersection graphs of axis-parallel rectangles. Due to its many applications, ranging from map labeling to data mining, MISR has received a significant amount of attention from various research communities. Since the problem is NP-hard, the main focus has been on designing approximation algorithms. Several groups of researches have independently suggested O(log n)-approximation algorithms for MISR, and this remained the best currently known approximation factor for the problem. The main result of our paper is an O(log log n)-approximation algorithm for MISR. Our algorithm combines existing approaches for solving special cases of the problem, in which the input set of rectangles is restricted to containing only specific intersection types, with new insights into the combinatorial structure of sets of intersecting rectangles in
the plane.
We also consider a generalization of MISR to higher dimensions, where rectangles are replaced by d-dimensional hyper-rectangles. This problem is known as Maximum Independent Set on d-box graphs. Our results for MISR imply an O((log n)^{d-2}loglog n) approximation algorithm for this problem, improving upon the best previously known O((log n)^{d-1})-approximation.
------------------------------------------
Brendan Nagle, Annika Poerschke, Vojtech Rödl and Mathias Schacht. On Algorithmic Hypergraph Regularity
Abstract: Thomason and Chung, Graham, and Wilson were the first to systematically
study
quasi-random graphs and hypergraphs, and proved that
several properties of random graphs imply each other in a determinstic
sense. Their concepts of quasi-randomness
match the notion of regularity from
the earlier
Szemeredi Regularity Lemma.
In contrast,
there exists no "natural" hypergraph regularity lemma matching the notions of
quasi-random hypergraphs considered by those authors.
Here, we study several notions of
quasi-randomness for 3-uniform hypergraphs
which correspond to the regularity lemmas of Frankl and Rödl,
Gowers and Haxell, Nagle and Rödl.
We establish an equivalence among the three notions of regularity
of these lemmas. Since the regularity lemma of Haxell et al. is
algorithmic, we obtain algorithmic versions of the lemmas of
Frankl-Rödl (a special case thereof)
and Gowers as corollaries. As a further corollary, we show
that the special case of the Frankl-Rödl lemma (which we can make
algorithmic)
suffices for an application of its corresponding Counting Lemma.
------------------------------------------
Robi Krauthgamer, Seffi Naor and Roy Schwartz. Partitioning Graphs into Balanced Components
Abstract: We consider the {\em $k$-balanced partitioning} problem, where the
goal is to partition the vertices of an input graph $G$ into $k$
equally sized components, while minimizing the total weight of the
edges connecting different components. We allow $k$ to be part of
the input and denote the cardinality of the vertex set by $n$.
This problem is a natural and important generalization of
well-known graph partitioning problems, including {\em minimum
bisection} and {\em minimum balanced cut}.
We present a bi-criteria approximation algorithm that achieves
an approximation factor of $O(\sqrt{\log{n}\log{k}})$, which
matches or improves over previous algorithms for all relevant values of
$k$. Our algorithm uses a semidefinite relaxation which combines
$\ell _2^2$ metrics with spreading metrics. Surprisingly, we show
that the integrality gap of the semidefinite relaxation is $\Omega
(\log{k})$ even for large values of $k$ (e.g., $k=n^{\Omega(1)}$),
implying that the dependence on $k$ of the approximation factor is
necessary. This is in contrast to the situation with previous
approximation algorithms for $k$-balanced partitioning which are
based on linear programming relaxations and where the
approximation factor is independent of $k$.
------------------------------------------
Nikhil Bansal, Ho-Leung Chan and Kirk Pruhs. Speed Scaling with an Arbitrary Power Function
Abstract: All of the theoretical speed scaling research to date has assumed that the
power function, which expresses the power consumption $P$ as a function
of the processor speed $s$,
is of the form $P=s^\alpha$, where $\alpha > 1$ is some constant.
Motivated in part by technological advances,
we initiate a study of speed scaling with arbitrary
power functions.
We consider the problem of minimizing the total flow plus energy.
Our main result is a $(3+\epsilon)$-competitive algorithm for this problem, that holds
for essentially any power function.
We also give a $(2+\epsilon)$-competitive algorithm for the objective of
fractional weighted flow plus energy.
Even for power functions of the form $s^\alpha$, it was not previously
known how to obtain competitiveness independent of $\alpha$ for
these problems.
We also introduce a model of allowable speeds that generalizes
all known models in the literature.
------------------------------------------
Zdenek Dvorak, Daniel Kral and Robin Thomas. Coloring triangle-free graphs on surfaces
Abstract: Gimbel and Thomassen asked whether the 3-colorability of a triangle-free graph drawn on a fixed surface can be tested in polynomial time. We settle the question by giving a linear-time algorithm for every surface. When combined with previous results this gives a linear-time algorithm to compute the chromatic number of a triangle-free graph drawn on a fixed surface.
Our algorithm is based on a structure theorem that for a triangle-free graph drawn on a surface S guarantees the existence of (and can be converted to a linear-time algorithm to find) a subgraph H, whose size depends only on S, such that there is an easy test whether a 3-coloring of H extends to a 3-coloring of G. The test is based on a topological obstruction, called the ``winding number" of a 3-coloring. To prove the structure theorem we make use of disjoint paths with specified ends (a.k.a. integral multicommodity flows) to find a 3-coloring.
If the input triangle-free graph G drawn in S is 3-colorable we can find a 3-coloring in quadratic time, and if G quadrangulates S then we can find the 3-coloring in linear time. The latter algorithm requires two ingredients that may be of independent interest: a generalization of a data structure of Kowalik and Kurowski to weighted graphs and a speedup of a disjoint paths algorithm of Robertson and Seymour to linear time.
------------------------------------------
Amitabh Basu, Pierre Bonami, gerard cornuejols and Francois Margot. On the Relative Strength of Split, Triangle and Quadrilateral Cuts (Extended Abstract)
Abstract: Integer programs defined by two equations with two free integer
variables and nonnegative continuous variables have three types of
nontrivial facets: split, triangle or quadrilateral inequalities. In this
paper, we compare the strength of these three families of inequalities.
In particular we study how well each family approximates the integer hull.
We show that, in a well defined sense, triangle inequalities provide
a good approximation of the integer hull. The same statement holds for
quadrilateral inequalities. On the other hand, the approximation produced by
split inequalities may be arbitrarily bad.
------------------------------------------
Raphael Clifford, Klim Efremenko, Ely Porat and Amir Rothschild. From coding theory to efficient pattern matching
Abstract: We consider the classic problem of pattern matching with few mismatches in the presence of promiscuously matching wildcard symbols. Given a text t of length n and a pattern p of length m with optional wildcard symbols and a bound k, our algorithm finds all the locations for which the pattern matches the text with Hamming distance at most k. The algorithm we present is deterministic and runs in \tilde{O}(kn) time, returning the location of each mismatch at no extra cost. The solutions we develop borrow from the tool set of algebraic coding theory and provide a new framework in which to tackle approximate pattern matching problems.
------------------------------------------
Ramesh Hariharan and Anand Bhalgat. Fast Edge Orientation for Unweighted Graphs
Abstract: We consider an unweighted undirected graph with $n$ vertices,
$m$ edges, and edge connectivity $2k$. The {\em weak edge orientation problem} requires that the edges of this graph be oriented so the resulting directed graph is at least $k$ edge connected.
Nash-Williams proved the existence of such orientations and subsequently Frank \cite{F93}, Gabow \cite{G94}, and Nagamochi-Ibaraki gave algorithmic constructions. All of these algorithm took time at least quadratic in $n$. We provide the first sub-quadratic (in $n$) algorithm for this problem. Our algorithm takes $\tilde{O}(nk^4+m)$ time. This improves the previous best bounds of $\tilde{O}(n^2k^2+m)$ by Gabow \cite{G94} and $\tilde{O}(n^2m)$ by Nagamochi-Ibaraki when $k \le \sqrt{n}$.
Indeed, many real networks have $k\ll n$.
Our algorithm uses the fast edge splitting paradigm introduced by Bhalgat et al. \cite{BHKP08}. We seek to split out a large fraction of the vertices, recurse on the resulting graph, and then put back the split-off vertices. The main challenge we face is that only vertices with even degree may be split-off in an undirected graph and there may not be any such vertex in the current graph.
The edge orientation algorithms of Gabow and Nagamochi-Ibaraki as well as Frank's proof are based on showing the existence of at least two even degree vertices (in fact, vertices with degree $2k$) in a $2k$ minimally connected graph. We generalize this to show that in any edge minimal $2k$ connected graph, there are at least $n/3$ even degree vertices. These vertices are then split-off.
Our next challenge is to drop edges from the given graph so it remains $2k$ connected and yet has $\Omega(n)$ even degree vertices. We provide two algorithms for this. The first algorithm produces an edge-minimal $2k$ connected
graph in time $\tilde{O}(nk^5+m)$; this improves the previous best $\tilde{O}(n^2k^2 + m)$ algorithm for this task due to by Gabow \cite{G94}. The second algorithm speeds this up
by a factor of $k$ by giving up the minimality criterion; it discards edges specifically to produce $\Omega(n)$ even degree vertices while maintaining connectivity $2k$ and takes time $\tilde{O}(nk^4+m)$.
------------------------------------------
Viswanath Nagarajan and Maxim Sviridenko. On the Maximum Quadratic Assignment Problem
Abstract: Quadratic assignment is a basic problem in combinatorial optimization, which generalizes several other problems such as Traveling Salesman, Linear Arrangement, Dense k Subgraph, and Clustering with given sizes. Quadratic Assignment is defined relative to two n by n symmetric non-negative matrices. In this paper, we study the Maximum Quadratic Assignment problem, and give an ~\sqrt{n} approximation algorithm, which is the first non-trivial approximation guarantee for this problem. The above guarantee also holds when the input matrices are asymmetric. An indication of the hardness of Maximum Quadratic Assignment is that it contains as a special case, the Dense k Subgraph problem, for which the best known approximation guarantee is ~n^{1/3} (Feige et al.~2001).
When one of the matrices satisfies triangle inequality, we give an algorithm achieving approximation ratio ~ 3.16, which improves over the previous best factor of 4 (Arkin et al. 2001).
See complete abstract in pdf file.
------------------------------------------
Bernard Chazelle. Natural Algorithms
Abstract: We provide further evidence
that the study of complex self-organizing systems
can benefit from an algorithmic perspective.
The subject has been traditionally
viewed through the lens of physics and control theory.
Using tools associated with computer science,
we settle a longstanding
open question in theoretical ecology: the
convergence of bird flocks in the Reynolds model.
We bound the time to reach steady state
by a tower-of-twos of height exponential in the number of birds.
We prove that, surprisingly, the
tower-of-twos growth is intrinsic to the model.
This unexpected result demonstrates the merits of approaching
biological dynamical systems as "natural algorithms"
and applying algorithmic tools to them.
------------------------------------------
Timothy M. Chan. Comparison-Based, Time-Space Lower Bounds for Selection
Abstract: We establish the first nontrivial lower bounds on time-space tradeoffs
for the selection problem. We prove that any comparison-based,
randomized algorithm for finding the median requires
$\Omega(n\log\log_S n)$ expected time in the RAM model (or more
generally in the comparison branching program model), if we have $S$
bits of extra space besides the read-only input array. This bound is
tight for all $S\gg\log n$, and remains true even if the array is
given in a random order. Our result thus answers a 16-year-old
question of Munro and Raman, and also complements recent lower bounds
that are restricted to sequential access, as in the multi-pass
streaming model [Chakrabarti \etal, SODA 2008].
We also prove that any comparison-based, deterministic, multi-pass
streaming algorithm for finding the median requires
$\Omega(n\log^*(n/s) + n\log_s n)$ worst-case time (in scanning plus
comparisons), if we have $s$ cells of space. This bound is also tight
for all $s\gg\log^2 n$. We can get similar deterministic lower bounds for
I/O-efficient algorithms, or for the two-dimensional linear
programming problem.
All proofs are ``elementary''.
------------------------------------------
Peyman Afshani and Timothy M. Chan. Optimal Halfspace Range Reporting in Three Dimensions
Abstract: We give the first optimal solution to a standard problem in
computational geometry: three-dimensional halfspace range reporting.
We show that $n$ points in 3-d can be stored in a linear-space data
structure so that all $k$ points inside a query halfspace can be
reported in $O(\log n+k)$ time. The data structure can be built in
$O(n\log n)$ expected time. The previous methods with optimal query
time requires superlinear ($O(n\log\log n)$) space.
We mention consequences to external-memory data structures, and as an
aside, we partially answer another open question concerning the
crossing number in Matou\v sek's {\em shallow partition theorem\/} in the
3-d case (a tool used in known halfspace range reporting methods).
------------------------------------------
Justin Salez and Devavrat Shah. Optimality of Belief Propagation for Random Assignment Problem
Abstract: The assignment problem concerns finding the minimum cost perfect matching in a complete weighted bipartite graph. The best known algorithm, due to Edmonds and Karp (1972), for this classical question finds a solution in O(n^3) time for a graph
of size n. Clearly, any algorithm requires \Omega(n^2) time. For
decades, it has not been answered whether optimal computation time is closer to n^3 or n2? In this paper, we provide answer to this question for random instance of assignment problem. Specifically, we establish that Belief Propagation essentially finds solution in O(n2) time when edge weights are i.i.d. with light tailed distribution. To establish this result, we use the formalism of local weak convergence introduced by Aldous (1992, 2000). The standard next step requires proving existence of ?correlation decay?. Interestingly enough, even though we find that there is no correlation decay, we are still able to prove convergence of belief propagation. Understanding such different method of convergence beyond correlation decay for BP should be of interest in its own right.
------------------------------------------
Ping Li. Compressed Counting
Abstract: Counting the $\alpha$th frequency moment, $F_{(\alpha)} = \sum_{i=1}^D A_t[i]^\alpha$, of a streaming signal $A_t$ (where $t$ denotes time), has been an active area of research. When $0<\alpha\leq 2$, one popular algorithm for approximating $F_{(\alpha)}$ is based on symmetric stable random projections, whose sample complexity is $O\left(1/\epsilon^2\right)$, even for $\alpha = 1$.
Compressed Counting (CC) is proposed for efficiently computing the $\alpha$th frequency moment, also for $0<\alpha\leq2$. In the neighborhood of $\alpha = 1$, its sample complexity is $O\left(1/\epsilon\right)$, instead of $O\left(1/\epsilon^2\right)$. The underlying technique of CC is maximally-skewed stable random projections.
Our contributions include:
1) Compressed Counting (CC) is the first proposal of using skewed projections in data stream computations. We also show that maximally-skewed projections can achieve the best performance.
2) CC is the first algorithm which captures the intuition that, when $\alpha =1$ a simple counter suffices, and when $\alpha = 1\pm\Delta$ with small $\Delta$, the sample complexity should be low. We show the sample complexity of a proposed estimator $= \frac{G}{\epsilon^2}\log\left(\frac{2}{\delta}\right)$, where $G= O\left(\epsilon\right)$ as $\Delta\rightarrow 0$. In other words, for small $\Delta$, CC has the complexity $=O\left({1}/{\epsilon}\right)$. Previous results only achieved $O\left(1/\epsilon^2\right)$ (even for $\alpha =1$), which in general is expected and can not be improved, according to the central limit theorem.
3) We show, when $\alpha = 1\pm\Delta$, the asymptotic variance of a proposed estimator is $\propto \Delta$. As $\alpha \rightarrow 1$, CC achieves ``an infinite improvement'' over the previous results, in terms of the asymptotic variances.
4) Our results (especially when $\alpha=1\pm\Delta\approx 1$) have important applications. In some situation, $\Delta$ might be interpreted as the ``decay rate'' or ``interest rate,'' which is usually small. The method of moments is popular for statistical inference, which requires computing frequency moments. Also, some important summary statistics such as Renyi entropy and Tsallis entropy are functions of frequency moments and hence CC naturally provides an efficient algorithm to compute them. Very importantly, CC may serve the basic building element for developing other algorithms, for example, approximating the Shannon entropy using Renyi entropy and Tsallis entropy with $\alpha\approx 1$.
4) Our results enrich the fundamental theory of skewed stable distributions.
------------------------------------------
Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane and Mihai Patrascu. The Geometry of Binary Search Trees
Abstract: We present a novel connection between binary search trees (BSTs) and points in the plane satisfying a simple property. Using this correspondence, we achieve the following results:
1. A surprisingly clean restatement in geometric terms of many results and conjectures relating to BSTs and dynamic optimality.
2. A new lower bound for searching in the BST model, which subsumes the previous two known bounds of Wilber [FOCS'86].
3. The first proposal for dynamic optimality not based on splay trees. A natural greedy but offline algorithm was presented by Lucas [1988], and independently by Munro [2000], and was conjectured to be an (additive) approximation of the best binary search tree. We show that there exists an equal-cost online algorithm, transforming the conjecture of Lucas and Munro into the conjecture that the greedy algorithm is dynamically optimal.
------------------------------------------
Satoru Iwata and James Orlin. A Simple Combinatorial Algorithm for Submodular Function Minimization
Abstract: This paper presents a new simple algorithm for minimizing submodular functions. For integer valued submodular functions, the algorithm runs in O(n^6 EO log nM)time, where n is the cardinality of the ground set, M is the maximum absolute value of the function value, and EO is the time for function evaluation. The algorithm can be improved to run in O((n^4 EO + n^5) log nM) time. The strongly polynomial version of this faster algorithm runs in O((n^5 EO + n^6) log n) time for real valued general submodular functions. These are comparable to the best known running time bounds for submodular function minimization.
The algorithm can also be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method.
------------------------------------------
Prasad Raghavendra and David Steurer. Towards Computing the Grothendieck Constant
Abstract: The \emph{Grothendieck constant $K_G$} is the smallest constant such
that for every $n\in \N$ and every matrix $A = (a_{ij})$ the
following holds,
\begin{displaymath}
\sup_{\vec u_i,\vec v_j \in B^{(n)}}
\sum_{ij} a_{ij} \langle \vec u_i , \vec v_j\rangle
\leq K_G \cdot \sup_{x_i,y_j \in [-1,1]}
\sum_{ij} a_{ij} x_i y_j \, ,
\end{displaymath}
where $B^{( n)}$ is the unit ball in $\mathbb R^n$. Despite several
efforts \cite{krivine, reeds}, the value of the constant $K_G$
remains unknown. The Grothendieck constant $K_G$ is precisely the
integrality gap of a natural SDP relaxation for the
\textsc{$K_{N,N}$-QuadraticProgramming} problem. The input to this
problem is a matrix $A = (a_{ij})$ and the objective is to maximize
the quadratic form $\sum_{ij} a_{ij} x_i y_j$ over $x_i, y_j \in
[-1,1]$.
In this work, we apply techniques from~\cite{prasad1} to the \BQP
problem.
%
Using some standard but non-trivial modifications, the reduction in
\cite{prasad1} yields the following hardness result: Assuming the
Unique Games Conjecture, it is NP-hard to approximate the \BQP
problem to any factor better than the Grothendieck constant $K_G$.
By adapting a ``bootstrapping'' argument used in a proof of
Grothendieck inequality \cite{linden}, we perform a tighter analysis
than \cite{prasad1}. Through this careful analysis, we obtain the
following new results:
\begin{itemize}
\item An approximation algorithm for \BQP that is guaranteed to
achieve an approximation ratio arbitrarily close to the
Grothendieck constant $K_G$ (optimal approximation ratio assuming
the Unique Games Conjecture).
\item We show that the Grothendieck constant $K_G$ can be computed
within an error $\eta$, in time depending only on $\eta$.
Specifically, for each $\eta$, we formulate an explicit finite
linear program, whose optimum is $\eta$-close to the Grothendieck
constant.
\end{itemize}
We also exhibit a simple family of operators on the Gaussian Hilbert
space that is guaranteed to contain tight examples for the
Grothendieck inequality. To achieve this, we give a direct
conversion from dictatorship tests to integrality gap instances
bypassing the use of a reduction from \textsc{UniqueGames} and the
Khot-Vishnoi \cite{khotvishnoi} integrality gap instances for
\textsc{UniqueGames}.
------------------------------------------
Mordecai J. Golin, Xiaoming Xu and Jiajin Yu. A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding
Abstract: Given a probability distribution over a set of n words, the Huffman-Coding problem is to find a minimal-cost prefix free code for transmitting/storing those words. Due to its nice structural properties, the basic Huffman-coding problem can be solved in O(n log n) time but, because they lack these properties, variations of the problem are more difficult. A small number of such variations have been shown to be solvable using a bottom-up (on the code tree) dynamic programming approach but the most generic solution method utilizes a top-down dynamic-programming one.
In this paper we show that the top-down approach can be sped up, permitting an order of magnitude improvement in the running time of many algorithms in the literature for such Huffman-coding variations as mixed radix, reserved length and one-ended coding. These speedups are immediate implications of a general structural property that permits batching together the calculation of many DP entries.
------------------------------------------
Ken-ichi Kawarabayashi, Erik Demaine and Mohammad Taghi Haijaghayi. Additive Approximation Algorithms for List-Coloring Minor-Closed Class of Graphs
Abstract: It is known that computing the list-chromatic number is much harder
than the chromatic number (assuming that the complexity classes $NP$
and $coNP$ are different.). In fact, the problem of deciding if a
given graph is $f$-list-colorable for a function $f : V \to
\{k-1,k\}$ for $k \geq 3$ is $\Pi_{2}^p$-complete.
In general, it is believed that approximating
list-coloring is hard for dense graphs.
In this paper, we are interested in sparse graphs.
More specifically, we deal with
minor-closed class of graphs,
i.e., graphs without $K_k$-minors.
We develop the seminal structure
theorem of Robertson and Seymour, and then give an additive
approximation for list-coloring within $k-2$ of the list-chromatic
number. This improves the $O(k)$-multiplicative-approximation algorithm by
Kawarabayashi and Mohar (STOC'06). Clearly our result gives rise
to an additive approximation algorithm for graph-coloring of minor-closed
class of graphs too. This result is comparable to the 2-approximation algorithm of
graph-coloring by Demaine, Hajiaghayi and Kawarabayashi (FOCS'05),
since our additive approximation algorithm
may give a better graph-coloring. This result also answers a question
posed by Robin Thomas (who conjectured that there is an additive
approximation algorithm for graph-coloring of minor-closed class of
graphs).
Our structure theorem is of independent interest in the sense that
it gives rise to a new insight on well-connected $H$-minor-free
graphs. In particular, this class of
graphs can be easily decomposed into two parts so that one part has
bounded tree-width and the other part is disjoint union of bounded
genus graphs. Moreover, we can control the number of edges between
two parts. Also, the proof method itself tells us how knowledge of a local structure
can be used to gain a global structure. This may be of interest,
since this gives a new insight how to decompose a graph, with help
of a local structure information.
------------------------------------------
Ken-ichi Kawarabayashi and Bruce Reed. A Nearly Linear Time Algorithm For The Half Integral Parity Disjoint Paths Packing Problem
Abstract: We consider the following problem, which is called the {\it half
integral parity disjoint paths packing problem}.
\medskip
{\bf Input}: A graph $G$, $k$ pair of vertices
$(s_1,t_1),(s_2,t_2),\dots, (s_k,t_k)$ in $G$ (which are sometimes
called {\it terminals}), and a parity $l_i$ for each $i$ with $1
\leq i \leq k$, where $l_i=0$ or $1$.
\medskip
{\bf Output} : Paths $P_1,\dots,P_k$ in $G$ such that $P_i$ joins
$s_i$ and $t_i$ for $i=1,2,\dots,k$ and parity of length of the path
$P_i$ is $l_i$, i.e, if $l_i=0$, then length of $P_i$ is even, and
if $l_i=1$, then length of $P_i$ is odd for $i=1,2,\dots,k$.
In addition, each vertex is on at most two of these paths.
\medskip
We present an $O(m \alpha(m,n) \log n)$ algorithm for fixed $k$,
where $n,m$ are the number of vertices and the number of edges,
respectively, and the function $\alpha(m,n)$ is the inverse of the
Ackermann function. This is the first polynomial time algorithm for
this problem, and generalizes polynomial time algorithms by
Kleinberg (STOC'98) and Kawarabayashi and Reed (SODA'08),
respectively, for the half integral disjoint paths packing problem,
i.e., without the parity requirement.
As with the Robertson-Seymour algorithm to solve the $k$ disjoint
paths problem, in each iteration, we would like to either use a huge
clique minor as a ''crossbar", or exploit the structure of graphs in
which we cannot find such a minor. Here, however, we must maintain
the parity of the paths and can only use an ''odd clique minor". We
must also describe the structure of those graphs in which we cannot
find such a minor and discuss how to exploit it.
In fact, we also have algorithms running in $O(m^{(1+\epsilon)})$
time for any $\epsilon > 0$ for this problem, if $k$ is up to
$o(\log{\log{\log n}})$ for general graphs, up to $o(\log{\log n})$
for planar graphs, and up to $o(\log{\log n/g})$ for graphs on the
surface, where $g$ is Euler genus. Furthermore, if $k$ is fixed,
then we have linear time algorithms for the planar case and for the
bounded genus case.
------------------------------------------
Michel Goemans, Nicholas J.A. Harvey, Satoru Iwata and Vahab Mirrokni. Approximating Submodular Functions Everywhere
Abstract: Submodular functions are a key concept in combinatorial optimization. Algorithms that involve submodular functions usually assume that they are given by a (value) oracle. Using only polynomially many queries to the oracle, one can minimize a submodular function or approximate its maximum within a constant.
In this paper, we consider the problem of approximating a monotone submodular function $f$ on a ground set of size $n$ {\it everywhere}, after only polynomially many oracle queries. Our main result is a deterministic algorithm that make polynomially many oracle queries to derive a function $\hat{f}$ of the form $\hat{f}(S)=\sqrt{\sum_{i\in S} c_i}$ such that, for {\it every} set $S$, $\hat{f}(S)$ approximates $f(S)$ within a factor $\alpha(n)$, where $\alpha(n)=\sqrt{n+1}$ for rank functions of matroids and $\alpha(n)=O(\sqrt{n} \log{n})$ for general monotone submodular functions. Our result is based on approximately finding a maximum volume inscribed ellipsoid in a symmetrized polymatroid, and the analysis involves various properties of submodular functions and polymatroids. We should point out that the general algorithm of Gr\"otschel, Lov\'asz and Schrijver for finding a large inscribed ellipsoid in a centrally symmetric convex body given by a separation oracle would only give us an approximation factor of $O(n)$.
Our algorithm is tight up to logarithmic factors. Indeed, we show that no algorithm can achieve a factor better than $\Omega(\sqrt{n} / \log(n))$, even for rank functions of a matroid.
------------------------------------------
Baharak Rastegari, Anne Condon and Kevin Leyton-Brown. Stepwise Randomized Combinatorial Auctions Achieve Revenue Monotonicity
Abstract: In combinatorial auctions that use VCG, a seller can sometimes increase revenue by dropping bidders. In our previous work (AAAI'07), we showed that such failures of ``revenue monotonicity'' occur under an extremely broad range of deterministic strategyproof combinatorial auction mechanisms, even when bidders have ``known single-minded'' valuations. In this work we consider the question of whether revenue monotonic, strategyproof mechanisms for such bidders can be found in the broader class of randomized mechanisms. We demonstrate that---surprisingly---such mechanisms do exist, show how they can be constructed, and consider algorithmic techniques for implementing them in polynomial time.
More formally, we characterize a class of randomized mechanisms defined for known single-minded bidders that are strategyproof and revenue monotonic, and furthermore satisfy some other desirable properties, namely participation, consumer sovereignty and maximality, representing the mechanism as a solution to a quadratically constrained linear program. We prove that the QCLP is always feasible (i.e., for all bidder valuations) and give its solution analytically. Furthermore, we give an algorithm for running such a mechanism in time quadratic in the number of bidders; this is interesting because constructing an instance of such mechanisms from our QCLP formulation in a naive way can be of exponential time.
Ilia Binder and Mark Braverman. The complexity of simulating Brownian Motion
Abstract: We analyze the complexity of the Walk on Spheres algorithm for simulating Brownian Motion in a domain Omega in R^d. The algorithm, which was first proposed in the 1950s, produces samples from the hitting probability distribution of the Brownian Motion process on boundary of Omega within an error of epsilon. The algorithm is used as a building block for solving a variety of differential equations, including the Dirichlet Problem.
The WoS algorithm simulates a BM starting at a point X_0=x in a given bounded domain Omega until it gets epsilon-close to the boundary of Omega. At every step, the algorithm measures the distance d_k from its current position X_k to the boundary of Omega and jumps a distance of d_k/2 in a uniformly random direction from X_k to obtain X_{k+1}. The algorithm terminates when it reaches X_n that is epsilon-close to the boundary of Omega.
It is not hard to see that the algorithm requires at least Omega(\log 1/epsilon) steps to converge. Only partial results with respect to upper bounds existed. In 1959 M. Motoo established an O(\log 1/epsilon) bound on the running time for convex domains. The results were later generalized for a wider, but still very restricted, class of planar and 3-dimensional domains by G.A. Mikhailov (1979). In our earlier work (2007), we established an upper bound of O(\log^2 1/epsilon) on the rate of convergence of WoS for arbitrary planar domains.
In this paper we introduce subharmonic energy functions to obtain very general upper bounds on the convergence of the algorithm. Special instances of the upper bounds yield the following results for bounded domains Omega:
* if Omega is a planar domain with connected exterior, the WoS converges in
O(\log 1/epsilon) steps;
* if Omega is a domain in R^3 with connected exterior, the WoS converges in O(\log^2 1/epsilon)$ steps;
* for d>2, if Omega is a domain in R^d, the WoS converges in O((1/epsilon)^{2-4/d}) steps;
* for d>3 if Omega is a domain in R^d with connected exterior, the WoS converges in O((1/epsilon)^{2-4/(d-1)}) steps;
* for any d if Omega is a domain in R^d bounded by a smooth surface, the WoS converges in O(\log 1/epsilon) steps.
We also demonstrate that the bounds are tight, i.e. we construct a domain from each class for which the upper bound is exact. Our results give the optimal upper bound of O(\log1/epsilon) in many cases for which only a bound polynomial in 1/epsilon was previously known.
Prosenjit Bose, Eric Chen, Meng He, Anil Maheshwari and Pat Morin. Succinct Geometric Indexes Supporting Point Location Queries
Abstract: We propose to design data structures called succinct geometric indexes of negligible space (more precisely, o(n) bits) that, by taking advantage of the n points in the data set permuted and stored elsewhere as a sequence, to support geometric queries in optimal time. Our first and main result is a succinct geometric index that can answer point location queries, a fundamental problem in computational geometry, on planar triangulations in O(lg n) time. We also design three variants of this index. The first supports point location using $\lg n + 2\sqrt{\lg n} + O(\lg^{1/4} n)$ point-line comparisons. The second supports point location in o(lg n) time when the coordinates are integers bounded by U. The last variant can answer point location queries in O(H+1) expected time, where H is the entropy of the query distribution. These results match the query efficiency of previous point location structures that use O(n) words or O(n lg n) bits, while saving drastic amounts of space. We generalize our succinct geometric index to planar subdivisions, and design indexes for other types of queries. Finally, we apply our techniques to design the first implicit data structures that support point location in $O(\lg^2 n)$ time.
------------------------------------------
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh and Sebastiano Vigna. Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses
Abstract: A minimal perfect hash function maps a set S of n keys into the
set {0,1,...,n-1} bijectively. Classical results state
that minimal perfect hashing is possible in constant time using
a structure occupying a number of bits close to the lower bound of
log e bits per element. Here we consider the problem of monotone
minimal perfect hashing, in which the bijection is required to preserve
the lexicographical ordering of the keys. A monotone minimal perfect
hash function can be seen as a very weak form of index that provides
just ranking on the set S (and answers randomly outside of S).
Our goal is to minimize the description size of the hash function: we show that, for a set
S of n elements out of a universe of u elements, O(n lg lg lg u) bits are
sufficient to hash monotonically in time O(lg lg u).
Alternatively, we can get space O(n lg lg u) bits with O(1) query
time. Both of these improve a straightforward construction with O(n
lg lg u) space and O(lg lg u) query time. As a consequence, it is possible
to search a sorted table with just one access to the table (using additional
O(n lg lg lg u) bits).
Our results are based
on a structure (of independent interest) that represents very
compactly a trie, but allows errors. As
a further application of the same structure, we show how to compute
the predecessor of any element of a sorted table, using O(1)
accesses in expectation and an index of O(n lg lg u) bits, improving
the trivial result of O(n lg u) bits. This implies an efficient index
for searching a blocked memory.
------------------------------------------
Alexandr Andoni, Piotr Indyk, Robi Krauthgamer and Huy Nguyen. Approximate Nearest Neighbors for Affine Subspaces Queries
Abstract: We consider the problem of approximate nearest neighbors in high
dimensions, when the queries are lines. In this problem, given n
points in R^d, we want to construct a data structure to support
efficiently the following queries: given a line L, report the point p
closest to L. This problem generalizes the more familiar nearest
neighbor problem. From a practical perspective, lines, and
low-dimensional flats in general, may model data under linear
variation, such as physical objects under different lighting.
For approximation 1+\epsilon, we achieve a query time of n^{0.5+t},
for arbitrary small $t>0$, with a polynomial space. To the best
of our knowledge, this is the first algorithm for this problem with
polynomial space and sub-linear query time.
------------------------------------------
Marcin Bienkowski, Marek Chrobak, Christoph Dürr, Mathilde Hurand, Artur Jez, ?ukasz Je? and Grzegorz Stachowiak. Collecting Weighted Items from a Dynamic Queue
Abstract: We consider the problem of collecting weighted items from a dynamic queue S. Before each step, some items at the front of S can be deleted and some other items can be added to S at any place. An item, once deleted, cannot be re-inserted -- in other words, it ``expires". We are allowed to collect one item from S per step. Each item can be collected only once. The objective is to maximize the total weight of the collected items.
We study the online version of the dynamic queue problem. It is quite easy to see that the greedy algorithm that always collects the maximum-value item is 2-competitive, and that no deterministic online algorithm can be better than 1.618-competitive. We improve both bounds: We give a 1.89-competitive algorithm for general dynamic queues and we show a lower bound of 1.632 on the competitive ratio. We also provide other upper and lower bounds for restricted versions of this problem.
The dynamic queue problem is a generalization of the well-studied buffer management problem, and it is an abstraction of the buffer management problem for network links with intermittent access.
------------------------------------------
Boaz Barak, Moritz Hardt and Satyen Kale. The Uniform Hardcore Lemma via Approximate Bregman Projections
Abstract: We give a simple, more efficient and uniform proof of the hard-core lemma, a fundamental result in complexity theory with applications in machine learning and cryptography. Our result follows from the connection between boosting algorithms and hard-core set constructions discovered by Klivans and Servedio [KS03]. Informally stated, our result is the following: suppose we fix a family of boolean functions. Assume there is an efficient algorithm which for every input length and every smooth distribution (i.e. one that doesn't assign too much weight to any single input) over the inputs produces a circuit such that the circuit computes the boolean function noticeably better than random. Then, there is an efficient algorithm which for every input length produces a circuit that computes the function correctly on almost all inputs.
Our algorithm significantly simplifies previous proofs of the uniform and the non-uniform hard-core lemma, while matching or improving the previously best known parameters. The algorithm uses a generalized multiplicative update rule combined with a natural notion of approximate Bregman projection. Bregman projections are widely used in convex optimization and machine learning. We present an algorithm which efficiently approximates the Bregman projection onto the set of high density measures when the Kullback-Leibler divergence is used as a distance function. Our algorithm has a logarithmic runtime over any domain provided that we can efficiently sample from this domain. High density measures correspond to smooth distributions which arise naturally, for instance, in the context of online learning. Hence, our technique may be of independent interest.
------------------------------------------
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova and David Woodruff. Transitive-Closure Spanners
Abstract: We define the notion of a transitive-closure spanner of a directed graph. Given a directed graph G = (V;E) and an integer k>0, a k-transitive-closure-spanner (k-TC-spanner) of G is a directed graph H = (V;E') that has (1) the same transitive-closure as G and (2) diameter at most k. These spanners were studied implicitly in access control, property testing, and data structures, and properties of these spanners have been rediscovered over the span of 20 years. We bring these areas under the unifying framework of TC-spanners. We abstract the common task implicitly tackled in these diverse applications as the problem of constructing sparse TC-spanners.
We study the approximability of the size of the sparsest k-TC-spanner for a given digraph. Our technical contributions fall into three categories: algorithms for general digraphs, inapproximability results, and structural bounds for a specific graph family which imply an efficient algorithm with a good approximation ratio for that family.
[Algorithms.] We present two efficient deterministic algorithms that find k-TC-spanners of size approximating the optimum. The first algorithm gives an O-tilde(n^{1-1/k})-approximation for k > 2. Our method, based on a combination of convex programming and sampling, yields the first sublinear approximation ratios for (1) DIRECTED k-SPANNER, a well-studied generalization of k-TC-SPANNER, and (2) its variants CLIENT/SERVER DIRECTED k-SPANNER, and the k-DIAMETER SPANNING SUBGRAPH. This resolves the main open question of Elkin and Peleg (IPCO, 2001). The second algorithm, specific to the k-TC-spanner problem, gives an O-tilde(n/(k^2))-approximation. It shows that for k = Omega(\sqrt{n}), our problem has a provably better approximation ratio than DIRECTED k-SPANNER and its variants. This algorithm also resolves an open question of Hesse (SODA, 2003).
[Inapproximability.] Our main technical contribution is a pair of strong inapproximability results. We resolve the approximability of 2-TC-spanners, showing that it is Theta(log n) unless P=NP. For constant k>2, we prove that the size of the sparsest k-TC-spanner is hard to approximate within 2^{\log^{1-\epsilon} n}, for any \epsilon > 0, under standard complexity assumptions. Our hardness result helps explain the difficulty in designing general efficient solutions for the applications above, and it cannot be improved without resolving a long-standing open question in complexity theory. It uses an involved application of generalized butterfly and broom graphs, as well as noise-resilient transformations of hard problems, which may be of independent interest.
[Structural bounds.] Finally, we study the size of the sparsest TC-spanner for H-minor-free digraphs, which include planar, bounded genus, and bounded tree-width graphs, explicitly investigated in applications above. We show that every H-minor-free digraph has an efficiently constructable k-TC-spanner of size O-tilde(n), which implies an O-tilde(1)-approximation algorithm for this family. Furthermore, using our insight that 2-TC-spanners yield property testers, we obtain a monotonicity tester with O(log^2 n /\epsilon)) queries for any poset whose transitive reduction is an H-minor free digraph. This improves and generalizes the previous Theta(\sqrt{n} \log n/\epsilon)-query tester of Fischer et al (STOC, 2002).
------------------------------------------
Constantinos Daskalakis, Grant Schoenebeck, Gregory Valiant and Paul Valiant. On the Complexity of Nash Equilibria of Action-Graph Games
Abstract: In light of much recent interest in finding a model of multi-player multi-action games that allows for efficient computation of Nash equilibria yet remains as expressive as possible, we investigate the computational complexity of Nash equilibria in the recently proposed model of Action-Graph Games (AGGs). AGGs, introduced by Bhat and Leyton-Brown, are succinct representations of games that encapsulate both local dependencies as in graphical games, and partial indifference to other agents' identities as in anonymous games, which occur in many natural settings such as financial markets. This is achieved by specifying a graph on the set of actions, so that the payoff of an agent for selecting a strategy depends only on the number of agents playing each of the neighboring strategies in the action graph. We present a simple Polynomial Time Approximation Scheme for computing mixed Nash equilibria of AGGs with constant treewidth and a constant number of agent types (but an arbitrary number of strategies). However, the main results of this paper are negative, showing that when either of these conditions is relaxed the problem becomes intractable. In particular, we show that even if the action graph is a tree but the number of agent-types is unconstrained, it is NP--complete to decide the existence of a pure-strategy Nash equilibrium and PPAD--complete to compute a mixed Nash equilibrium (even an approximate one). Analogously, for AGGs where all agents are of a single type (symmetric AGGs), if the treewidth is unconstrained then deciding the existence of a pure-strategy Nash equilibrium is NP--complete and computing a mixed Nash is PPAD--complete. These hardness results suggest that, in some sense, our PTAS is as strong a positive result as one can expect. In the broader context of trying to pin down the boundary where the equilibria of multi-player games can be computed efficiently, these results complement recent hardness results for graphical games and algorithmic results for anonymous games.
------------------------------------------
Alexandr Andoni, Piotr Indyk and Robi Krauthgamer. Overcoming the L_1 Non-Embeddability Barrier: Algorithms for Product Metrics
Abstract: A common approach for solving computational problems over a difficult
metric space is to embed the ``hard'' metric into $L_1$, which admits
efficient algorithms and is thus considered an ``easy'' metric. This
approach has proved successful or partially successful for important
spaces such as the edit distance, but it also has inherent
limitations: it is provably impossible to go below certain
approximation for some metrics.
We propose a new approach, of embedding the difficult space into
richer host spaces, namely iterated products of standard spaces like
$L_1$ and $L_\infty$. We show that this class is /rich/
since it contains useful metric spaces with only a constant
distortion, and, at the same time, it is /tractable/ and admits
efficient algorithms. Using this approach, we obtain for example the
first nearest neighbor data structure with $O(\log \log d)$
approximation for edit distance in non-repetitive strings (the Ulam
metric). This approximation is exponentially better than the {\em
lower bound} for embedding into $L_1$. Furthermore, we give
constant factor approximation for two other computational problems.
Along the way, we answer positively a question left open in
[Ajtai-Jayram-Kumar-Sivakumar, STOC'02]. One of
our algorithms has already found applications for smoothed edit
distance over 0-1 strings [Andoni-Krauthgamer, ICALP'08].
------------------------------------------
Parikshit Gopalan and Jaikumar Radhakrishnan. Finding repeats in a data-stream
Abstract: Given a string of length $n$ over the alphabet $[m]$ where $n > m$, we
consider the problem of finding a repeated element in a single
pass. We give a randomized algorithm for this problem that uses
$O((\log m)^4)$ space.
In contrast, we show that any deterministic single-pass algorithm for
finding a repeated element needs space at least $m$, even if $n$ is
arbitrarily large compared to $m$. However, we show that when we have
access to a clock that records the number of input symbols read so
far, the space required drops to $\log m + O(1)$ if $n \geq 2^m$;
thus for this problem non-uniformity adds considerable power to
deterministic algorithms. For non-uniform deterministic algorithms we
show that finding a repeated element in a stream of length $n$ requires
space at least $m-\log n$; we show that this lower bound is close
to optimal for a range of values of $n$.
------------------------------------------
James Aspnes and Keren Censor. Approximate Shared-Memory Counting Despite a Strong Adversary
Abstract: A new randomized asynchronous shared-memory data structure is given for implementing an approximate counter that can be incremented up to $n$ times. For any fixed $\epsilon$, the counter achieves a relative error of $\delta$ with high probability,
at the cost of $O(((1/\delta) \log n)^{O(1/\epsilon)})$ register operations per increment and $O(n^{4/5+\epsilon}((1/\delta) \log n)^{O(1/\epsilon)})$ register operations per read. The counter combines randomized sampling for estimating large values with an expander for estimating small values. This is the first sublinear solution to this problem that works despite a strong adversary scheduler that can observe internal states of processes.
An application of the improved counter is an improved protocol for solving randomized shared-memory consensus, which reduces the best previously known individual work complexity from $O(n \log n)$ to an optimal $O(n)$, resolving one of the last remaining open problems concerning consensus in this model.
------------------------------------------
Ittai Abraham, Yair Bartal and Ofer Neiman. On Low Dimensional Local Embeddings
Abstract: We study the problem of embedding metric spaces into low
dimensional $L_p$ spaces while faithfully preserving distances
from each point to its $k$ nearest neighbors. We show that any
metric space can be embedded into $L^{O(e^p \log^2 k)}_p$ with
$k$-local distortion of $O((\log k)/p)$. We also show that any
ultrametric can be embedded into $L^{O(\log
k)/\epsilon^3}_p$ with $k$-local distortion $1+\epsilon$.
Our embedding results have immediate applications to local
Distance Oracles. We show how to preprocess a graph in polynomial
time to obtain a data structure of $O(n k^{1/t} \log^2 k)$ bits,
such that distance queries from any node to its $k$ nearest
neighbors can be answered with stretch $t$.
------------------------------------------
Michael Bender, Jeremy Fineman and Seth Gilbert. Online Topological Ordering
Abstract: Let G=(V,E) be a directed acyclic graph (dag) with n = |V| and m=|E|. We say that a bijection P from V to the integers 1,2,...,n is a "topological ordering" if for every edge (u,v) in E, we have P(u) < P(v). In this paper, we consider the problem of maintaining a topological ordering subject to dynamic changes to the underlying graph. That is, we begin with an empty graph G = (V, {}) consisting of n nodes. The adversary adds m edges to the graph G, one edge at a time. Thoughout this process, we maintain an online topological ordering of the graph G. In this paper, we present a new algorithm for online topological ordering that has total cost O(n^2 log^2 n) for all edge additions. At the heart of our algorithm is a new approach for maintaining a topological ordering that differs from previous algorithms. Instead of attempting to maintain the nodes in an ordered list, we assign each node a label that preserves the appropriate ordering, and yet can be updated efficiently as edges are inserted. When the graph is dense, our algorithm is more efficient than all existing algorithms. By way of contrast, the best known prior algorithms achieve only O(min(m^{1.5}, n^{2.5})) cost.
------------------------------------------
William Johnson and Assaf Naor. The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
Abstract: Let $X$ be a normed spaces that satisfies the Johnson-Lindenstrauss
lemma, i.e. for any integer $n$ and any $x_1,\ldots,x_n\in X$ there
exists a linear mapping $L:X\to F$, where $F\subseteq X$ is a linear
subspace of dimension $O(\log n)$, such that $\|x_i-x_j\|\le
\|L(x_i)-L(x_j)\|\le O(1)\cdot\|x_i-x_j\|$ for all $i,j\in
\{1,\ldots, n\}$. We show that this implies that $X$ is almost
Euclidean in the following sense: Any $n$-dimensional subspace of
$X$ embeds into Hilbert space with distortion $2^{2^{O(\log_*n)}}$.
On the other hand, we show that there exists a normed space $Y$
which satisfies the Johnson-Lindenstrauss lemma, but for every $n$
there exists an $n$-dimensional subspace $E_n\subseteq Y$ whose
Euclidean distortion is at least $2^{\Omega(\alpha(n))}$, where
$\alpha$ is the inverse of the Ackermann function.
------------------------------------------
Klaus Jansen. Parameterized approximation scheme for the multiple knapsack problem
Abstract: The multiple knapsack problem (MKP) is a well-known generalization
of the classical knapsack problem. We are given a set $A$ of $n$
items and set $B$ of $m$ bins (knapsacks) such that each item $a
\in A$ has a size $size(a)$ and a profit value $profit(a)$, and
each bin $b \in B$ has a capacity $c(b)$. The goal is to find a
subset $U \subset A$ of maximum total profit such that $U$ can be
packed into $B$ without exceeding the capacities.
The decision version of MKP is strongly NP-complete, since it is a
generalization of the classical knapsack and bin packing problem.
Furthermore, MKP does not admit an FPTAS even if the number $m$ of
bins is two. Kellerer gave a PTAS for MKP with identical
capacities and Chekuri and Khanna presented a PTAS for MKP with
general capacities with running time $n^{O(\log(1/\epsilon) /
\epsilon^8)}$. In this paper we propose an EPTAS with
parameterized running time $2^{O(\log(1/\epsilon)/\epsilon^5)}
\cdot poly(n) + O(m)$ for MKP.
------------------------------------------
Markus Chimani, Carsten Gutwenger, Petra Mutzel and Christian Wolf. Inserting a Vertex into a Planar Graph
Abstract: We consider the problem of computing a crossing minimum drawing of a given
planar graph $G=(V,E)$ augmented by a star, i.e., an additional vertex $v$
together with its incident edges $E_v=\{(v,u) \mid u \in V\}$, in which all
crossings involve $E_v$. Alternatively, the problem can be stated as finding a
planar embedding of $G$, in which the given star can be inserted requiring
the minimum number of crossings. This is a generalization of the crossing
minimum edge insertion problem [12], and can help to find improved
approximations for the crossing minimization problem. Indeed, in practice,
the algorithm for the crossing minimum edge insertion problem turned out to be
the key for obtaining the currently strongest approximate solutions for the
crossing number of general graphs. The generalization considered here can lead
to even better solutions for the crossing minimization problem. Furthermore, it
offers new insight into the crossing number problem for almost-planar and apex
graphs.
It has been an open problem whether the star insertion problem is
polynomially solvable. We give an affirmative answer by describing the first
efficient algorithm for this problem. This algorithm uses the SPQR-tree
data structure to handle the exponential number of possible embeddings, in
conjunction with dynamic programming schemes for which we introduce
\emph{partitioning cost} subproblems.
------------------------------------------
Spyros Angelopoulos and Pascal Schweitzer. Paging and List Update under Bijective Analysis
Abstract: It has long been known that for the paging problem in its standard form, competitive analysis cannot adequately distinguish algorithms based on their performance: there exists a vast class of algorithms which achieve the same competitive ratio, ranging from extremely naive and inefficient strategies (such as Flush-When-Full), to strategies of excellent performance in practice (such as Least-Recently-Used and some of its variants). A similar situation arises in the list update problem: in particular, under the cost formulation studied by Martinez and Roura [TCS 2000] and Munro [ESA 2000] every list update algorithm has, asymptotically, the same competitive ratio. Several refinements of competitive analysis, as well as alternative performance measures have been introduced in the literature, with varying degrees of success in narrowing this disconnect between theoretical analysis and empirical evaluation.
In this paper we study these two fundamental online problems under the framework
of bijective analysis [Angelopoulos, Dorrigiv and Lopez-Ortiz, SODA 2007 and LATIN 2008]. This is an intuitive technique which is based on pairwise comparison of the costs incurred by two algorithms on sets of request sequences of the same size. Coupled with a well-established model of locality of reference due to Albers, Favrholdt and Giel [JCSS 2005], we show that Least-Recently-Used and Move-to-Front are the unique optimal algorithms for paging and list update, respectively. Prior to this work, only measures based on average-cost analysis have separated LRU and MTF from all other algorithms. Given that bijective analysis is a fairly stringent measure (and also subsumes average-cost analysis), we prove that in a strong sense LRU and MTF stand out as the best algorithms.
------------------------------------------
Adrian Dumitrescu, Csaba Toth and G Xu. On stars and Steiner stars. II
Abstract: A {\em Steiner star} for a set $P$ of $n$ points in $\RR^d$ connects an
arbitrary center point to all points of $P$, while a
{\em star} connects a point $p\in P$ to the remaining $n-1$ points of
$P$. All connections are realized by straight line segments.
Fekete and Meijer showed that the minimum star is at most $\sqrt{2}$ times
longer than the minimum Steiner star for any finite point configuration in
$\RR^d$. The maximum ratio between them, over all finite point configurations
in $\RR^d$, is called the {\em star Steiner ratio} in $\RR^d$.
It is conjectured that this ratio is $4/\pi = 1.2732\ldots$ in the plane and
$4/3=1.3333\ldots$ in three dimensions. Here we give upper bounds of $1.3631$
in the plane, and $1.3833$ in 3-space, thereby substantially improving recent
upper bounds of $1.3999$, and $\sqrt{2}-10^{-4}$, respectively.
Our results also imply improved bounds on the maximum ratios between the
minimum star and the maximum matching in two and three dimensions.
Our method exploits the connection with the classical problem of
estimating the maximum sum of pairwise distances among $n$ points on
the unit sphere, first studied by L\'aszl\'o Fejes T\'oth. It is quite general
and yields the first non-trivial estimates below $\sqrt2$ on the star Steiner
ratios in arbitrary dimensions. We show, however, that the star Steiner ratio
in $\RR^d$ tends to $\sqrt{2}$, the upper bound given by Fekete and Meijer,
as $d$ goes to infinity. Our estimates on the star Steiner ratios are
therefore much closer to the conjectured values in higher dimensions!
%The quality of our estimates on the star Steiner
%ratios is therefore much better for higher dimensions!
As it turns out, our estimates as well as the conjectured values of the
Steiner ratios (in the limit, for $n$ going to infinity) are related to the
classical infinite Wallis product:
$ \frac{\pi}{2}= \prod_{n=1}^{\infty} \left(\frac{4n^2}{4n^2-1}\right)
= \frac21 \cdot \frac23 \cdot \frac43 \cdot \frac45
\cdot \frac65 \cdot \frac67 \cdot \frac87 \cdot \frac89 \cdots $.
------------------------------------------
Benjamin Aminof, Orna Kupferman and Robby Lampert. Reasoning about Online Algorithms with Weighted Automata
Abstract: We describe an automata-theoretic approach for the competitive
analysis of {\em online algorithms}. Our approach is based on {\em
weighted automata}, which assign to each input word a cost in
$\R^{\geq 0}$. By relating the ``unbounded look ahead'' of optimal
offline algorithms with nondeterminism, and relating the ``no look
ahead'' of online algorithms with determinism, we are able to solve
problems about the competitive ratio of online algorithms, and the
memory they require, by reducing them to questions about {\em
determinization\/} and {\em approximated determinization} of
weighted automata.
------------------------------------------
Amin Coja-Oghlan, Uriel Feige, Alan Frieze, Michael Krivelevich and Dan Vilenchik. On smoothed k-CNF formulas and the Walksat algorithm
Abstract: In this paper we study the model of $\epsilon$-smoothed $k$-CNF
formulas. Starting from an arbitrary instance $F$ with $n$ variables
and $m = dn$ clauses, apply the $\epsilon$-smoothing operation of
flipping the polarity of every literal in every clause independently
at random with probability $\epsilon$. Keeping $\eps$ and $k$ fixed, and
letting the density $d = m/n$ grow, it is rather easy to see that
when $d = c\epsilon^{-k}$ (where $c$ is some sufficiently large constant
that depends only on $k$), every $F$ will whp become unsatisfiable
after smoothing.
We show that a lower density that behaves roughly like $\epsilon^{-k+1}$
suffices for this purpose. We also show that our bound on $d$ is
nearly best possible in the sense that there are $k$-CNF formulas
$F$ of slightly lower density that whp remain satisfiable after
smoothing. Moreover, the well known Walksat algorithm will whp
find a satisfying assignments in these smoothed formulas (whenever
$\epsilon\geq 1/k$).
Our proof (when setting $\epsilon = 1/2$) gives a new lower bound of
$\Omega(2^k/k^2)$ on the density in which for most $k$-CNF formulas
the Walksat algorithm whp terminates successfully in polynomial
time. We are not aware of any previous rigorous analysis that shows
that Walksat is successful at densities that are increasing as a
function of $k$.
------------------------------------------
Elad Hazan and Robi Krauthgamer. How hard is it to approximate the best Nash equilibrium?
Abstract: The quest for a PTAS for Nash equilibrium in a two-player game,
which emerged as a major open question in Algorithmic Game Theory,
seeks to circumvent the PPAD-completeness of an (exact) Nash equilibrium
but finding an approximate equilibrium.
A related problem of special interest is that of finding an equilibrium maximizing
a certain objective, such as the social welfare.
This optimization problem was shown to be NP-hard
by Gilboa and Zemel [Games and Economic Behavior 1989].
However, this NP-hardness is unlikely to extend to finding an approximate equilibrium, since the latter admits a quasi-polynomial time algorithm,
as proved by Lipton, Markakis and Mehta [EC, 2003].
We show that this optimization problem, namely, finding in a two-player game
an approximate equilibrium achieving large social welfare is
unlikely to have a polynomial time algorithm.
One interpretation of our results is that the quest for a PTAS for Nash equilibrium
should NOT extend to a PTAS for finding the best Nash equilibrium,
which stands in contrast to certain algorithmic techniques used so far
(e.g. sampling and enumeration).
Technically, our result is a reduction from a notoriously difficult problem in modern combinatorics, of finding a planted (but hidden) clique in a random graph G(n,1/2). Our reduction starts from an instance with planted clique size k=O(log n). For comparison, the currently known algorithms
due to Alon, Krivelevich and Sudakov [RSA, 1998],
and Krauthgamer and Feige [RSA, 2000],
are only effective for a much larger clique size $k=\Omega(\sqrt n)$.
------------------------------------------
Ashish Goel, Sanjeev Khanna and Brad Null. The Ratio Index for Budgeted Learning, with Applications
Abstract: In the budgeted learning problem, we are allowed to
experiment on a set of alternatives (given a fixed
experimentation budget) with the goal of picking a single
alternative with the largest possible expected payoff.
Approximation algorithms for this problem were developed
by Guha and Munagala by rounding a linear program that
couples the various alternatives together. In this paper
we present an index for this problem, which we call the
ratio index, which also guarantees a constant factor
approximation. Index based policies have the advantage
that a single number (i.e. the index) can be computed for
each alternative irrespective of all other alternatives,
and the alternative with the highest index is experimented
upon. This is analogous to the famous Gittins index for
the discounted multi-armed bandit problem.
The ratio index has several interesting structural
properties. First, we show that it can be computed in
strongly polynomial time; the techniques we develop may be
useful for deriving strongly polynomial algorithms for
other Markov Decision Problems. Second, we show that with
the appropriate discount factor, the Gittins index
and our ratio index are constant factor approximations of
each other, and hence the Gittins index also gives a
constant factor approximation to the budgeted learning
problem. Finally, we show that the ratio index can be used
to create an index based policy that achieves an
$O(1)$-approximation for the finite
horizon version of the multi-armed bandit problem.
Moreover, the policy does not
require any knowledge of the horizon (whereas we compare
its performance against an optimal strategy that is aware of
the horizon). This yields the following
surprising result: there is an index based policy
that achieves an $O(1)$-approximation
for the multi-armed bandit problem, oblivious to the
underlying discount factor.
------------------------------------------
Serge Gaspers and Gregory Sorkin. A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between
Abstract: In this paper we consider formulas consisting of "simple clauses", namely conjunctions and disjunctions of pairs of variables, and general integer-weighted 2-variable clauses, which can be any functions of pairs of variables. We present an exact (exponential-time) algorithm which is the fastest polynomial-space algorithm for Max 2-Sat, tied for fastest for Max 2-CSP, and fastest for everything in between.
That is, parametrizing an instance by the fraction p of non-simple clauses, we give a single algorithm which is the fastest known for p=0 (which includes the well-studied Max 2-Sat problem but also instances with arbitrary mixtures of AND and OR clauses); the only efficient algorithm for mixtures of AND, OR, and general integer-weighted clauses; and tied for fastest for general Max 2-CSP (p=1). Since a pure 2-Sat input instance may be transformed to a general instance in the course of being solved, the algorithm's efficiency and generality go hand in hand.
Our novel analysis results in a family of running-time bounds, each optimized for a particular value of p, but valid for all p. The algorithm uses some new reductions introduced here, as well as recent reductions such as "clause-learning" and "2-reductions" adapted to our setting's mixture of simple and general clauses. Each reduction imposes constraints on various parameters, the running-time bound is an "objective function" of these parameters and p, and the optimal running-time bound is obtained by solving a convex nonlinear program, which can be done efficiently and with a certificate of optimality.
------------------------------------------
Greg Aloupis, Jean Cardinal, Sebastien Collette, Stefan Langerman, David Orden and Pedro Ramos. Decomposition of Multiple Coverings into More Parts
Abstract: We prove that for every centrally symmetric convex polygon Q, there exists a constant alpha such that any alpha*k-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and Toth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery lifetime.
------------------------------------------
Edith Elkind and Dmitrii Pasechnik. Computing the nucleolus of weighted voting games
Abstract: Weighted voting games (WVG) are coalitional games in which an agent's contribution to a coalition is given by his {\it weight}, and a coalition wins if its total weight meets or exceeds a given quota. These games model decision-making in political bodies as well as collaboration and surplus division in multiagent domains. The computational complexity of various solution concepts for weighted voting games received a lot of attention in recent years. In particular, Elkind et al.(2007) studied the complexity of stability-related solution concepts in WVGs, namely, of the core, the least core, and the nucleolus. While they have completely characterized the algorithmic complexity of the core and the least core, for the nucleolus they have only provided an NP-hardness result.
In this paper, we solve an open problem posed by Elkind et al. by showing
that the nucleolus of WVGs, and, more generally, $k$-vector weighted voting games with fixed $k$, can be computed in pseudopolynomial time, i.e., there exists an algorithm that correctly computes the nucleolus and runs in time polynomial in the number of players $n$ and the maximum weight $W$. In doing so, we propose a general framework for computing the nucleolus, which may be applicable to a wider of class of games.
------------------------------------------
Konstantinos Panagiotou and Angelika Steger. Maximum Biconnected Subgraphs of Random Planar Graphs
Abstract: Let $\CP_n$ be the class of simple labeled planar graphs with $n$ vertices, and denote by $\SP_n$ a graph drawn uniformly at random from this set. Basic properties of $\SP_n$ were first investigated by Denise, Vasconcellos, and Welsh [dvw96]. Since then, the random planar graph has attracted considerable attention, and is nowadays an important and challenging model for evaluating methods that are developed to study properties of random graphs from classes with structural side constraints.
In this paper we study the structure of $\SP_n$. More precisely, let $b(\ell;\, \SP_n)$ be the number of blocks (i.e.\ maximal biconnected subgraphs) of $\SP_n$ that contain exactly $\ell$ vertices, and let~$lb(\SP_n)$ be the number of vertices in the largest block of $\SP_n$. We show that with high probability $\SP_n$ contains a \emph{giant} block that includes up to lower order terms $cn$ vertices, where $c \approx 0.959$ is an analytically given constant. Moreover, we show that the \emph{second} largest block contains only $n^{2/3}\text{polylog}(n)$ vertices, and prove sharp concentration results for $b(\ell;\, \SP_n)$, for all~$2\le\ell\le n^{2/3}$.
In fact, we obtain this result as a consequence of a much more general result that we prove in this paper. Let $\CG$ be a class of labeled connected graphs, and let $\SG_n$ be a graph drawn uniformly at random from graphs in $\CG$ that contain exactly $n$ vertices. Under certain assumptions on~$\CG$, and depending on the behavior of the singularity of the generating function enumerating the elements of $\CG$, $\SG_n$ belongs with high probability to one of the following three categories, which differ vastly in complexity. $\SG_n$ either
\begin{itemize}
\item[(1)] behaves like a random planar graph, i.e.\ $lb(\SG_n) \sim cn$, for some analytically given $c = c(\CG)$, and the second largest block is of order $n^{\alpha}$, where $1 > \alpha = \alpha(\CG)$, or
\item[(2)] $lb(\SG_n) = \mathcal{O}(\log n)$, i.e., all blocks contain at most logarithmically many vertices, or
\item[(3)] $lb(\SG_n) = \Theta(n^{\alpha})$, for some $\alpha = \alpha(\CG)$.
\end{itemize}
Planar graphs belong to category (1). In contrast to that, outerplanar and series-parallel graphs belong to category (2), and differ thus substantially from planar graphs.
Our proofs exploit recent progress in the development of Boltzmann samplers by Duchon, Flajolet, Louchard and Schaeffer [dfls04] and basic tools from modern probability theory.
------------------------------------------
Ken-ichi Kawarabayashi and Bojan Mohar. List-Color-Critical Graphs on a Fixed Surface
Abstract: We prove the following conjecture posed by Thomassen in 1994:
\medskip
There are only finitely many list-color-critical graphs with all lists of
cardinality 5 on a fixed surface.
\medskip
This generalizes the well-known result of Thomassen
on the usual graph coloring case.
We use this theorem to address the complexity status of the
following question on list-coloring graphs on a fixed surface $S$.
\medskip
{\bf Input}: A graph $G$ in the surface $S$.
{\bf Output}: Is $G$ $k$-list-colorable? If not, provide a certificate (a
list-color-critical subgraph) for this. If yes, given any lists of cardinality $k$,
then give a $k$-list-coloring.
\medskip
In fact, together with our recent algorithmic result, we give a linear time
algorithm for the problem when $k \geq 5$. The cases $k=3,4$ are known to be
NP-hard, and the cases $k=1,2$ are easy. This generalizes the
well-known linear time algorithms for planar graphs by Nishizeki and Chiba (for 5-coloring),
and Thomassen (for 5-list-coloring).
We also give a polynomial time algorithm to address the following algorithmic question:
\medskip
{\bf Input}: A graph $G$ in the surface $S$, and lists of cardinality $k \geq 5$.
{\bf Output}: Does $G$ have a valid coloring from the lists? If not, provide a certificate for this. If yes, then give a $k$-list-coloring.
\medskip
This is different from the first algorithmic one in the sense that
some list-color-critical graph $H$ may have a valid coloring from some lists of $H$.
Therefore, the second one is strictly stronger than the first one.
We give a polynomial time algorithm for this problem too.
We also use our main theorem to prove the following conjecture, made
recently by Thomassen:
\medskip
For every fixed surface $S$, there exists a positive constant $c$
such that every $5$-list-colorable graph with $n$ vertices embedded on $S$,
and any lists of cardinality 5, has at least $c \times 2^{n}$ distinct 5-list-colorings.
\medskip
Thomassen himself proved that this conjecture holds for the usual 5-coloring.
In addition to these results, we also made partial progress toward
a conjecture of Albertson concerning coloring extension.
------------------------------------------
Ariel Kulik, Hadas Shachnai and Tami Tamir. Maximizing Submodular Set Functions Subject to Multiple Linear Constraints
Abstract: The concept of submodularity plays a vital role in combinatorial
optimization. In particular, many important optimization problems
can be cast as submodular maximization
problems, including maximum coverage, maximum
facility location and Max Cut in directed/undirected graphs.
In this paper we
present the first known approximation algorithms for the problem of
maximizing a non-decreasing submodular set function subject to
multiple linear constraints. Given an oracle for a non-decreasing
submodular set function $f$ over a universe $U$, where each element
$e \in U$ is associated with a $d$-dimensional cost vector and a
$d$-dimensional budget vector $\bL$, for some $d \geq 1$, we seek a
subset of elements $\mathbf{S} \subseteq U$ whose total cost is at
most $\bL$, such that $f(\mathbf{S})$ is maximized.
We develop a framework
for maximizing submodular functions subject to $d$ linear constraints
that yields a $(1-\eps)(1-e^{-1})$-approximation to the optimum
for any $\eps > 0$, where $d >1$ is some constant.
Our study is motivated from a variant of the classical maximum coverage
problem that we call {\em maximum coverage with multiple packing
constraints}.
We use our framework to obtain the same approximation ratio for this problem.
To the best of our knowledge, this is the first time the theoretical bound of
$1-e^{-1}$ is (almost) matched for both of these problems.
------------------------------------------
Marcel R. Ackermann and Johannes Blömer. Coresets and Approximate Clustering for Bregman Divergences
Abstract: We study the generalized $k$-median problem with respect to a Bregman divergence $D_\phi$. Given a finite set $P \subset R^d$ of size $n$, our goal is to find a set $C$ of size $k$ such that the sum of errors $cost(P,C) = \sum_{p \in P} \min_{c \in C} D_\phi(p,c)$ is minimized. The Bregman $k$-median problem plays an important role in many applications, e.g. information theory, statistics, text classification, and speech processing. We give the first coreset construction for this problem for a large subclass of Bregman divergences, including important dissimilarity measures such as the Kullback-Leibler divergence and the Itakura-Saito divergence. Using these coresets, we give a $(1+\epsilon)$-approximation algorithm for the Bregman $k$-median problem with running time $O( dkn + d^2 2^{(k/\epsilon)^{\Theta(1)}} \log^{k+2} n )$. This result improves over the previousely fastest known $(1+\epsilon)$-approximation algorithm from [ABS08]. Unlike the analysis of most coreset constructions our analysis does not rely on the construction of $\epsilon$-nets. Instead, we prove our results by purely combinatorial means.
References
[ABS08] M. R. Ackermann, J. Bl\"omer, and C. Sohler. Clustering for metric and non-metric distance measures. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '08), pages 799--808, 2008.
------------------------------------------
Benjamin Moseley and Chandra Chekuri. Online Scheduling to Minimize the Maximum Delay Factor
Abstract: In this paper two forms of information dissemination or scheduling
are addressed. First is the standard model (unicast) where requests
(or jobs) are independent. The other is the broadcast model where
broadcasting a page can satisfy multiple outstanding requests for
that page. We consider online scheduling of requests
when they have deadlines. Unlike previous models which mainly
consider the objective of maximizing throughput while respecting
deadlines, here we focus on scheduling all jobs with the goal of
minimizing the maximum {\em delay factor}. The delay factor of a
schedule, $\alpha$, is defined to be the minimum $\alpha \ge 1$ such
that each job $i$ is completed by time $a_i + \alpha(d_i - a_i)$
where $d_i$ is the deadline of request $i$ and $a_i$ is the arrival
time of request $i$. Delay factor generalizes the previously defined
measure of maximum stretch which is based only the processing times
of requests.
We prove strong lower bounds on the achievable competitive ratios
for delay factor scheduling even with unit-time requests. Motivated
by this, we consider resource augmentation analysis and prove the
following positive results. For the unicast model we give
algorithms that are $(1 + \eps)$-speed $O({1 \over
\eps})$-competitive in both the single machine and multiple
machine settings. In the broadcast model we give an algorithm for
similar-sized pages that is $(1+ \eps)$-speed $O({1 \over
\eps^2})$-competitive. Online algorithms have been difficult to
design for the broadcast setting and ours is the first to give a
$(1+\eps)$-speed analysis for a natural measure of performance.
------------------------------------------
Maria-Florina Balcan, Avrim Blum and Anupam Gupta. Approximate Clustering without the Approximation
Abstract: Approximation algorithms for clustering points in metric spaces is a
flourishing area of research, with much research effort spent on
getting a better understanding of the approximation guarantees possible
for many objective functions such as $k$-median, $k$-means, and min-sum clustering.
This quest for better approximation algorithms is further fueled by the implicit hope that these better approximations also give us better clusterings. E.g., for many problems such as clustering proteins by function, or clustering images by subject, there is some unknown ``correct'' target clustering---one that clusters proteins by function, or that clusters images by content---and there is an implicit hope is that approximately optimizing these objective functions will in fact
produce a clustering that is close (in symmetric difference) to the truth.
In this paper, we show that if we make this implicit assumption explicit---that is, if we assume that any $c$-approximation to the given clustering objective $F$ is $\epsilon$-close to the target---then we can produce clusterings that are $O(\epsilon)$-close to the target, {\em even for values $c$ for which obtaining a $c$-approximation is NP-hard}. In particular, for $k$-median and $k$-means objectives, we show that we can achieve this guarantee for any constant $c > 1$, and for min-sum objective we can do this for any constant $c > 2$.
Our results also highlight a somewhat surprising conceptual difference between assuming that the {\em optimal} solution to, say, the $k$-median objective is $\epsilon$-close to the target, and assuming that any {\em approximately optimal} solution is $\epsilon$-close to the target, even for approximation factor say $c=1.01$. In the former case, the problem of finding a solution that is
$O(\epsilon)$-close to the target remains computationally hard, and yet for the latter we have an efficient algorithm.
------------------------------------------
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica and Kunal Talwar. Secretary Problems: Weights and Discounts
Abstract: The classical secretary problem studies the problem of selecting
online an element (a ``secretary'') with maximum value in a randomly
ordered sequence. The difficulty lies in the fact that an element must
be either selected or discarded upon its arrival, and this decision is
irrevocable. It is well-known how to design constant-competitive
algorithms for the classical secretary problems (see, e.g., the survey
of Freeman (Internat.~Statist.~Rev.~1983)) and several
variants.
We study the following two extensions of the secretary problem:
1. In the discounted secretary problem, there is a
time-dependent ``discount'' factor $d(t)$, and the benefit derived
from selecting an element/secretary $e$ at time $t$ is $d(t)\cdot
v(e)$. For this problem with arbitrary (not necessarily decreasing) functions
$d(t)$, we show a constant-competitive algorithm when the expected
optimum is known in advance. With no prior knowledge, we exhibit a
lower bound of $\Omega(\frac{\log n}{\log \log n})$, and give a
nearly-matching $O(\log n)$-competitive algorithm.
2. In the weighted secretary problem, up to $K$ secretaries can
be selected; when a secretary is selected (s)he must be irrevocably
assigned to one of $K$ positions, with position $k$ having weight
$w(k)$, and assigning object/secretary $e$ to position $k$ has benefit
$w(k)\cdot v(e)$. The goal is to select secretaries and assign them to
positions to maximize $\sum_{e,k}w(k)\cdot v(e)\cdot x_{ek}$ where $x_{ek}$ is an
indicator variable that secretary $e$ is assigned position $k$. We
give constant-competitive algorithms for this problem.
Most of these results can also be extended to the \emph{matroid
secretary} case (Babaioff et al., \emph{SODA~2007}) for a large family
of matroids with a constant-factor loss, and an $O(\log \text{rank})$
loss for general matroids. These results are based on a reduction from
various matroids to partition matroids which present a unified approach
to many of the upper bounds of Babaioff et al.
These problem is closely connected with online mechanism design (see,
e.g., Hajiaghayi et al., \emph{Elec.~Comm.~2004}). All our algorithms
are monotone, and hence lead to truthful mechanisms for the
corresponding online auction problem.
------------------------------------------
Maria-Florina Balcan, Avrim Blum and Yishay Mansour. Improved Equilibria via Public Service Advertising
Abstract: Many natural games have both bad and good Nash equilibria: their Price of Anarchy is high and yet their Price of Stability is low. In such cases, one could hope to ``move'' behavior from a high cost equilibrium to a low cost one by a ``public service advertising campaign'' encouraging players to follow the low-cost equilibrium, and if every player follows the advice then we are done. This has motivated much of the research on Price of Stability. However, the assumption that everyone follows instructions is unrealistic. A more natural assumption is that some players will follow them, while other players will not. In this paper we consider the question of to what extent can such an advertising campaign cause behavior to switch from a bad equilibrium to a good one even if only a fraction of people actually follow the given advice, and do so only temporarily. Note that unlike in the ``price of altruism'' model we assume everyone will ultimately act in their own interest.
We consider several important and widely studied classes of games including network design with fair cost sharing, scheduling with unrelated machines, party affiliation games (which include consensus and cut games). We show that for some of these games (such as fair cost sharing), a random $\alpha$ fraction of the population following the given advice is sufficient to get behavior within an $O(1/\alpha)$ factor of the price of stability for any $\alpha > 0$. However, for some games such as consensus and cut games, there is a strict threshold (in this case, $\alpha < 1/2$ yields almost no benefit, yet $\alpha > 1/2$ is enough to reach near-optimal behavior), and for some games, such as scheduling, no value $\alpha < 1$ is sufficient. We also consider a ``viral marketing'' model in which certain players are specifically targeted, and analyze the ability of such targeting to influence behavior using a much smaller number of targeted players.
------------------------------------------
Yusu Wang, Kevin Buchin and Maike Buchin. Exact Algorithm for Partial Curve Matching via the Frechet Distance
Abstract: Curve matching is a fundamental problem that occurs in many applications. In this paper, we study the problem of measuring \emph{partial} similarity between curves. More specifically, given two curves, we wish to maximize the total length of subcurves of them that are \emph{close} to each other, where the \emph{closeness} is measured by the Frechet distance, a common distance measure for curves. The resulting maximal length is called the \emph{partial Frechet similarity} between the two input curves. Given two polygonal curves $P$ and $Q$ in $\reals^d$ of sizes $n$ and $m$, respectively, we present the first exact algorithm that runs in polynomial time to compute $\PFDist(P,Q)$, the partial Frechet similarity between $P$ and $Q$, under the $L_1$ and the $L_\infty$ norms. Specifically, we reduce the problem of computing $\PFDist(P,Q)$ to $O(nm(n+m))$ instances of a simpler problem, each of which can be solved in $O((n+m)\log (nm))$ time. Hence the partial Frechet similarity between $P$ and $Q$ under the $L_1$ or the $L_\infty$ norm can be computed in $O(nm(n+m)^2 \log (nm))$ time. To the best of our knowledge, this is the first paper to study this natural definition of partial curve similarity between curves under the continuous setting (where all points in the curve are considered), and present a polynomial-time exact algorithm for it.
------------------------------------------
Pankaj K Agarwal, R Sharathkumar and Hai Yu. Approximate Euclidean Shortest Path amid convex obstacles
Abstract: We study the approximate Euclidean shortest path problem amid a small number k of convex obstacles of total complexity n. We obtain algorithms for
computing approximate shortest paths between two points whose running time
depends linearly in $n$, and data structures for answering approximate
shortest-path distance queries to a fixed source whose size is independent of n.
------------------------------------------
Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld and Elad Verbin. Sorting and Selection in Posets
Abstract: Classical problems of sorting and searching assume an underlying linear ordering of the objects being compared. In this paper, we study these problems in the context of partially ordered sets, in which some pairs of objects are incomparable. This generalization is interesting from a combinatorial perspective, and it has immediate applications in ranking scenarios where there is no underlying linear ordering, e.g., conference submissions. It also has applications in certain settings in biology.
Our results represent significant progress over previous results from two decades ago by Faigle and Turan. In particular, we present the first algorithm that sorts a width-w poset of size n with optimal query complexity O(n (w + log n)). We also describe a variant of Mergesort with query complexity O(w n log(n/w)) and total complexity O(w^2 n log(n/w)); an algorithm with the same query complexity was given by Faigle and Turan, but no efficient implementation of that algorithm is known. Both our sorting algorithms can be applied with negligible overhead to the more general problem of reconstructing transitive relations.
We also consider two related problems: finding the minimal elements, and its generalization to finding the bottom k "levels", called the k-selection problem. We give efficient deterministic and randomized algorithms for finding the minimal elements with O(w n) query and total complexity. We provide matching lower bounds for the query complexity up to a factor of 2 and generalize the results to the k-selection problem. Finally, we present efficient algorithms for computing a linear extension of a poset and computing the heights of all elements.
------------------------------------------
Sergi Elizalde and Peter Winkler. Sorting by Placement and Shift
Abstract: In sorting situations where the final destination of each item
is known, it is natural to repeatedly choose items and place
them where they belong, allowing the intervening items to
shift by one to make room. (In fact, a special case of this
algorithm is commonly used to hand-sort files.) However, it
is not obvious that this algorithm necessarily terminates.
We show that in fact the algorithm terminates after at most
$2^{n-1}-1$ steps in the worst case (confirming a conjecture of
L. Larson), and that there are super-exponentially many
permutations for which this exact bound can be achieved.
The proof involves a curious symmetrical binary representation.
------------------------------------------
Ryan O'Donnell and Yi Wu. 3-Bit Dictator Testing: 1 vs. 5/8
Abstract: In the conclusion of his monumental paper on optimal inapproximability results, Hastad [Has01] suggested that Fourier analysis of Dictator (Long Code) Tests does not seem universally applicable in the study of CSPs. His main open question was to determine if the technique could resolve the approximability of *satisfiable* 3-bit constraint satisfaction problems. In particular, he asked if the "Not Two" (NTW) predicate is non-approximable beyond the random assignment threshold of 5/8 on satisfiable instances. Around the same time, Zwick [Zwi98] showed that all satisfiable 3-CSPs are 5/8-approximable, and conjectured that the 5/8 is optimal.\\
In this work we show that Fourier analysis techniques *can* produce a Dictator Test based on NTW with completeness 1 and soundness 5/8. Our test's analysis uses the Bonami-Gross-Beckner hypercontractive inequality. We also show a soundness *ower bound* of 5/8 for all 3-query Dictator Tests with perfect completeness. This lower bound for Property Testing is proved in part via a semidefinite programming algorithm of Zwick [Zwi98].
Our work completes the determination of the 3-query "Dictatorship Testing curve". Although this represents progress on Zwick's conjecture, current PCP "outer verifier" technology is insufficient to convert our Dictator Test into an NP-hardness-of-approximation result.
------------------------------------------
Siddharth Barman and Shuchi Chawla. Packing multiway cuts in graphs
Abstract: We consider the following ``multiway cut packing" problem in
undirected graphs: we are given a graph $G=(V,E)$ and $k$ commodities,
each corresponding to a set of terminals located at different vertices
in the graph; our goal is to produce a collection of cuts
$\{C_1,\cdots,C_k\}$ such that $C_i$ is a multiway cut for commodity
$i$ and the maximum load on any edge is minimized. The load on an edge
is defined to be the number of cuts in the solution crossing the
edge. In the capacitated version of the problem edges have capacities
$c_e$ and the goal is to minimize the maximum {\em relative} load on
any edge -- the ratio of the edge's load to its capacity. We present
constant factor approximations for this problem in arbitrary
undirected graphs. The multiway cut packing problem arises in the
context of graph labeling problems where we are given a partial
labeling of a set of items and a neighborhood structure over them,
and, informally stated, the goal is to complete the labeling in the
most consistent way. This problem was introduced by Rabani, Schulman,
and Swamy (SODA'08), who developed an $O(\log n/\log \log n)$
approximation for it in general graphs, as well as an improved
$O(\log^2 k)$ approximation in trees. Here $n$ is the number of nodes
in the graph.
We present an LP-based algorithm for the multiway cut packing problem
in general graphs that guarantees a maximum edge load of at most
$8\OPT+4$. Our rounding approach is based on the observation
that every instance of the problem admits a laminar solution (that is,
no pair of cuts in the solution crosses) that is near-optimal. For the
special case where each commodity has only two terminals and all commodities
share a common sink (the ``common sink $s$-$t$ cut packing" problem)
we guarantee a maximum load of $\OPT+1$. Both of these variants are
NP-hard; for the common-sink case our result is optimal.
------------------------------------------
Frederic Chazal, Leonidas Guibas, Steve Oudot and Primoz Skraba. Analysis of Scalar Fields over Point Cloud Data
Abstract: Given a real-valued function f defined over some metric
space X, is it possible to recover some structural information about f
from the sole information of its values at a finite set L of sample
points, whose pairwise distances in X are given? We provide a positive
answer to this question. More precisely, taking advantage of recent
advances on the front of stability for persistence diagrams, we
introduce a novel algebraic construction, based on a pair of nested
families of simplicial complexes built on top of the point cloud L,
from which the persistence diagram of f can be faithfully
approximated. We derive from this construction a series of algorithms
for the analysis of scalar fields from point cloud data. These
algorithms are simple and easy to implement, they have reasonable
complexities, and they come with theoretical guarantees. To illustrate
the genericity and practicality of the approach, we also present some
experimental results obtained in various applications, ranging from
clustering to sensor networks.
------------------------------------------
Frederic Magniez, Ashwin Nayak, Peter Richter and Miklos Santha. On the hitting times of quantum versus random walks
Abstract: The {\em hitting time} of a classical random walk (Markov chain) is
the time required to {\em detect} the presence of (or equivalently, to
{\em find}) a marked state. The hitting time of a quantum walk is
subtler to define -- in particular, the detection and finding
problems are no longer equivalent. We prove relationships among
several definitions of classical and quantum hitting times.
Then, extending a recent theorem of Tulsi [2007] for the 2D grid, we
show that for any state-transitive Markov chain with unique marked
state, the quantum hitting time is of the same order for both the
detection and finding problems. We conjecture that this remains true
for all reversible Markov chains and any number of marked states.
------------------------------------------
Elad Hazan and Satyen Kale. Better Algorithms for Benign Bandits
Abstract: The online multi-armed bandit problem and its generalizations are repeated decision making problems, and incur a cost associated with the decision, in such a way that the total cost incurred over all iterations is close to the cost of the best fixed decision in hindsight. The difference in these costs is known as the {\em regret} of the algorithm. The term {\em bandit} refers to the setting where one only obtains the cost of the decision used in a given iteration and no other information.
Perhaps the most general form of this problem is the non-stochastic bandit linear optimization problem, where the set of decisions is a convex set in some Euclidean space, and the cost functions are linear. Only recently an efficient algorithm attaining $\tilde{O}(\sqrt{T})$ regret was discovered in this setting.
In this paper we propose a new algorithm for the bandit linear optimization problem which obtains a regret bound of $\tilde{O}(\sqrt{Q})$, where $Q$ is the total variation in the cost functions. This regret bound shows that it is possible to incur much less regret in a slowly changing environment, and in fact, matches regret bounds that are attainable in the simpler stochastic setting, when the cost functions are obtained from a probability distribution. This regret bound, previously conjectured to hold in the full information case, is surprisingly attainable even in the bandit setting. Our algorithm is efficient and applies several new ideas to bandit optimization such as reservoir sampling.
------------------------------------------
Florin Constantin, Jon Feldman, S Muthukrishnan and Martin Pal. An Online Mechanism for Ad Slot Reservations with Cancellations
Abstract: Many advertisers (bidders) use Internet systems to buy display
advertisements on publishers' webpages or on traditional media such as
radio, TV and newsprint. They seek a simple, online mechanism to
reserve ad slots in advance. On the other hand, media publishers
(sellers) represent a vast and varying inventory, and they too seek
automatic, online mechanisms for pricing and allocating such
reservations. Designing mechanisms as effective as repeated
Generalized Second Price auctions (that now power spot auctions in
sponsored search) is a great challenge. Such a mechanism should not
only have certain optimization properties (such as in efficiency or
revenue maximization), but also, crucially, have robust game-theoretic
properties (such as honest bidding, limited speculations, etc).
We propose and study a simple model for auctioning such ad slot
reservations in advance. There is one seller with a set of slots to be
displayed at some point T in the future. Until T, bidders arrive
sequentially and place a bid on the slots they are interested in. The
seller must decide immediately whether or not to grant a
reservation. Our model allows the seller to cancel at any time any
reservation made earlier, in which case the holder of the reservation
incurs a utility loss amounting to a fraction of its value for the
reservation, and may also receive a cancellation fee from the seller.
Our main result is an online mechanism for allocation and pricing in
this model with many desirable game-theoretic properties. It is
individually rational; winners have an incentive to be honest and
bidding one's true value dominates any lower bid. Further, it bounds
the earnings of speculators who are in the game to obtain the
cancellation fees. The mechanism in addition has optimization
guarantees. Its revenue is within a constant fraction of the a
posteriori revenue of the famed Vickrey-Clarke-Groves (VCG) auction
which is known to be truthful (in the offline case). Our mechanism's
efficiency is within a constant fraction of the a posteriori optimally
efficient solution. If efficiency also takes into account the utility
losses of bidders whose reservation was canceled, we show that our
mechanism matches (for appropriate values of the parameters) an upper
bound on the competitive ratio of any deterministic online algorithm.
The technical core of the mechanism is a variant of the online
weighted bipartite matching problem where unlike prior variants in
which one randomizes edge arrivals or bounds edge weights, we need to
consider revoking previously committed edges. On top of an online
competitive algorithm for this problem, we impose an appropriate
payment structure to obtain the main game-theoretic and optimization
guarantees of our mechanism. Our results make no assumptions about the
arrival order or value distribution of bidders. They still hold if we
replace items with elements of a matroid and matchings with
independent sets of the matroid, or if all bidders have linear
(additive) value for a set of items.
------------------------------------------
Colin Cooper and Alan Frieze. The cover time of random geometric graphs
Abstract: We study the cover time of random geometric graphs.
Let $I(d)=[0,1]^d$
denote the unit torus in $d$ dimensions.
Let $D(x, r)$ denote the ball (disc) of radius $r$.
Let $\U_d$ be the volume of the
unit ball $D( 0,1)$ in $d$ dimensions.
A random geometric
graph $G=G(d,r,n)$ in $d$ dimensions is defined as follows:
Sample $n$ points $V$ independently
and uniformly at random from $I(d)$.
For each point $x$ draw
a ball $D(x, r)$ of radius $r$ about $ x$.
The vertex set $V(G)=V$ and
the edge set $E(G)=\set{\set{v,w}:\;w\neq v,\,w\in D(v,r)}$.
Let $G(d,r,n),\,d\geq 3$ be a random geometric graph.
Let $c>1$ be constant, and let $r= \brac {c \log n/( \U_d n)}^{1/d}$. Then \whp
$$C_G \sim
c\log\bfrac{c}{c-1} n \log n.$$
------------------------------------------
Lorenz Minder and Alistair Sinclair. The extended k-tree algorithm
Abstract: Consider the following problem: Given $q=2^k$ random lists of $n$-bit
vectors, $L_1, ..., L_q$, each of length $m$, find $x_1 \in L_1, ...,
x_q \in L_q$ such that $x_1 + ... + x_q = 0$, where + is the XOR
operation. This problem has applications in a number of areas,
including cryptanalysis, coding and learning theory. The so-called
$k$-tree algorithm, due to Wagner (CRYPTO 2002) and Blum-Kalai-Wasserman
(JACM 2003), solves this problem in $O(2^{k+n/(k+1)})$ time provided the
length $m$ of the lists is large enough, specifically if $m \geq
2^{n/(k+1)}$.
In many applications, however, it is necessary to work with lists of
smaller length, where the above algorithm breaks down. In this paper we
generalize the algorithm to work for significantly smaller values of
the list length $m$, all the way down to the minimum value for which a
solution exists with reasonable probability. Our algorithm exhibits a
tradeoff between the value of $m$ and the running time. We also provide
rigorous bounds on the failure probability of both our algorithm and
that of Wagner and Blum et al.
------------------------------------------
Misha Belkin, jian sun and Yusu Wang. Constructing Laplace operators from Point Clouds
Abstract: We present an algorithm for approximating the Laplace-Beltrami operator from an
arbitrary point cloud obtained from a $k$-dimensional submanifold embedded in
the $d$-dimensional space. We show that this \emph{PCD Laplace (Point-Cloud
Data Laplace) operator} converges to the Laplace-Beltrami operator on the
underlying manifold as the point cloud becomes denser. Unlike the previous
work, we do not assume that the data samples are independent identically
distributed from a probability distribution and do not require a global mesh.
The resulting algorithm is easy to implement. We present experimental results
indicating that even for point sets sampled from a uniform distribution, PCD
Laplace converges faster than the weighted graph Laplacian. We also show that
certain geometric invariants, such as manifold area, can be estimated directly
from the point cloud using our PCD Laplacian with reasonable accuracy. We make
the software publically available at the authors' webpages.
------------------------------------------
Anirban Dasgupta, Arpita Ghosh, Hamid Nazerzadeh and Prabhakar Raghavan. Online story scheduling for web advertising
Abstract: We study an online job scheduling problem motivated by
\emph{storyboarding} in web advertising, where an advertiser derives
value from having uninterrupted sequential access to a user surfing
the web. The user ceases to browse with probability $1-\beta$ at each
step, independently. \emph{Stories} (jobs) arrive online; job $s$ has
a length $\ell_s$ and a per-unit value $v_s$. We get a value $v_s$ for
every unit of the job that we schedule consecutively without
interruption, discounted for the time at which it is scheduled. Jobs
can be preempted, with no further value derived from the residual
unscheduled units of the job. We seek an online algorithm whose total
reward is competitive against that of the offline scheduler that knows
all jobs in advance.
We consider two models based on the maximum delay that can be allowed
between the arrival and scheduling of a job. In the first, a job
can be scheduled anytime after its arrival; in the second a
job is lost unless scheduled immediately upon arrival, pre-empting a currently running job if needed. The two
settings correspond to two natural models of how long an advertiser
retains interest in a relevant user. We show that there is, in fact,
a {\em sharp separation} between what an online scheduler can achieve
in these two settings. In the first setting with no deadlines, we
give a natural deterministic algorithm with a constant
competitive ratio against the offline scheduler. In contrast,
we show that in the sharp deadline setting, no (deterministic or
randomized) online algorithm can achieve better than a
polylogarithmic ratio.
------------------------------------------
Mohsen Bayati, Andrea Montanari and Amin Saberi. Generating Random Graphs with Large Girth
Abstract: We present a simple and efficient algorithm for randomly generating simple graphs
with no small cycles. These graphs are used to design high performance Low-Density Parity-Check (LDPC) codes. For any constant $k$, $\alpha\leq1/2k(k+3)$ and $m=O(n^{1+\alpha})$, our algorithm generates an almost uniform random graph with girth larger than $k$ in polynomial time.
In this range of $m$ and $n$, the fraction of graphs having girth larger than $k$ is exponentially small in the average degree $(m/n)$. Therefore na\"{i}ve methods such as repeatedly producing graphs from $\gens_{n,m}$ till obtaining one with girth larger than $k$ take exponential amount of time.
Our approach is based on \emph{sequential} methods that have been recently successful for efficiently counting and generating random graphs.
------------------------------------------
Florian Diedrich and Klaus Jansen. Improved Approximation Algorithms for Scheduling with Fixed Jobs
Abstract: We study two closely related problems in non-preemptive scheduling of
sequential jobs on identical parallel machines. In these two settings there are either fixed jobs or non-availability intervals during which the machines are not available; in either case, the objective is to minimize the makespan. Both of these formulations have differentapplications, e.g. in turnaround scheduling or overlay computing.
For both problems we contribute approximation algorithms with an improved ratio of 3/2+epsilon, respectively; these are shown to be basically tight by suitable inapproximability results.
We use dual approximation, creation of a gap structure and job configurations, and a PTAS for the multiple subset sum problem. However, the main feature of our algorithms is a new technique for the assignment of large jobs via flexible rounding. Our new technique is based on an interesting cyclic shifting argument in combination with a network flow model for the assignment of jobs to gaps.
------------------------------------------
Aurore Amaudruz and Christina Fragouli. Combinatorial Algorithms for Wireless Information Flow
Abstract: Calculating the capacity of wireless networks is a notoriously hard problem to solve in information theory - even the case of networks consisting of three nodes remains today unsolved. The difficulty comes from the inherently shared nature of the wireless channels. A node transmitting can reach all receiver nodes within a certain range (broadcasting). However, if multiple nodes transmit at the same time, a node can receive the superposition of the transmitted signals (interference).
Recently, Avestimehr, Diggavi and Tse proposed a linear binary deterministic model that takes into account the interactions between the signals in a wireless network, i.e., broadcasting and interference, and ignores the effect of noise. The argument is that for high Signal-to-Noise-Ratio, it is these signal interactions that will
dominate the performance, and thus the capacity of the deterministic
could be very close to that of the noisy network.
Thus networks of deterministic channels can be used as approximate models for wireless networks.
Constructively taking interference into account allows to achieve, even for a single unicast session,
a capacity that can be $O(N)$ larger than the capacity when only broadcasting and routing are employed,
where $N$ is the number of network nodes, as we show through a developed example.
To characterize how much the capacity of a unicast session is,
Avestimehr, Diggavi and Tse generalized the min-cut max-flow theorem for graphs to networks of deterministic channels.
They showed that the value of the minimum cut is in this case the minimum rank of all the binary
adjacency matrices describing source-destination cuts. However, since there exists an exponential number of cuts, identifying the capacity through exhaustive search becomes very fast infeasible.
Avestimehr et al. also proved that the value of the minimum cut can be achieved, by
using information theoretical tools,
where intermediate network nodes have no complexity constraints,
and perform random mappings using arbitrarily long blocks of bits.
In practical networks, it is not realistic to envisage such operations; thus the natural question that
arises is whether the calculated capacity can be achieved or approximated in practice, using bounded complexity operations at the network nodes, and how well.
In this paper, we develop a polynomial time algorithm
that allows to achieve the min-cut value in binary linear deterministic networks,
for the case of a unicast connection. Our algorithm crucially uses a notion of Linear Independence
between edges, and cannot be derived as direct consequence of the Ford-Fulkerson algorithm
or other path-augmenting techniques over graphs.
Using our algorithm we can calculate the capacity in polynomial time; moreover, we can achieve the capacity by using very simple one-bit processing at the intermediate nodes.
------------------------------------------
Ran Duan and Seth Pettie. Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths
Abstract: Given a directed graph with a capacity on each edge, the
\emph{all-pairs bottleneck paths} (APBP) problem is to determine,
for all vertices $s$ and $t$, the maximum flow that can be routed from $s$ to $t$.
For dense graphs this problem is equivalent to that of computing the $(\max,\min)$-product of two real-valued matrices.
In this paper, we give a $(\max,\min)$-matrix multiplication algorithm running in time $O(n^{(3+\omega)/2})\leq O(n^{2.688})$,
where $\omega$ is the exponent of binary matrix multiplication.
Our algorithm improves on a recent $O(n^{2+\omega/3}) \le O(n^{2.792})$-time algorithm of Vassilevska, Williams, and Yuster.
In a similar fashion to Vassilevska et al., we reduce $(\max,\min)$-product
to computing the {\em dominance product} of sparse real-valued matrices. However, our reduction is different
and we use a completely new sparse dominance product algorithm whose running time is incomparable to that of Vassilevska et al.
The running time of our $(\max,\min)$-multiplier matches that of the best dominance product algorithm
but is slightly slower than the $O(n^{2.575})$-time APBP algorithm of Shapira et al.~that assumes {\em vertex}-capacitated graphs.
We also give faster algorithms for the \emph{all-pairs bottleneck shortest path}
(APBSP) problem on both edge- and vertex-capacitated graphs. The problem here is to find the maximum flow
that can be sent from $s$ to $t$ along a {\em shortest} path w.r.t.~the unit length function.
For edge-capacitated graphs, the running time of our APBSP algorithm is $O(n^{(3+\omega)/2})$, matching the time bound of our APBP algorithm.
For vertex-capacitated graphs the running time is $O(n^{2.65})$, which improves
significantly on the $O(n^{2.86})$ time algorithm of Shapira et al.
------------------------------------------
Mehmet Begen and Maurice Queyranne. Appointment Scheduling with Discrete Random Durations
Abstract: We consider the problem of determining optimal appointment times for a given sequence of jobs (medical procedures) on a single processor
(operating room, examination facility), to minimize the expected total underage and overage costs when each job has a random duration given by its discrete probability distribution. Simple conditions on the cost rates imply that the objective function is L-convex. Then there exists an optimal appointment schedule which is integer and can be found in polynomial time.
------------------------------------------
Navin Goyal, Luis Rademacher and Santosh Vempala. Expanders via Random Spanning Trees
Abstract: Motivated by the problem of routing reliably and scalably in a
graph, we introduce the notion of a splicer, the union of
spanning trees of a graph. We prove that for any bounded-degree
$n$-vertex graph, the union of two random spanning trees
approximates the expansion of every cut of the graph to within a
factor of $O(\log n)$. For the random graph $G_{n,p}$, for $p> c\log{n}/n$,
a constant number of spanning trees give an expander.
This is suggested by the
case of the complete graph, where we prove that a constant number of
random spanning trees give an expander. The construction of the
splicer is elementary --- each spanning tree is produced
independently using an algorithm by Aldous and Broder: a random walk in the graph
with edges leading to previously unvisited vertices included in the
tree.
A second important application of splicers is to graph
sparsification where the goal is to approximate every cut (and more
generally the quadratic form of the Laplacian) using only a small
subgraph of the original graph. Benczur-Karger as well as
Spielman-Srivastava have shown sparsifiers with $O(n \log
n/\eps^2)$ edges that achieve approximation within factors $1+\eps$
and $1-\eps$. Their
methods, based on independent sampling of edges, need $\Omega(n\log
n)$ edges to get any approximation (else the subgraph could be
disconnected) and leave open the question of linear-size
sparsifiers. Splicers address this question for random graphs by
providing sparsifiers of size $O(n)$ that approximate every cut to
within a factor of $O(\log n)$.
------------------------------------------
Aaron Williams. Loopless Generation of Multiset Permutations using a Constant Number of Variables by Prefix Shifts
Abstract: This paper affirmatively answers the following combinatorial question: Can the permutations of any multiset be ordered so that each permutation is a prefix shift of the previous permutation? Previously, the answer was known only for the permutations of any set, and the permutations of any multiset containing at most two distinct elements. As a side benefit, the proof is used to affirmatively answer the following algorithmic question: Can the permutations of any multiset be generated by a loopless algorithm that uses only a constant number of variables? Previously, the best algorithm used a linear number of variables.
------------------------------------------
Ran Duan and Seth Pettie. Dual-Failure Distance and Connectivity Oracles
Abstract: Spontaneous failure is an unavoidable aspect of all networks, particularly those with a physical basis such as communications networks or road networks.
Whether due to malicious coordinated attacks or other causes, failures temporarily change the topology of the network and, as a consequence, its
connectivity and distance metric. In this paper we look at the problem of efficiently answering connectivity, distance, and shortest route queries in the presence of
two node or link failures. Our data structure uses $\tilde{O}(n^2)$ space and answers queries in $\tilde{O}(1)$ time, which is within a polylogarithmic factor of optimal
and nearly matches the single-failure distance oracles of Demetrescu {\em et al.} It may yet be possible to find distance/connectivity oracles capable of handling any fixed number
of failures. However, the sheer complexity of our algorithm suggests that moving beyond dual-failures will require a fundamentally different approach to the problem.
------------------------------------------
david gamarnik and Dimitry Katz. Sequential cavity method for computing limits of the log-partition function for
Abstract: ABSTRACT: One of the key computational problems in combinatorics/statistical physics is the problem of computing
limits of the log-partition functions for various statistical mechanics models on lattices. In combinatorics
this limit corresponds to the exponent of various arrangements on lattices, for example the exponents of the number
of independent sets, proper colorings or matchings on a lattice. We propose a new method, sequential cavity, which
beats the best known existing methods, such as transfer matrix method, in obtaining sharper bounds on the limits
of the log-partition function for two models: independent sets (hard-core) and matchings (monomer-dimer). Our method is based on a surprisingly simple representation of the log-partition function limit in terms of a certain marginal probability of a suitably modified lattice, and using recent deterministic approximation counting algorithms for these two models. Our method also has a provably better theoretical performance compared with the transfer matrix method.
------------------------------------------
Alexander Golynski. Lower Bounds for Succinct Data Structures
Abstract: In this paper, we consider several data structure problems in the static deterministic cell probe model.
%
We develop a new technique for proving lower bounds for succinct data structures, where the redundancy in the storage can be small compared to the information-theoretic minimum.
%
The lower bounds are truly succinct in the sense that we try to match (up to constant factors) the lower order terms of the existing data structures with the lower order terms provided by our lower bound.
%
Using this technique, we obtain (i) the first lower bound for the problem of searching and retrieval of a substring in text; (ii) a cell probe lower bound for the problem of representing permutation $\pi$ with queries $\pi(i)$ and $\pi^{-1}(i)$ that matches the lower order term of the existing data structures, and (iii) a lower bound for representing binary matrices that is also matches upper bounds for some set of parameters.
%
The nature of all these problems is that we are to implement two operations that are in a reciprocal relation to each other (search and retrieval, computing forward and inverse element, operations on rows and columns of a matrix).
%
As far as we know, this paper is the first to provide an insight to such problems.
------------------------------------------
Umang Bhaskar, Lisa Fleischer, Darrell Hoy and Chien-Chung Huang. Equilibria of Collusive Flow Games are not Unique
Abstract: In STOC 2006, Hayrapetyan, Wexler, and Tardos introduced the problem
of studying collusion in congestion games. In this
work, we show that collusion adds significant
complexity to the structure of equilibria in nonatomic routing games,
answering an open question posed by
Comminetti, Correa, and Steir-Moses (ICALP 2006):
Without collusion, it follows from well-known convexity arguments
that equilibria are unique (up to induced latencies). The question
is, does this uniqueness continue to hold in the presence of collusion?
We answer no:
We show that if collusion is allowed in nonatomic routing games,
there may be multiple equilibria.
We demonstrate this multiplicity via 2 specific examples.
In addition, we show our examples are topologically minimal
by giving a complete characterization of
network topologies for which, up to induced latencies,
unique equilibria exist.
------------------------------------------
Sam Greenberg, Amanda Pascoe and Dana Randall. Sampling Biased Lattice Configurations using Exponential Metrics
Abstract: We define a geometric distance function that can be used to show fast mixing of certain natural Markov Chains for biased lattice models, including a reversible tiling model that arises in the context of self-assembly and a coloring model that arises in the context of asynchronous cellular automata. For each of these models, we show that the local Markov chain converges rapidly to the stationary distribution and we believe that couplings based on exponential metrics can be used for many related lattice models.
------------------------------------------
Benoît Hudson, Gary Miller, Todd Phillips and Don Sheehy. Size Complexity of Volume Meshes vs. Surface Meshes
Abstract: Typical volume meshes in three dimensions are designed to conform to
an underlying two-dimensional surface mesh, with volume mesh element size growing larger away from the surface. The surface mesh may be uniformly spaced or
highly graded, and may have fine resolution due to extrinsic mesh size concerns.
When we desire that such a mesh have good aspect ratio, we require that
some space-filling scaffold vertices be
inserted off the surface. We show that under simple preconditions, the number of scaffold vertices will only be linear in the number of surface vertices.
We analyze the number of scaffold vertices
in a setting that encompasses many existing volume meshing algorithms.
------------------------------------------
Yury Lifshits and Shengyu Zhang. Combinatorial Algorithms for Nearest Neighbors, Near-Duplicates and Small-World Design.
Abstract: We study the so called combinatorial framework for algorithmic
problems in similarity spaces. Namely, the input dataset is
represented by a comparison oracle that given three points
x,y,y' answers whether y or y' is closer to x. We assume
that the similarity order of the dataset satisfies the four
variations of the following disorder inequality: if x is
the A'th most similar object to y and y is the B'th most
similar object to z, then x is among the D(A+B) most similar
objects to z.
Though the oracle gives much less information compared to the
standard general metric space model where distance values are
given, one can still design very efficient algorithms
for various fundamental computational tasks. For nearest
neighbor search we present deterministic and exact algorithm with
almost linear time and space complexity of preprocessing, and
near-logarithmic time complexity of search. Then, for
near-duplicate detection we present the first known deterministic
algorithm that requires just near-linear time + time proportional
to the size of output. Finally, we show that for any dataset
satisfying the disorder inequality a visibility graph can be
constructed: all out-degrees are near-logarithmic and greedy
routing deterministically converges to the nearest neighbor of a
target in logarithmic number of steps. The later result is the
first known work-around for Navarro's impossibility of
generalizing Delaunay graphs.
The technical contribution of the paper consists of handling
"false positives" in data structures and an algorithmic
technique up-aside-down-filter.