On randomized algorithms for the majority problem

In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n−B(n) where B(n) is the number of 1’s in the binary representation of n. In this paper we study randomized algorithms for determining majority, which are allowed to err with probability at most ε. We show that any such algorithm must have expected running time at least . Moreover, we provide a randomized algorithm which shows that this result is best possible. These extend a result of De Marco and Pelc [G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006) 823-834].     

The Poisson aggregation process

In this paper we introduce and analyze the Poisson Aggregation Process (PAP): a stochastic model in which a random collection of random balls is stacked over a general metric space. The scattering of the balls’ centers follows a general Poisson process over the metric space, and the balls’ radii are independent and identically distributed random variables governed by a general distribution. For each point of the metric space, the PAP counts the number of balls that are stacked over it. The PAP model is a highly versatile spatial counterpart of the temporal M/G/∞ model in queueing theory. The surface of the moon, scarred by circular meteor-impact craters, exemplifies the PAP model in two dimensions: the PAP counts the number of meteor-impacts that any given moon-surface point sustained. A comprehensive analysis of the PAP is presented, and the closed-form results established include: general statistics, stationary statistics, short-range and long-range dependencies, a Central Limit Theorem, an Extreme Limit Theorem, and fractality.     

Helly-Type Theorems for Line Transversals to Disjoint Unit Balls

We prove Helly-type theorems for line transversals to disjoint unit balls in ℝ ^d . In particular, we show that a family of n≥2d disjoint unit balls in ℝ ^d has a line transversal if, for some ordering ≺ of the balls, any subfamily of 2d balls admits a line transversal consistent with ≺. We also prove that a family of n≥4d−1 disjoint unit balls in ℝ ^d admits a line transversal if any subfamily of size 4d−1 admits a transversal. Andreas Holmsen was supported by the Research Council of Norway, prosjektnummer 166618/V30. Otfried Cheong and Xavier Goaoc acknowledge support from the French-Korean Science and Technology Amicable Relationships program (STAR).     

Covering L p Spaces by Balls

We prove that, given any covering of any separable infinite-dimensional uniformly rotund and uniformly smooth Banach space X by closed balls each of positive radius, some point exists in X which belongs to infinitely many balls.     

Line Transversals to Disjoint Balls

We prove that the set of directions of lines intersecting three disjoint balls in ℝ³ in a given order is a strictly convex subset of . We then generalize this result to n disjoint balls in ℝ ^d . As a consequence, we can improve upon several old and new results on line transversals to disjoint balls in arbitrary dimension, such as bounds on the number of connected components and Helly-type theorems.     

Covering an ellipsoid with equal balls

The thinnest coverings of ellipsoids are studied in the Euclidean spaces of an arbitrary dimension n. Given any ellipsoid, our goal is to find the minimum number of unit balls needed to cover this ellipsoid. A tight asymptotic bound on the logarithm of this number is obtained.     

How to collect balls moving in the Euclidean plane

In this paper, we study how to collect n balls moving with a fixed constant velocity in the Euclidean plane by k robots moving on straight track-lines through the origin. Since all the balls might not be caught by robots, differently from Moving-target TSP, we consider the following 3 problems in various situations: (i) deciding if k robots can collect all n balls; (ii) maximizing the number of the balls collected by k robots; (iii) minimizing the number of the robots to collect all n balls. The situations considered in this paper contain the cases in which track-lines are given (or not), and track-lines are identical (or not). For all problems and situations, we provide polynomial time algorithms or proofs of intractability, which clarify the tractability-intractability frontier in the ball collecting problems in the Euclidean plane.     

Diversity vectors of balls in graphs and estimates of the components of the vectors

The diversity vectors of balls are considered (the ith component of a vector of this kind is equal to the number of different balls of radius i) for the usual connected graphs and the properties of the components of the vectors are studied. The sharp upper and lower estimates are obtained for the number of different balls of a given radius in the n-vertex graphs (trees) and n-vertex trees (graphs with n ? 2d) of diameter d. It is shown that the estimates are precise in every graph regardless of the radius of balls. It is proven a necessary and sufficient condition is given for the existence of an n-vertex graph of diameter d with local (complete) diversity of balls.     

