An improved approximation algorithm for the <Emphasis Type="Italic">k</Emphasis>-level facility location problem with soft capacities

We consider the k-level facility location problem with soft capacities (k-LFLPSC). In the k-LFLPSC, each facility i has a soft capacity u _i along with an initial opening cost f _i ≥ 0, i.e., the capacity of facility i is an integer multiple of u _i incurring a cost equals to the corresponding multiple of f _i . We firstly propose a new bifactor (ln(1/β)/(1 ?β),1+2/(1 ?β))-approximation algorithm for the k-level facility location problem (k-LFLP), where β ∈ (0, 1) is a fixed constant. Then, we give a reduction from the k-LFLPSC to the k-LFLP. The reduction together with the above bifactor approximation algorithm for the k-LFLP imply a 5.5053-approximation algorithm for the k-LFLPSC which improves the previous 6-approximation.     

Local search algorithm for universal facility location problem with linear penalties

The universal facility location problem generalizes several classical facility location problems, such as the uncapacitated facility location problem and the capacitated location problem (both hard and soft capacities). In the universal facility location problem, we are given a set of demand points and a set of facilities. We wish to assign the demands to facilities such that the total service as well as facility cost is minimized. The service cost is proportional to the distance that each unit of the demand has to travel to its assigned facility. The open cost of facility i depends on the amount z of demand assigned to i and is given by a cost function \(f_i(z)\). In this work, we extend the universal facility location problem to include linear penalties, where we pay certain penalty cost whenever we refuse serving some demand points. As our main contribution, we present a (\(7.88+\epsilon \))-approximation local search algorithm for this problem.     

Approximation algorithms for the robust facility leasing problem

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods \(\{1, 2, \ldots , T\}\) and a nonnegative integer \(q < n\). At each time period t, a subset of clients \(D_{t}\) arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost \(f_i^{k}\) such that facility i is opened at time period s with a lease length \(l_k\). Each client in \(D_t\) can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost \(c_{ij}\). We want to lease some facilities to serve at least \(n-q\) clients such that the total cost including leasing and serving cost is minimized. Using the standard primal–dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.     

Integration of combinatorial decompositions in the presence of collinearities

Many results in Combinatorial Integral Geometry are derived by integration of the combinatorial decompositions associated with finite point sets {P _i } given in the plane ?². However, most previous cases of integration of the decompositions in question were carried out for the point sets {P _i } containing no triads of collinear points, where the familiar algorithm sometimes called the “Four indicator formula” can be used. The present paper is to demonstrate that the complete combinatorial algorithm valid for sets {P _i } not subject to the mentioned restriction opens the path to various results, including the field of Stochastic Geometry. In the paper the complete algorithm is applied first in an integration procedure in a study of the perforated convex domains, i.e convex domains containing a finite array of non-overlapping convex holes. The second application is in the study of random colorings of the plane that are Euclidean motions invariant in distribution, basing on the theory of random polygonal windows from the so-called Independent Angles (IA) class. The method is a direct averaging of the complete combinatorial decompositions written for colorings observed in polygonal windows from the IA class. The approach seems to be quite general, but promises to be especially effective for the random coloring generated by random Poisson polygon process governed by the Haar measure on the group of Euclidean motions of the plane, assuming that a point P ∈ ?² is colored J if P is covered by exactly J polygons of the Poisson process. A general theorem clearing the way for Laplace transform treatment of the random colorings induced on line segments is formulated.     

The 〈G<Emphasis Type="Italic">/M/r/</Emphasis>FIFO〉 Machine-Interference Model with State-Dependent Speeds

This article treats a version of the multiple machine-interference problem with r operatives under FIFO repair discipline. The running times of machine i are supposed to be identically and arbitrarily distributed random variables with density function f _i (x), i = 1,…, n. The repair times of all machines are assumed to be identically and exponentially distributed random variables with mean 1/μ. The paper provides the main steady-state operational characteristics of the system when the running and repair speeds are dependent on the number of machines in working order.     

A Minimax Approach to Errors-in-Variables Linear Models

The paper considers a simple Errors-in-Variables (EiV) model Y_i = a + bX_i + εξ_i; Z_i= X_i + σζ_i, where ξ_i, ζ_i are i.i.d. standard Gaussian random variables, X_i ∈ ? are unknown non-random regressors, and ε, σ are known noise levels. The goal is to estimates unknown parameters a, b ∈ ? based on the observations {Y_i, Z_i, i = 1, …, n}. It is well known [3] that the maximum likelihood estimates of these parameters have unbounded moments. In order to construct estimates with good statistical properties, we study EiV model in the large noise regime assuming that n → ∞, but \({\epsilon ^2} = \sqrt n \epsilon _ \circ ^2,{\sigma ^2} = \sqrt n \sigma _ \circ ^2\) with some \(\epsilon_\circ^2, \sigma_\circ^2>0\). Under these assumptions, a minimax approach to estimating a, b is developed. It is shown that minimax estimates are solutions to a convex optimization problem and a fast algorithm for solving it is proposed.     

