Analysis of algorithms for an online version of the convoy movement problem

In the convoy movement problem (CMP), a set of convoys must be routed from specified origins to destinations in a transportation network, represented by an undirected graph. Two convoys may not cross each other on the same edge while travelling in opposing directions, a restriction referred to as blocking. However, convoys are permitted to follow each other on the same edge, with a specified headway separating them, but no overtaking is permitted. Further, the convoys to be routed are distinguished based on their length. Particle convoys have zero length and are permitted to traverse an edge simultaneously, whereas convoys with non-zero length have to follow each other, observing a headway. The objective is to minimize the total time taken by convoys to travel from their origins to their destinations, given the travel constraints on the edges. We consider an online version of the CMP where convoy demands arise dynamically over time. For the special case of particle convoys, we present an algorithm that has a competitive ratio of 3 in the worst case and (5/2) on average. For the particle convoy problem, we also present an alternate, randomized algorithm that provides a competitive ratio of (√13?1). We then extend the results to the case of convoys with length, which leads to an algorithm with an O(T+CL) competitive ratio, where T={Max _e t(e)}/{Min _e t(e)}, C is the maximum congestion (the number of distinct convoy origin–destination pairs that use any edge e) and L={Max _c L(c)}/{Min _c L(c)}; here L(c)>0 represents the time-headway to be observed by any convoy that follows c and t(e) represents the travel time for a convoy c on edge e.     

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.     

An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

Heuristic algorithms for general <Emphasis Type="Italic">k</Emphasis>-level facility location problems

In a general k-level uncapacitated facility location problem (k-GLUFLP), we are given a set of demand points, denoted by D, where clients are located. Facilities have to be located at a given set of potential sites, which is denoted by F in order to serve the clients. Each client needs to be served by a chain of k different facilities. The problem is to determine some sites of F to be set up and to find an assignment of each client to a chain of k facilities so that the sum of the setup costs and the shipping costs is minimized. In this paper, for a fixed k, an approximation algorithm within a factor of 3 of the optimum cost is presented for k-GLUFLP under the assumption that the shipping costs satisfy the properties of metric space. In addition, when no fixed cost is charged for setting up the facilities and k=2, we show that the problem is strong NP-complete and the constant approximation factor is further sharpen to be 3/2 by a simple algorithm. Furthermore, it is shown that this ratio analysis is tight.     

Optimal Linear Bernoulli Factories for Small Mean Problems

Suppose a coin with unknown probability p of heads can be flipped as often as desired. A Bernoulli factory for a function f is an algorithm that uses flips of the coin together with auxiliary randomness to flip a single coin with probability f(p) of heads. Applications include perfect sampling from the stationary distribution of certain regenerative processes. When f is analytic, the problem can be reduced to a Bernoulli factory of the form f(p) = C p for constant C. Presented here is a new algorithm that for small values of C p, requires roughly only C coin flips. From information theoretic considerations, this is also conjectured to be (to first order) the minimum number of flips needed by any such algorithm. For large values of C p, the new algorithm can also be used to build a new Bernoulli factory that uses only 80 % of the expected coin flips of the older method. In addition, the new method also applies to the more general problem of a linear multivariate Bernoulli factory, where there are k coins, the kth coin has unknown probability p _k of heads, and the goal is to simulate a coin flip with probability C ₁ p ₁+? + C _k p _k of heads.     

How to make a linear network code (strongly) secure

A linear network code is called k-secure if it is secure even if an adversary eavesdrops at most k edges. In this paper, we show an efficient deterministic construction algorithm of a linear transformation T that transforms an (insecure) linear network code to a k-secure one for any k, and extend this algorithm to strong k-security for any k . Our algorithms run in polynomial time if k is a constant, and these time complexities are explicitly presented. We also present a concrete size of \(|\mathsf{F}|\) for strong k-security, where \(\mathsf{F}\) is the underling finite field.     

Approximation algorithms for <Emphasis Type="Italic">k</Emphasis>-echelon extensions of the one warehouse multi-retailer problem

In this paper, we consider k-echelon extensions of the deterministic one warehouse multi-retailer problem. We give constant factor approximation algorithms for some of these extensions when k is fixed. We focus first on the case without backorders and we give a \((2k-1)\)-approximation algorithm under general assumptions on the evolution of the holding costs as products move toward the final customers. We then improve this result to a k-approximation when the holding costs are monotonically non-increasing or non-decreasing (which is a natural situation in practice). Finally we address problems with backorders: we give a 3-approximation for the one-warehouse multi-retailer problem with backlog and a k-approximation algorithm for the k-level Joint Replenishment Problem with backlog (a variant where inventory can only be kept at the final retailers). Ours results are the first constant approximation algorithms for those problems. In addition, we demonstrate the potential of our approach on a practical case. Our preliminary experiments show that the average optimality gap is around 15%.     