On the problem of characterizing the diversity vectors of balls

Under study are the diversity vectors of balls (the ith entry of the vector is equal to the number of different balls of radius i) for ordinary connected graphs. The problem is solved of characterizing the diversity vectors of balls in graphs of small diameter.     

Estimation in the Markov-Pólya scheme

The Markov-Pólya urn scheme is considered, in which the balls are sequentially and equiprobably drawn from an urn initially containing a given numberaj of balls of thejth color,j = 1,…,N, and after each draw the ball is returned into the urn together withs new balls of the same color. It is assumed that at the beginning only the total number of balls in the urn is known and one must estimate its structure ā = (a1, …,aN) by observing the frequencies inn trials of the balls of corresponding colors. Various approaches including the Bayes and minimax ones for estimatingā under a quadratic loss function are discussed. The connection of the obtained results with known ones for multinomial and multivariate hypergeometric distributions is also discussed.     

Randomized allocation processes

Many dynamic resource allocation and on‐line load balancing problems can be modeled by processes that sequentially allocate balls into bins. The balls arrive one by one and are to be placed into bins on‐line without using a centralized controller. If n balls are sequentially placed into n bins by placing each ball in a randomly chosen bin, then it is widely known that the maximum load in bins is ln n /ln ln n?(1+o(1)) with high probability. Azar, Broder, Karlin, and Upfal extended this scheme, so that each ball is placed sequentially into the least full of d randomly chosen bins. They showed that the maximum load of the bins reduces exponentially and is ln ln n/In d+Θ(1) with high probability, provided d<2. In this paper we investigate various extensions of these schemes that arise in applications in dynamic resource allocation and on‐line load balancing. Traditionally, the main aim of allocation processes is to place balls into bins to minimize the maximum load in bins. However, in many applications it is equally important to minimize the number of choices performed (the allocation time). We study adaptive allocation schemes that achieve optimal tradeoffs between the maximum load, the maximum allocation time, and the average allocation time. We also investigate allocation processes that may reallocate the balls. We provide a tight analysis of a natural class of processes that each time a ball is placed in one of d randomly chosen bins may move balls among these d bins arbitrarily. Finally, we provide a tight analysis of the maximum load of the off‐line process in which each ball may be placed into one of d randomly chosen bins. We apply this result to competitive analysis of on‐line load balancing processes. ©2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 297–331, 2001     

Complex Banach spaces whose duals areL 1-spaces

We prove that for a complex Banach spaceA the following properties are equivalent:

1. A ^* is isometric to anL ₁(μ)-space;
2. every family of 4 balls inA with the weak intersection property has a non-empty intersection;
3. every family of 4 balls inA such that any 3 of them have a non-empty intersection, has a non-empty intersection.

     

Tutte uniqueness of line graphs

We prove that if a graph H has the same Tutte polynomial as the line graph of a d-regular, d-edge-connected graph, then H is the line graph of a d-regular graph. Using this result, we prove that the line graph of a regular complete t-partite graph is uniquely determined by its Tutte polynomial. We prove the same result for the line graph of any complete bipartite graph.     

A combinatorial problem on translation-invariant extensions of the Lebesgue measure

It is proved that, for every natural number k≥2, there exist k subsets of the real line such that any k−1 of them can be made measurable with respect to a translation-invariant extension of the Lebesgue measure, but there is no nonzero σ-finite translation-quasi-invariant measure for which all of these k subsets become measurable. In connection with this result, a related open problem is posed.     

A Unified Derivation of the Complementary Waiting Time Distribution in Sequential Occupancy