A Probabilistic Characterization of the Dominance Order on Partitions

We present a probabilistic characterization of the dominance order on partitions. Let ν be a partition and Y _ν its Ferrers diagram, i.e. a stack of rows of cells with row i containing ν _i cells. Let the cells of Y _ν be filled with independent and identically distributed draws from the random variable X = B i n(r, p) with r ≥ 1 and p ∈ (0, 1). Given j, t ≥ 0, let P(ν, j, t) be the probability that the sum of all the entries in Y _ν is j while the sum of the entries in each row of Y _ν is no more than t. It is shown that if ν and μ are two partitions of n, ν dominates μ if and only if P(ν, j, t) ≤ P(μ, j, t) for all j, t ≥ 0. It is shown that the same result holds if X is any log-concave integer valued random variable with {i : P(X = i) > 0} = {0, 1,…,r} for some r ≥ 1.     

Packing circles in the smallest circle: an adaptive hybrid algorithm

The circular packing problem (CPP) consists of packing n circles C _i of known radii r _i , i∈N={1,?…,?n}, into the smallest containing circle ?. The objective is to determine the coordinates (x _i ,?y _i ) of the centre of C _i , i∈N, as well as the radius r and centre (x,?y) of ?. CPP, which is a variant of the two-dimensional open-dimension problem, is NP hard. This paper presents an adaptive algorithm that incorporates nested partitioning within a tabu search and applies some diversification strategies to obtain a (near) global optimum. The tabu search is to identify the n circles’ ordering, whereas the nested partitioning is to determine the n circles’ positions that yield the smallest r. The computational results show the efficiency of the proposed algorithm.     

Complete moment convergence of moving average processes under <Emphasis Type="Italic">ρ</Emphasis>-mixing assumption

Let {Y _i : ?∞ < i < ∞} be a doubly infinite sequence of identically distributed ρ-mixing random variables, and {a _i : ?∞ < i < ∞} an absolutely summable sequence of real numbers. In this paper we prove the complete moment convergence for the partial sums of moving average processes \(\{ X_n = \sum\limits_{i = - \infty }^\infty {a_i Y_{i + n,} n \geqslant 1} \} \) based on the sequence {Y _i : ?∞ < i < ∞} of ρ-mixing random variables under some suitable conditions.     

New algorithm for computing the Hermite interpolation polynomial

Let x ₀, x ₁,? , x _n , be a set of n + 1 distinct real numbers (i.e., x _i ≠ x _j , for i ≠ j) and y _{i, k} , for i = 0,1,? , n, and k = 0 ,1 ,? , n _i , with n _i ≥ 1, be given of real numbers, we know that there exists a unique polynomial p _{N ? 1}(x) of degree N ? 1 where \(N={\sum }_{i=0}^{n}(n_{i}+1)\), such that \(p_{N-1}^{(k)}(x_{i})=y_{i,k}\), for i = 0,1,? , n and k = 0,1,? , n _i . P _N?1(x) is the Hermite interpolation polynomial for the set {(x _i , y _{i, k} ), i = 0,1,? , n, k = 0,1,? , n _i }. The polynomial p _N?1(x) can be computed by using the Lagrange polynomials. This paper presents a new method for computing Hermite interpolation polynomials, for a particular case n _i = 1. We will reformulate the Hermite interpolation polynomial problem and give a new algorithm for giving the solution of this problem, the Matrix Recursive Polynomial Interpolation Algorithm (MRPIA). Some properties of this algorithm will be studied and some examples will also be given.     

Coloring number and on-line Ramsey theory for graphs and hypergraphs

Let c,s,t be positive integers. The (c,s,t)-Ramsey game is played by Builder and Painter. Play begins with an s-uniform hypergraph G ₀=(V,E ₀), where E ₀=Ø and V is determined by Builder. On the ith round Builder constructs a new edge e _i (distinct from previous edges) and sets G _i =(V,E _i ), where E _i =E _i?1∪{e _i }. Painter responds by coloring e _i with one of c colors. Builder wins if Painter eventually creates a monochromatic copy of K _s ^t , the complete s-uniform hypergraph on t vertices; otherwise Painter wins when she has colored all possible edges.We extend the definition of coloring number to hypergraphs so that χ(G)≤col(G) for any hypergraph G and then show that Builder can win (c,s,t)-Ramsey game while building a hypergraph with coloring number at most col(K _s ^t ). An important step in the proof is the analysis of an auxiliary survival game played by Presenter and Chooser. The (p,s,t)-survival game begins with an s-uniform hypergraph H ₀ = (V,Ø) with an arbitrary finite number of vertices and no edges. Let H _i?1=(V _i?1,E _i?1) be the hypergraph constructed in the first i ? 1 rounds. On the i-th round Presenter plays by presenting a p-subset P _i ?V _i?1 and Chooser responds by choosing an s-subset X _i ?P _i . The vertices in P _i ? X _i are discarded and the edge X _i added to E _i?1 to form E _i . Presenter wins the survival game if H _i contains a copy of K _s ^t for some i. We show that for positive integers p,s,t with s≤p, Presenter has a winning strategy.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

