Bounds on the cover time of parallel rotor walks

The rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node successively propagates walkers visiting it along its outgoing arcs in round-robin fashion, according to a fixed ordering. We consider the cover time of such a system, i.e., the number of steps after which each node has been visited by at least one walk, regardless of the initialization of the walks. We show that for any graph with m edges and diameter D, this cover time is at most $\mathrm{\Theta }(mD/\log k)$ and at least $\mathrm{\Theta }(mD/k)$, which corresponds to a speedup of between $\mathrm{\Theta }(\log k)$ and $\mathrm{\Theta }(k)$ with respect to the cover time of a single walk.     

Efficient algorithms for the round-trip 1-center and 1-median problems

This paper presents improved algorithms for the round-trip single-facility location problem on a general graph, in which a set A of collection depots is given and the service distance of a customer is defined to be the distance from the server, to the customer, then to a depot, and back to the server. Each customer i is associated with a subset $A^i\subseteq A$ of depots that i can potentially select from and use. When $A^i=A$ for each customer i, the problem is unrestricted; otherwise it is restricted. For the restricted round-trip 1-center problem, we give an $O(mn\lg n)$-time algorithm. For the restricted 1-median problem, we give an $O(mn\lg (|A|/m)+n^2\lg n)$-time algorithm. For the unrestricted 1-median problem, we give an $O(mn+n^2\lg \lg n)$-time algorithm.     

On the bounds of feedback numbers of (n,k)-star graphs

The feedback number of a graph G is the minimum number of vertices whose removal from G results in an acyclic subgraph. We use $f(n,k)$ to denote the feedback number of the $(n,k)$-star graph $S_{n,k}$ and $p(n,k)$ the number of k-permutations of an n-element set. This paper proves that$p(n,k)?2(k?1)!\left(\begin{array}{c}\hfill n\hfill \\ \hfill k?1\hfill \end{array}\right)?f(n,k)?p(n,k)?2(k?1)!\sum _{i=1}^{\theta }\left(\begin{array}{c}\hfill n?2i+1\hfill \\ \hfill k?i\hfill \end{array}\right),$ where $\theta =\min \{k?1,n?k+1\}$.     

Proximity and average eccentricity of a graph

Let $G=(V,E)$ be a connected graph on n vertices. The proximity $\pi (G)$ of G is the minimum average distance from a vertex of G to all others. The eccentricity $e(v)$ of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity $\mathit{ecc}(G)$ of the graph G is $\frac{1}{n}{\sum }_{v\in V(G)}e(v)$. Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on $n?3$ vertices, $\mathit{ecc}(G)?\pi (G)?\mathit{ecc}(P_n)?\pi (P_n)$, with equality if and only if $G?P_n$. In this paper, we show that this conjecture is true.     

On multiple-instance learning of halfspaces

In multiple-instance learning the learner receives bags, i.e., sets of instances. A bag is labeled positive if it contains a positive example of the target. An $\Omega (d\log r)$ lower bound is given for the VC-dimension of bags of size r for d-dimensional halfspaces and it is shown that the same lower bound holds for halfspaces over any large point set in general position. This lower bound improves an $\Omega (\log r)$ lower bound of Sabato and Tishby, and it is sharp in order of magnitude. We also show that the hypothesis finding problem is NP-complete and formulate several open problems.