Occupancy distributions are defined on the stochastic model of random allocation of balls to a specific number of distinguishable urns. The reduction of the joint distribution of the occupancy numbers, when a specific number of balls are allocated, to the joint conditional distribution of independent random variables given their sum, when the number of balls allocated is unspecified, is a powerful technique in the study of occupancy distributions. Consider a supply of balls randomly distributed into n distinguishable urns and assume that the number X of balls distributed into any specific urn is a random variable with probability function P(X = x) = q _x , x = 0, 1,.... The probability function of the number L _r of occupied urns until r balls are placed into previously occupied urns is derived in terms of convolutions of q _x , x = 0, 1,... and their finite differences. Further, using this distribution, the minimum variance unbiased estimator of the parameter n, based on a suitable sequential sampling scheme, is deduced. Finally, some illustrating applications are discussed.      

Randomized strategies for the plurality problem

We consider a game played by two players, Paul and Carol. At the beginning of the game, Carol fixes a coloring of n balls. At each turn, Paul chooses a pair of the balls and asks Carol whether the balls have the same color. Carol truthfully answers his question. Paul’s goal is to determine the most frequent (plurality) color in the coloring by asking as few questions as possible. The game is studied in the probabilistic setting when Paul is allowed to choose his next question randomly.We give asymptotically tight bounds both for the case of two colors and many colors. For the balls colored by k colors, we prove a lower bound Ω(kn) on the expected number of questions; this is asymptotically optimal. For the balls colored by two colors, we provide a strategy for Paul to determine the plurality color with the expected number of questions; this almost matches the lower bound .     

Ball-covering property of Banach spaces

We consider the following question: For a Banach spaceX, how many closed balls not containing the origin can cover the sphere of the unit ball? This paper shows that: (1) IfX is smooth and with dimX=n<∞, in particular,X=R ⁿ,then the sphere can be covered byn+1 balls andn+1 is the smallest number of balls forming such a covering. (2) Let Λ be the set of all numbersr>0 satisfying: the unit sphere of every Banach spaceX admitting a ball-covering consisting of countably many balls not containing the origin with radii at mostr impliesX is separable. Then the exact upper bound of Λ is 1 and it cannot be attained. (3) IfX is a Gateaux differentiability space or a locally uniformly convex space, then the unit sphere admits such a countable ball-covering if and only ifX ^* isw ^*-separable.     

Pinning a Line by Balls or Ovaloids in ℝ<Superscript>3</Superscript>

We show that if a line ℓ is an isolated line transversal to a finite family F\mathcal{F} of (possibly intersecting) balls in ℝ³ and no two balls are externally tangent on ℓ, then there is a subfamily G í F\mathcal{G}\subseteq\mathcal{F} of size at most 12 such that ℓ is an isolated line transversal to G\mathcal{G}. We generalize this result to families of semialgebraic ovaloids.     

Saturated packings and reduced coverings obtained by perturbing tilings

Let a normed space X possess a tiling T consisting of unit balls. We show that any packing P of X obtained by a small perturbation of T is completely translatively saturated; that is, one cannot replace finitely many elements of P by a larger number of unit balls such that the resulting arrangement is still a packing.In contrast with that, given a tiling T of Rⁿ with images of a convex body C under Euclidean isometries, there may exist packings P consisting of isometric images of C obtained from T by arbitrarily small perturbations which are no longer completely saturated. This means that there exists some positive integer k such that one can replace k−1 members of P by k isometric copies of C without violating the packing property. However, we quantify a tradeoff between the size of the perturbation and the minimal k such that the above phenomenon occurs.Analogous results are obtained for coverings.     

Line transversals to blown up closed balls

The number ?? _d (k) is defined as the minimum ???>?0 such that the following holds: For any finite family ${\mathcal {F}=\{B_1,B_2, \ldots , B_n\}}$ of closed balls in ${{\mathbb{R}}^d}$ such that every k elements of ${\mathcal {F}}$ have a common line transversal, the elements of the blown up family ${\lambda\mathcal {F}=\{\lambda B_1,\lambda B_2, \ldots , \lambda B_n\}}$ have a common line transversal. In this paper we show that ${\lambda_d(d+1)\leq4, \lambda_2(4)\leq 2\sqrt 2}$ and ??₂(3)?<?2.88.