Preemptive scheduling of equal-length jobs to maximize weighted throughput

We study the problem of computing a preemptive schedule of equal-length jobs with given release times, deadlines and weights. Our goal is to maximize the weighted throughput. In Graham's notation this problem is described as . We provide an O(n⁴)-time algorithm, improving the previous bound of O(n¹⁰).     

Self-duality of bounded monotone boolean functions and related problems

In this paper we examine the problem of determining the self-duality of a monotone boolean function in disjunctive normal form (DNF). We show that the self-duality of monotone boolean functions with n disjuncts such that each disjunct has at most k literals can be determined in O(2^k2k²n) time. This implies an O(n²logn) algorithm for determining the self-duality of -DNF functions. We also consider the version where any two disjuncts have at most c literals in common. For this case we give an O(n^4(c+1)) algorithm for determining self-duality.     

Minimizing a monotone concave function with laminar covering constraints

Let V be a finite set with |V|=n. A family F⊆2^V is called laminar if for all two sets X,Y∈F, X∩Y≠∅ implies X⊆Y or X⊇Y. Given a laminar family F, a demand function , and a monotone concave cost function , we consider the problem of finding a minimum-cost such that x(X)?d(X) for all X∈F. Here we do not assume that the cost function F is differentiable or even continuous. We show that the problem can be solved in O(n²q) time if F can be decomposed into monotone concave functions by the partition of V that is induced by the laminar family F, where q is the time required for the computation of F(x) for any . We also prove that if F is given by an oracle, then it takes Ω(n²q) time to solve the problem, which implies that our O(n²q) time algorithm is optimal in this case. Furthermore, we propose an algorithm if F is the sum of linear cost functions with fixed setup costs. These also make improvements in complexity results for source location and edge-connectivity augmentation problems in undirected networks. Finally, we show that in general our problem requires Ω(2^n/2q) time when F is given implicitly by an oracle, and that it is NP-hard if F is given explicitly in a functional form.     

Computing an eigenvector of an inverse Monge matrix in max-plus algebra

The problem of computing an eigenvector of an inverse Monge matrix in max-plus algebra is addressed. For a general matrix, the problem can be solved in at most O(n³) time. This note presents an O(n²) algorithm for computing one max-plus algebraic eigenvector of an inverse Monge matrix . It is assumed that is irreducible.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

Further analysis of the number of spanning trees in circulant graphs

Let 1?s₁<s₂<?<s_k?⌊n/2⌋ be given integers. An undirected even-valent circulant graph, has n vertices 0,1,2,…, n-1, and for each and j(0?j?n-1) there is an edge between j and . Let stand for the number of spanning trees of . For this special class of graphs, a general and most recent result, which is obtained in [Y.P. Zhang, X. Yong, M. Golin, [The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337-350]], is that where a_n satisfies a linear recurrence relation of order 2^s_k-1. And, most recently, for odd-valent circulant graphs, a nice investigation on the number a_n is [X. Chen, Q. Lin, F. Zhang, The number of spanning trees in odd-valent circulant graphs, Discrete Math. 282 (2004) 69-79].In this paper, we explore further properties of the numbers a_n from their combinatorial structures. Comparing with the previous work, the differences are that (1) in finding the coefficients of recurrence formulas for a_n, we avoid solving a system of linear equations with exponential size, but instead, we give explicit formulas; (2) we find the asymptotic functions and therefore we ‘answer’ the open problem posed in the conclusion of [Y.P. Zhang, X. Yong, M. Golin, The number of spanning trees in circulant graphs, Discrete Math. 223 (2000) 337-350]. As examples, we describe our technique and the asymptotics of the numbers.     

Large deviation principles for sequences of logarithmically weighted means

In this paper we consider several examples of sequences of partial sums of triangular arrays of random variables {Xn:n?1}; in each case Xn converges weakly to an infinitely divisible distribution (a Poisson distribution or a centered Normal distribution). For each sequence we prove large deviation results for the logarithmically weighted means with speed function . We also prove a sample path large deviation principle for {Xn:n?1} defined by , where σ²∈(0,∞) and {Un:n?1} is a sequence of independent standard Brownian motions.     

On the Laplacian spectral radii of trees

Let Δ(T) and μ(T) denote the maximum degree and the Laplacian spectral radius of a tree T, respectively. Let T_n be the set of trees on n vertices, and . In this paper, we determine the two trees which take the first two largest values of μ(T) of the trees T in when . And among the trees in , the tree which alone minimizes the Laplacian spectral radius is characterized. We also prove that for two trees T₁ and T₂ in , if Δ(T₁)>Δ(T₂) and , then μ(T₁)>μ(T₂). As an application of these results, we give a general approach about extending the known ordering of trees in T_n by their Laplacian spectral radii.     

Coloring the complements of intersection graphs of geometric figures

Let be the complement of the intersection graph G of a family of translations of a compact convex figure in Rⁿ. When n=2, we show that , where γ(G) is the size of the minimum dominating set of G. The bound on is sharp. For higher dimension we show that , for n?3. We also study the chromatic number of the complement of the intersection graph of homothetic copies of a fixed convex body in Rⁿ.     

A greedy approximation algorithm for the group Steiner problem