Radar placement along banks of river

In this paper, we consider the Radar Placement and Power Assignment problem (RPPA) along a river. In this problem, a set of crucial points in the river are required to be monitored by a set of radars which are placed along the two banks. The goal is to choose the locations for the radars and assign powers to them such that all the crucial points are monitored and the total power is minimized. If each crucial point is required to be monitored by at least k radars, the problem is a k-Coverage RPPA problem (k-CRPPA). Under the assumption that the river is sufficiently smooth, one may focus on the RPPA problem along a strip (RPPAS). In this paper, we present an O(n ⁹) dynamic programming algorithm for the RPPAS, where n is the number of crucial points to be monitored. In the special case where radars are placed only along the upper bank, we present an O(kn ⁵) dynamic programming algorithm for the k-CRPPAS. For the special case that the power is linearly dependent on the radius, we present an O(n log n)-time \({2\sqrt 2}\)-approximation algorithm for the RPPAS.     

Metric extension operators,vertex sparsifiers and Lipschitz extendability

We study vertex cut and flow sparsifiers that were recently introduced by Moitra (2009), and Leighton and Moitra (2010). We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k/ log log k) cut and flow sparsifiers, matching the best known existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log²k/ log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomialtime algorithm for finding optimal operators.     

Markov decision processes with noise-corrupted and delayed state observations

We consider the partially observed Markov decision process with observations delayed by k time periods. We show that at stage t, a sufficient statistic is the probability distribution of the underlying system state at stage t - k and all actions taken from stage t - k through stage t - 1. We show that improved observation quality and/or reduced data delay will not decrease the optimal expected total discounted reward, and we explore the optimality conditions for three important special cases. We present a measure of the marginal value of receiving state observations delayed by (k - 1) stages rather than delayed by k stages. We show that in the limit as k →∞ the problem is equivalent to the completely unobserved case. We present numerical examples which illustrate the value of receiving state information delayed by k stages.     

New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths

The independent set problem is solvable in polynomial time for the graphs not containing the path P _k for any fixed k. If the induced path P _k is forbidden then the complexity of this problem is unknown for k > 6. We consider the intermediate cases that the induced path P _k and some of its spanning supergraphs are forbidden. We prove the solvability of the independent set problem in polynomial time for the following cases: (1) the supergraphs whose minimal degree is less than k/2 are forbidden; (2) the supergraphs whose complementary graph has more than k/2 edges are forbidden; (3) the supergraphs from which we can obtain P _k by means of graph intersection are forbidden.     

Fast separation for the three-index assignment problem

A critical step in a cutting plane algorithm is separation, i.e., establishing whether a given vector x violates an inequality belonging to a specific class. It is customary to express the time complexity of a separation algorithm in the number of variables n. Here, we argue that a separation algorithm may instead process the vector containing the positive components of x,  denoted as supp(x),  which offers a more compact representation, especially if x is sparse; we also propose to express the time complexity in terms of |supp(x)|. Although several well-known separation algorithms exploit the sparsity of x,  we revisit this idea in order to take sparsity explicitly into account in the time-complexity of separation and also design faster algorithms. We apply this approach to two classes of facet-defining inequalities for the three-index assignment problem, and obtain separation algorithms whose time complexity is linear in |supp(x)| instead of n. We indicate that this can be generalized to the axial k-index assignment problem and we show empirically how the separation algorithms exploiting sparsity improve on existing ones by running them on the largest instances reported in the literature.     

A gradual rank increasing process for matrix completion

The matrix completion problem is easy to state: let A be a given data matrix in which some entries are unknown. Then, it is needed to assign “appropriate values” to these entries. A common way to solve this problem is to compute a rank-k matrix, B _k , that approximates A in a least squares sense. Then, the unknown entries in A attain the values of the corresponding entries in B _k . This raises the question of how to determine a suitable matrix rank. The method proposed in this paper attempts to answer this question. It builds a finite sequence of matrices \(B_{k}, k = 1, 2, \dots \), where B _k is a rank-k matrix that approximates A in a least squares sense. The computational effort is reduced by using B _k-1 as starting point in the computation of B _k . The ability of B _k to serve as substitute for A is measured with two objective functions: a “training” function that measures the distance between the known part of A and the corresponding part of B _k , and a “probe” function that assesses the quality of the imputed entries. Watching the changes in these functions as k increases enables us to find an optimal matrix rank. Numerical experiments illustrate the usefulness of the proposed approach.     

A Formula for the Partition Function That “Counts”

