## Efficient Distributed Random Walks with Applications

Author: Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, Prasad Tetali

Conference: PODC 2010

Journal: Journal of the ACM 2013

Abstract:

We  focus on  the problem of performing random walks efficiently in a distributed network. Given bandwidth constraints, the goal is to minimize the number of rounds required to obtain a random walk sample. We first present a fast sublinear time distributed algorithm for performing random walks whose time complexity is sublinear in the length of the walk. Our algorithm performs a random walk of length $\ell$  in $\tilde{O}(\sqrt{\ell D})$  rounds (with high probability) on an undirected  network, where $D$ is the diameter of the network. This improves over the previous best algorithm that ran in $\tilde{O}(\ell^{2/3}D^{1/3})$ rounds (Das Sarma et al., PODC 2009). We further extend our algorithms to efficiently perform $k$ independent random walks in   $\tilde{O}(\sqrt{k\ell D} + k)$ rounds. We then show that there is a fundamental difficulty in improving the dependence on $\ell$ any further by proving a lower bound of $\Omega(\sqrt{\frac{\ell}{\log \ell}} + D)$ under a general model of distributed random walk algorithms. Our random walk algorithms are useful in speeding up distributed algorithms for a variety of applications that use random walks as a subroutine. We present two main applications. First, we give a fast distributed algorithm for computing a random spanning tree (RST) in an arbitrary (undirected) network which runs in $\tilde{O}(\sqrt{m}D)$ rounds (with high probability; here $m$ is the number of edges). Our second application is a fast decentralized algorithm for estimating mixing time and related parameters of the underlying network. Our algorithm is fully decentralized and can serve as a building block in the design of topologically-aware networks.

Update History

Mar 03, 2009 (New version posted on ArXiv)
Nov 06, 2009 (Link to arXiv posted)
Feb 18, 2010 (New version posted)
Feb 18, 2013 (Journal version posted)

## Stackelberg Pricing is Hard to Approximate within 2−ε

Author Parinya Chalermsook, Bundit Lekhanukit, Danupon Nanongkai

Conference:

Abstract:

Stackelberg Pricing Games is a two-level combinatorial pricing problem studied in the Economics, Operation Research, and Computer Science communities. In this paper, we consider the decade-old shortest path version of this problem which is the first and most studied problem in this family. The game is played on a graph (representing a network) consisting of fixed cost edges and pricable or variable cost edges. The fixed cost edges already have some fixed price (representing the competitor’s prices). Our task is to choose prices for the variable cost edges. After that, a client will buy the cheapest path from a node $s$ to a node $t$, using any combination of fixed cost and variable cost edges. The goal is to maximize the revenue on variable cost edges.

In this paper, we show that the problem is hard to approximate within $2-\epsilon$, improving the previous APX-hardness result by Joret [to appear in Networks]. Our technique combines the existing ideas with a new insight into the price structure and its relation to the hardness of the instances.

Update History

[v1] Oct 2, 2009 (Manuscript posted on arXiv)

## Faster Algorithms for Semi-Matching Problems

Author Jittat Fakcharoenphol, Bundit Lekhanukit, Danupon Nanongkai

For the weighted case, we give an $O(nm\log n)$-time algorithm, where $n$ is the number of vertices and $m$ is the number of edges, by exploiting geometric structure of the problem. This improves the classical $O(n^3)$ algorithms by Horn [Operations Research 1973] and Brono, Coffman and Sethi [Communications of the ACM 1974].
For the unweighted case, the bound could be improved even further. We give a simple divide-and-conquer algorithm which runs in time $O(\sqrt{n}m\log n)$, improving two previous $O(nm)$-time algorithms by Abraham [MSc thesis, University of Glasgow 2003] and Harvey, Ladner, Lovasz and Tamir [WADS 2003 and Journal of Algorithms 2006]. We also extend this algorithm to solve the Balance Edge Cover problem in time $O(\sqrt{n}m\log n)$, improving the previous $O(nm)$-time algorithm by Harada, Ono, Sadakane and Yamashita [ISAAC 2008].