Some upper and lower bounds on the coupon collector problem

The classical coupon collector problem is closely related to probabilistic-packet-marking (PPM) schemes for IP traceback problem in the Internet. In this paper, we study the classical coupon collector problem, and derive some upper and lower bounds of the complementary cumulative distribution function (ccdf) of the number of objects (coupons) that one has to check in order to detect a set of different objects. The derived bounds require much less computation than the exact formula. We numerically find that the proposed bounds are very close to the actual ccdf when detecting probabilities are set to the values common to the PPM schemes.     

Asymptotics for the random coupon collector problem

We develop techniques of computing the asymptotics of the expected number of items that one has to check in order to detect all N existing kinds, as N → ∞. The occurring frequencies of the differend kinds are random variables.     

Normal approximation and fourth moment theorems for monochromatic triangles

Given a graph sequence denote by T₃(G_n) the number of monochromatic triangles in a uniformly random coloring of the vertices of G_n with colors. In this paper we prove a central limit theorem (CLT) for T₃(G_n) with explicit error rates, using a quantitative version of the martingale CLT. We then relate this error term to the well-known fourth-moment phenomenon, which, interestingly, holds only when the number of colors satisfies . We also show that the convergence of the fourth moment is necessary to obtain a Gaussian limit for any , which, together with the above result, implies that the fourth-moment condition characterizes the limiting normal distribution of T₃(G_n), whenever . Finally, to illustrate the promise of our approach, we include an alternative proof of the CLT for the number of monochromatic edges, which provides quantitative rates for the results obtained in [7].     

Capacitated transportation problem with bounds on RIM conditions

Motivated by dead-mileage problem assessed in terms of running empty buses from various depots to starting points, we consider a class of the capacitated transportation problems with bounds on total availabilities at sources and total destination requirements. It is often difficult to solve such problems and the present paper establishes their equivalence with a balanced capacitated transportation problem which can be easily solved by existing methods. Sometimes, total flow in transportation problem is also specified by some external decision maker because of budget/political consideration and optimal solution of such problem is of practical interest to the decision maker and has motivated us to discuss such problem. Various situations arising in unbalanced capacitated transportation problems have been discussed in the present paper as a particular case of original problem. In addition, we have discussed paradoxical situation in a balanced capacitated transportation problem and have obtained the paradoxical solution by solving one of the unbalanced problems. Numerical illustrations are included in support of theory.     

On perturbation bounds of the linear complementarity problem

In this paper, new perturbation bounds for linear complementarity problems are presented based on the sign patterns of the solution of the equivalent modulus equations. The new bounds are shown to be the generalization of the existing ones.     

Lower bounds for the quadratic assignment problem

We investigate the classical Gilmore-Lawler lower bound for the quadratic assignment problem. We provide evidence of the difficulty of improving the Gilmore-Lawler bound and develop new bounds by means of optimal reduction schemes. Computational results are reported indicating that the new lower bounds have advantages over previous bounds and can be used in a branch-and-bound type algorithm for the quadratic assignment problem.     

Solution of Shannon's problem on the monotonicity of entropy

It is shown that if are independent and identically distributed square-integrable random variables, then the entropy of the normalized sum

is an increasing function of .

The result also has a version for non-identically distributed random variables or random vectors.

     

On Berry-Esseen bounds of summability transforms

Let , , , be a collection of random variables, where for each , , , are independent. Let be a regular summability method. We provide some rates of convergence (Berry-Esseen type bounds) for the weak convergence of summability transform . We show that when is the classical Cesáro summability method, the rate of convergence of the resulting central limit theorem is best possible among all regular triangular summability methods with rows adding up to one. We further provide some summability results concerning -negligibility. An application of these results characterizes the rate of convergence of Schnabl operators while approximating Lipschitz continuous functions.

     

Upper bounds for the homogeneous case of a two-dimensional packing problem

A method for determining an upper bound for the homogeneous case of a two-dimensional packing problem is presented in this paper. It is based on an analysis of the problem's structure and can be evaluated as the optimal solution of a non-convex minimization problem which can be transformed to a piecewise linear problem by using its special properties. Finally a comparative analysis of solution quality and time complexity is presented.

---

Zusammenfassung In dieser Arbeit wird ein Verfahren zur Bestimmung oberer Schranken für ein homogenes zweidimensionales Packproblem vorgestellt. Auf der Grundlage von Analysen der Problemstruktur kann man eine obere Schranke als optimale Lösung eines nichtkonvexen Minimierungsproblems ermitteln, das unter Ausnutzung spezieller Eigenschaften in ein stückweise lineares Problem transformiert werden kann. Den Abschluß dieser Arbeit bildet eine vergleichende Analyse von Lösungsqualität und Rechenzeitbedarf.

     