We derive a combinatorial multisum expression for the number D(n, k) of partitions of n with Durfee square of order k. An immediate corollary is therefore a combinatorial formula for p(n), the number of partitions of n. We then study D(n, k) as a quasipolynomial. We consider the natural polynomial approximation \({\tilde{D}(n, k)}\) to the quasipolynomial representation of D(n, k). Numerically, the sum \({\sum_{1\leq k \leq \sqrt{n}} \tilde{D}(n, k)}\) appears to be extremely close to the initial term of the Hardy-Ramanujan-Rademacher convergent series for p(n).     

Computational complexity of the original and extended diophantine Frobenius problem

We deduce the law of nonstationary recursion which makes it possible, for given a primitive set A = {a ₁,...,a _k }, k > 2, to construct an algorithm for finding the set of the numbers outside the additive semigroup generated by A. In particular, we obtain a new algorithm for determining the Frobenius numbers g(a ₁,...,a _k ). The computational complexity of these algorithms is estimated in terms of bit operations. We propose a two-stage reduction of the original primitive set to an equivalent primitive set that enables us to improve complexity estimates in the cases when the two-stage reduction leads to a substantial reduction of the order of the initial set.     

A polynomial-time approximation scheme for the Euclidean problem on a cycle cover of a graph

We study the minimum-weight k-size cycle cover problem (Min-k-SCCP) of finding a partition of a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a natural generalization of the known traveling salesman problem (TSP) and has a number of applications in operations research and data analysis. We show that the problem is strongly NP-hard in the general case and preserves intractability even in the geometric statement. For the metric subclass of the problem, a 2-approximation algorithm is proposed. For the Euclidean Min-2-SCCP, a polynomial-time approximation scheme based on Arora’s approach is built.     

Boundary value problem with normal derivatives for a higher-order elliptic equation on the plane

For an elliptic operator of order 2l with constant (and only leading) real coefficients, we consider a boundary value problem in which the normal derivatives of order (k _j ?1), j = 1,..., l, where 1 ≤ k ₁ < ··· < k _l, are specified. It becomes the Dirichlet problem for kj = j and the Neumann problem for k _j = j + 1. We obtain a sufficient condition for the Fredholm property of which problem and derive an index formula.     

On the k-polygonal numbers and the mean value of Dedekind sums

For any positive integer k ≥ 3, it is easy to prove that the k-polygonal numbers are a_n(k) = (2n+n(n?1)(k?2))/2. The main purpose of this paper is, using the properties of Gauss sums and Dedekind sums, the mean square value theorem of Dirichlet L-functions and the analytic methods, to study the computational problem of one kind mean value of Dedekind sums S(a_n(k)ā_m(k), p) for k-polygonal numbers with 1 ≤ m, n ≤ p ? 1, and give an interesting computational formula for it.     

Parity check matrices and product representations of squares

Let \(N_{\mathbb{F}} \)(n,k,r) denote the maximum number of columns in an n-row matrix with entries in a finite field \(\mathbb{F}\) in which each column has at most r nonzero entries and every k columns are linearly independent over \(\mathbb{F}\). We obtain near-optimal upper bounds for \(N_{\mathbb{F}} \)(n,k,r) in the case k > r. Namely, we show that \(N_\mathbb{F} (n,k,r) \ll n^{\frac{r}{2} + \frac{{cr}}{k}} \) where \(c \approx \frac{4}{3}\) for large k. Our method is based on a novel reduction of the problem to the extremal problem for cycles in graphs, and yields a fast algorithm for finding short linear dependencies. We present additional applications of this method to a problem on hypergraphs and a problem in combinatorial number theory.     

On Representation of a Solution to the Cauchy Problem by a Fourier Series in Sobolev-Orthogonal Polynomials Generated by Laguerre Polynomials

We consider the problem of representing a solution to the Cauchy problem for an ordinary differential equation as a Fourier series in polynomials l _r,k ^α (x) (k = 0, 1,...) that are Sobolev-orthonormal with respect to the inner product

$$\left\langle {f,g} \right\rangle = \sum\limits_{v = 0}^{r - 1} {{f^{(v)}}(0){g^{(v)}}} (0) + \int\limits_0^\infty {{f^{(r)}}(t)} {g^{(r)}}(t){t^\alpha }{e^{ - t}}dt$$

, and generated by the classical orthogonal Laguerre polynomials L _k ^α (x) (k = 0, 1,...). The polynomials l _r,k ^α (x) are represented as expressions containing the Laguerre polynomials L _n ^α?r (x). An explicit form of the polynomials l _r,k+r ^α (x) is established as an expansion in the powers x ^r+l , l = 0,..., k. These results can be used to study the asymptotic properties of the polynomials l _r,k ^α (x) as k→∞and the approximation properties of the partial sums of Fourier series in these polynomials.