The general facility location problem with connectivity on trees

In this note we study the general facility location problem with connectivity. We present an O(np ²)-time algorithm for the general facility location problem with connectivity on trees. Furthermore, we present an O(np)-time algorithm for the general facility location problem with connectivity on equivalent binary trees.     

On structural decompositions of finite frames

A frame in an n-dimensional Hilbert space H _n is a possibly redundant collection of vectors {f _i } _i∈I that span the space. A tight frame is a generalization of an orthonormal basis. A frame {f _i } _i∈I is said to be scalable if there exist nonnegative scalars {c _i } _i∈I such that {c _i f _i } _i∈I is a tight frame. In this paper we study the combinatorial structure of frames and their decomposition into tight or scalable subsets by using partially-ordered sets (posets). We define the factor poset of a frame {f _i } _i∈I to be a collection of subsets of I ordered by inclusion so that nonempty J?I is in the factor poset iff {f _j } _j∈J is a tight frame for H _n . We study various properties of factor posets and address the inverse factor poset problem, which inquires when there exists a frame whose factor poset is some given poset P. We then turn our attention to scalable frames and present partial results regarding when a frame can be scaled to have a given factor poset; in doing so we present a bridge between erasure resilience (as studied via prime tight frames) and scalability.     

On a recursive inverse eigenvalue problem

Let s ₁, ..., s _n be arbitrary complex scalars. It is required to construct an n × n normal matrix A such that s _i is an eigenvalue of the leading principal submatrix A _i , i = 1, 2, ..., n. It is shown that, along with the obvious diagonal solution diag(s ₁, ..., s _n ), this problem always admits a much more interesting nondiagonal solution A. As a rule, this solution is a dense matrix; with the diagonal solution, it shares the property that each submatrix A _i is itself a normal matrix, which implies interesting connections between the spectra of the neighboring submatrices A _i and A _{i + 1}.     

A Polynomial Time Algorithm for the Resource Allocation Problem with a Convex Objective Function

Consider the resource allocation problem:minimize ∑ⁿ_i=1 f_i(x_i) subject to ∑ⁿ_i=1 x_i = N and x_i's being nonnegative integers, where each f_i is a convex function. The well-known algorithm based on the incremental method requires O(N log n + n) time to solve this problem. We propose here a new algorithm based on the Lagrange multiplier method, requiring O[n²(log N)²] time. The latter is faster if N is much larger than n. Such a situation occurs, for example, when the optimal sample size problem related to monitoring the urban air pollution is treated.     

Erratum: Scheduling jobs with position-dependent processing times

Bachman and Janiak provided a sketch of the proof that the problem 1∣r _i ,p _i (v)=a _i /v∣C_max is NP-hard in the strong sense. However, they did not show how to avoid using harmonic numbers whose encoding is not pseudo-polynomial, which makes the proof incomplete. In this corrigendum, we provide a new complete proof.     

On necessary and sufficient conditions for the self-normalized central limit theorem

Let X₁, X₂, … be a sequence of independent random variables and S_n = Σ _i=1 ⁿ X_i and V _n ² = Σ _i=1 ⁿ X _i ² . When the elements of the sequence are i.i.d., it is known that the self-normalized sum S_n=V_n converges to a standard normal distribution if and only if max_1?i?n|X_i|/V_n→0 in probability and the mean of X₁ is zero. In this paper, sufficient conditions for the self-normalized central limit theorem are obtained for general independent random variables. It is also shown that if max_1?i?n|X_i|/V_n→0 in probability, then these sufficient conditions are necessary.     

Precise large deviations for sums of random vectors with dependent components of consistently varying tails

Let {X _i = (X _1,i ,...,X _m,i )^?, i ≥ 1} be a sequence of independent and identically distributed nonnegative m-dimensional random vectors. The univariate marginal distributions of these vectors have consistently varying tails and finite means. Here, the components of X ₁ are allowed to be generally dependent. Moreover, let N(·) be a nonnegative integer-valued process, independent of the sequence {X _i , i ≥ 1}. Under several mild assumptions, precise large deviations for S _n = Σ _i=1 ⁿ X _i and S _N(t) = Σ _i=1 ^N(t) X _i are investigated. Meanwhile, some simulation examples are also given to illustrate the results.