Asymptotic distribution for the birthday problem with multiple coincidences,via an embedding of the collision process

We study the random variable B(c, n), which counts the number of balls that must be thrown into n equally‐sized bins in order to obtain c collisions. The asymptotic expected value of B(1, n) is the well‐known appearing in the solution to the birthday problem; the limit distribution and asymptotic moments of B(1, n) are also well known. We calculate the distribution and moments of B(c, n) asymptotically as n goes to ∞ and c = O(n). We have two main tools: an embedding of the collision process — realizing the process as a deterministic function of the standard Poisson process — and a central limit result by Rényi. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 480–502, 2016     

一维紧邻时间随机环境下可逗留随机游动的有关性质

给出了可数状态空间中时间随机环境下可逗留随机游动的一个统一模型,对于一维紧邻时间随机环境下的随机游动,在一定的条件下,讨论它的极限性质和中心极限定理,该结论类似于空间随机环境下的随机游动的有关结论.     

Tight bounds for periodicity theorems on the unbounded Knapsack problem

Three new bounds for periodicity theorems on the unbounded Knapsack problem are developed. Periodicity theorems specify when it is optimal to pack one unit of the best item (the one with the highest profit-to-weight ratio). The successive applications of periodicity theorems can drastically reduce the size of the Knapsack problem under analysis, theoretical or empirical. We prove that each new bound is tight in the sense that no smaller bound exists under the given condition.     

Minimum flow problem on network flows with time-varying bounds

In this paper, we consider the minimum flow problem on network flows in which the lower arc capacities vary with time. We will show that this problem for set {0, 1, … , T} of time points can be solved by at most n minimum flow computations, by combining of preflow-pull algorithm and reoptimization techniques (no matter how many values of T are given). Running time of the presented algorithm is O(n²m).     

Lower bounds for the quadratic assignment problem via triangle decompositions

We consider transformations of the (metric) Quadratic Assignment Problem (QAP) that exploit the metric structure of a given instance. We show in particular how the structural properties of rectangular grids can be used to improve a given lower bound. Our work is motivated by previous research of Palubetskes (1988), and it extends a bounding approach proposed by Chakrapani and Skorin-Kapov (1993). Our computational results indicate that the present approach is practical; it has been applied to problems of dimension up ton = 150. Moreover, the new approach yields by far the best lower bounds on most of the instances of metric QAPs that we considered.The authors gratefully acknowledge financial support by the Christian Doppler Laboratorium für Diskrete Optimierung.     

Some aspects of the finite moment problem

The approximate solution of the finite moment problem $\text{μ}{}_{\mathrm{k}}\text{= ∫}{}_0{}^1\text{x}{}^{\mathrm{k?1}}\text{?(x)}\text{d}\text{x}$, k = 1, 2, 3, …, is considered. This problem is related to the problem of finding a best polynomial least squares approximation to a given function $\text{?(x)}$ in [0,1]. The connection with Laplace transform inversion is emphasized, and a set of special square matrices with integral elements is introduced, which has an intimate relation to the above two problems. These matrices are the well-known inverses of finite segments of the infinite Hilbert matrix.     

The firefighter problem for cubic graphs

We show that the firefighter problem is NP-complete for cubic graphs. We also show that given a rooted tree of maximum degree three in which every leaf is at the same distance from the root, it is NP-complete to decide whether or not there is a strategy that protects every leaf from the fire, which starts at the root. By contrast, we describe a polynomial time algorithm to decide if it is possible to save a given subset of the vertices of a graph with maximum degree three, provided the fire breaks out at a vertex of degree at most two.     

Sharp probability bounds for the binomial moment problem with symmetry

Sharp bounds in terms of the first few binomial moments are found for the probability of a union of events, when the random variable denoting the number of events that occur follows symmetric distribution. Connection between the bounds of this paper and the bounds from a special case of the binomial moment problem of Prekopa (1995) is shown. As a special case, bounds for the probability when the underlying probability distribution is unimodal-symmetric are also found.     

Two-sided bounds and leading term for rates of convergence in the multivariate central limit theorem

For a sequence of independent and identically distributed random vectors, upper and lower bounds are obtained for the discrepancy between the probability measure P_n, induced by their normalized sum, and the Normal measure Φ. The upper and lower bounds are of the same order of magnitude. These results may be derived by a “leading term” approach, in which a signed measure Q_n is introduced as a first order approximation to P_n − Φ. The purpose of this paper is to investigate properties of the leading term.