In the group Steiner problem we are given an edge-weighted graph G=(V,E,w) and m subsets of vertices . Each subset g_i is called a group and the vertices in ?_ig_i are called terminals. It is required to find a minimum weight tree that contains at least one terminal from every group.We present a poly-logarithmic ratio approximation for this problem when the input graph is a tree. Our algorithm is a recursive greedy algorithm adapted from the greedy algorithm for the directed Steiner tree problem [Approximating the weight of shallow Steiner trees, Discrete Appl. Math. 93 (1999) 265-285, Approximation algorithms for directed Steiner problems, J. Algorithms 33 (1999) 73-91]. This is in contrast to earlier algorithms that are based on rounding a linear programming based relaxation for the problem [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259, On directed Steiner trees, Proceedings of SODA, 2002, pp. 59-63]. We answer in positive a question posed in [A polylogarithmic approximation algorithm for the Group Steiner tree problem, J. Algorithms 37 (2000) 66-84, preliminary version in Proceedings of SODA, 1998 pp. 253-259] on whether there exist good approximation algorithms for the group Steiner problem that are not based on rounding linear programs. For every fixed constant ε>0, our algorithm gives an approximation in polynomial time. Approximation algorithms for trees can be extended to arbitrary undirected graphs by probabilistically approximating the graph by a tree. This results in an additional multiplicative factor of in the approximation ratio, where |V| is the number of vertices in the graph. The approximation ratio of our algorithm on trees is slightly worse than the ratio of O(log(max_i|g_i|)·logm) provided by the LP based approaches.     

Large deviations for martingales and derivatives

Fix a sequence of positive integers (mn) and a sequence of positive real numbers (wn). Two closely related sequences of linear operators (Tn) are considered. One sequence has given by the Lebesgue derivatives . The other sequence has given by the dyadic martingale when (l−1)/n²?x<l/n² for l=1,…,n². We prove both positive and negative results concerning the convergence of .     

The Cameron-Erd?s conjecture

A subset A of integers is said to be sum-free if a+b∉A for any a,b∈A. Let s(n) be the number of sum-free sets in interval [1,n] of integers. P. Cameron and P. Erd?s conjectured that s(n)=O(2^n/2). We show that for even n and for odd n, where are absolute constants, thereby proving the conjecture.     

Bounded-hops power assignment in ad hoc wireless networks

Motivated by topology control in ad hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). The input consists of a directed complete weighted digraph G=(V,c) (that is, ). The power of a vertex u in a directed spanning subgraph H is given by , and corresponds to the energy consumption required for node u to transmit to all nodes v with uv∈E(H). The power of H is given by . Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint.Min-Power Bounded-Hops Broadcast is a power assignment problem which has as additional input a positive integer d and a r∈V. The output H must be a r-rooted outgoing arborescence of depth at most d. We give an (O(logn),O(logn)) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(dlogn) and power at most O(logn) times the optimum solution.For the Euclidean case, when c(u,v)=c(v,u)=∥u,v∥^κ (here ∥u,v∥ is the Euclidean distance and κ is a constant between 2 and 5), the output of our algorithm can be modified to give a O((logn)^κ) approximation ratio. Previous results for Min-Power Bounded-Hops Broadcast are only exact algorithms based on dynamic programming for the case when the nodes lie on the line and c(u,v)=c(v,u)=∥u,v∥^κ.Our bicriteria results extend to Min-Power Bounded-Hops Strong Connectivity, where H must have a path of at most d edges in between any two nodes. Previous work for Min-Power Bounded-Hops Strong Connectivity consists only of constant or better approximation for special cases of the Euclidean case.     

p-Catalan numbers and squarefree binomial coefficients

In this paper, we consider the generalized Catalan numbers , which we call s-Catalan numbers. For p prime, we find all positive integers n such that p^q divides F(p^q,n), and also determine all distinct residues of , q?1. As a byproduct we settle a question of Hough and the late Simion on the divisibility of the 4-Catalan numbers by 4. In the second part of the paper we prove that if pq?99999, then is not squarefree for n?τ₁(p^q) sufficiently large (τ₁(p^q) computable). Moreover, using the results of the first part, we find n<τ₁(p^q) (in base p), for which may be squarefree. As consequences, we obtain that is squarefree only for n=1,3,45, and is squarefree only for n=1,4,10.     

On finding a large number of 3D points with a small diameter

Given a set S of n points in R³, we wish to decide whether S has a subset of size at least k with Euclidean diameter at most r. It is unknown whether this decision problem is NP-hard. The two closely related optimization problems, (i) finding a largest subset of diameter at most r, and (ii) finding a subset of the smallest diameter of size at least k, were recently considered by Afshani and Chan. For maximizing the size, they presented several polynomial-time algorithms with constant approximation factors, the best of which has a factor of . For maximizing the diameter, they presented a polynomial-time approximation scheme. In this paper, we present improved approximation algorithms for both optimization problems. For maximizing the size, we present two algorithms: the first one improves the approximation factor to 2.5 and the running time by an O(n) factor; the second one improves the approximation factor to 2 and the running time by an O(n²) factor. For minimizing the diameter, we improve the running time of the PTAS from O(nlogn+2^O(1/ε3)n) to O(nlogn+2^{O(1/(ε1.5logε))}n).     

Composition operators on the polydisc induced by smooth symbols

We study composition operators CΦ on the Hardy spaces Hp and weighted Bergman spaces of the polydisc Dn in Cn. When Φ is of class C² on , we show that CΦ is bounded on Hp or if and only if the Jacobian of Φ does not vanish on those points ζ on the distinguished boundary Tn such that Φ(ζ)∈Tn. Moreover, we show that if ε>0 and if , then CΦ is bounded on .