Local Approximability of Max-Min and Min-Max Linear Programs

In a max-min LP, the objective is to maximise ω subject to A x≤1, C x≥ω 1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A x≤ρ 1, C x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a _i of A has at most Δ _I positive elements, and each row c _k of C has at most Δ _K positive elements.     

Approximability of Sparse Integer Programs

The main focus of this paper is a pair of new approximation algorithms for certain integer programs. First, for covering integer programs {min cx:Ax≥b,0≤x≤d} where A has at most k nonzeroes per row, we give a k-approximation algorithm. (We assume A,b,c,d are nonnegative.) For any k≥2 and ε>0, if P≠NP this ratio cannot be improved to k−1−ε, and under the unique games conjecture this ratio cannot be improved to k−ε. One key idea is to replace individual constraints by others that have better rounding properties but the same nonnegative integral solutions; another critical ingredient is knapsack-cover inequalities. Second, for packing integer programs {max cx:Ax≤b,0≤x≤d} where A has at most k nonzeroes per column, we give a (2k ²+2)-approximation algorithm. Our approach builds on the iterated LP relaxation framework. In addition, we obtain improved approximations for the second problem when k=2, and for both problems when every A _ij is small compared to b _i . Finally, we demonstrate a 17/16-inapproximability for covering integer programs with at most two nonzeroes per column.     

Randomized approximation of bounded multicovering problems

The problem of finding approximate solutions for a subclass of multicovering problems denoted byILP(k, b) is considered. The problem involves findingx∈{0,1} ⁿ that minimizes ∑ _j x _j subject to the constraintAx≥b, whereA is a 0–1m×n matrix with at mostk ones per row,b is an integer vector, andb is the smallest entry inb. This subclass includes, for example, the Bounded Set Cover problem whenb=1, and the Vertex Cover problem whenk=2 andb=1. An approximation ratio ofk−b+1 is achievable by known deterministic algorithms. A new randomized approximation algorithm is presented, with an approximation ratio of (k−b+1)(1−(c/m)^1/(k−b+1)) for a small constantc>0. The analysis of this algorithm relies on the use of a new bound on the sum of independent Bernoulli random variables, that is of interest in its own right. The first author was supported in part by a Walter and Elise Haas Career Development Award and by a grant from the Israeli Science Foundation. This work was done white the third author was at the Department of Applied Mathematics and Computer Science, The Weizmann Institute, Rehovot 76100, Israel.     

On Space Efficient Two Dimensional Range Minimum Data Structures

The two dimensional range minimum query problem is to preprocess a static m by n matrix (two dimensional array) A of size N=m⋅n, such that subsequent queries, asking for the position of the minimum element in a rectangular range within A, can be answered efficiently. We study the trade-off between the space and query time of the problem. We show that every algorithm enabled to access A during the query and using a data structure of size O(N/c) bits requires Ω(c) query time, for any c where 1≤c≤N. This lower bound holds for arrays of any dimension. In particular, for the one dimensional version of the problem, the lower bound is tight up to a constant factor. In two dimensions, we complement the lower bound with an indexing data structure of size O(N/c) bits which can be preprocessed in O(N) time to support O(clog ² c) query time. For c=O(1), this is the first O(1) query time algorithm using a data structure of optimal size O(N) bits. For the case where queries can not probe A, we give a data structure of size O(N⋅min {m,log n}) bits with O(1) query time, assuming m≤n. This leaves a gap to the space lower bound of Ω(Nlog m) bits for this version of the problem.     

Polynomial Time Introreducibility

Abstract. We introduce the polynomial time version, in short ≤ ^P _T -introreducibility, of the notion of introreducibility studied in Recursion Theory. We give a simpler proof of the known fact that a set is ≤ ^P _T -introreducible if and only if it is in P. Our proof generalizes to virtually all the computation bounded reducibilities ≤ _r , showing that a set is ≤ _r -introreducible if and only if it belongs to the minimum ≤ _r -degree. It also holds for most unbounded reducibilities like ≤ _m , ≤ _c , ≤ _d , ≤ _p , ≤ _tt , etc., but it does not hold for ≤ _T . A very strong way for a set L to fail being ≤ _r -introreducible is that L is not ≤ _r -reducible to any coinfinite subset of L . We call such sets ≤ _r -introimmune. It is known that ≤ _T -introimmune sets exist but they are not arithmetical. In this paper we ask for which reducibilities ≤ _r there exist arithmetical ≤ _r -introimmune sets. We show that they exist for the reducibilities ≤ _c and ≤ ^N _m . Finally, we prove separation results between introimmunities.     

Systolic networks for iterative methods for linear equations with cyclic reduction II

This paper presents systolic networks for the application of cyclic reduction to iterative methods for the solution of a linear system of equations A x=b where A is a p-cyclic matrix derived from multi-colouring ordered difference schemes on a regular mesh.     

A new quantum claw-finding algorithm for three functions

Fork functionsf ₁, ...f _k, ak-tuple (x ₁, ...x _k) such thatf ₁(x ₁)=...=f _k(x _k) is called a claw off ₁, ...,f _k. In this paper, we construct a new quantum claw-finding algorithm for three functions that is efficient when the numberM of intermediate solutions is small. The known quantum claw-finding algorithm for three functions requiresO(N ^7/8 logN) queries to find a claw, but our algorithm requiresO(N ^3/4 logN) queries ifM ≤ √N andO(N ^7/12 M ^1/3 logN) queries otherwise. Thus, our algorithm is more efficient ifM≤N ^7/8. Kazuo Iwama, Ph.D.: Professor of Informatics, Kyoto University, Kyoto 606-8501, Japan. Received BE, ME, and Ph.D. degrees in Electrical Engineering from Kyoto University in 1978, 1980 and 1985, respectively. His research interests include algorithms, complexity theory and quantum computation. Editorial board of Information Processing Letters and Parallel Computing. Council Member of European Association for Theoretical Computer Science (EATCS). Akinori Kawachi: Received B.Eng. and M.Info. from Kyoto University in 2000 and 2002, respectively. His research interests are quantum computation and distributed computation.     

An Explicit Formula for the L 2-Discrepancy of (n α)-Sequences

Assume that α is an irrational number with continued fraction expansion [a₀;a₁, . . .] and convergents ,n= 0, 1 . . . . Every positive integer N has a unique expansion N=b₀q₀+b₁q₁+ . . . +b_mq_m, where the digits b_i are nonnegative integers with b₀<a₁,b_i≤a_i+1 and such that b_i=a_i+1 implies b_i−1=0, the so-called Ostrowski expansion of N to base α. On the other hand let c_[0,x) be the characteristic function of the half-open interval [0,x) and let be the L₂-discrepancy of the sequence (nα) mod 1, where {y} denotes the fractional part of the real number y. In this paper, we give an explicit formula for D*⁽²⁾_N(α) entirely in terms of the digits b₀, . . . ,b_m. This formula enables one to compute the L₂-discrepancy in at most O(log⁴N) steps, where the O-constant does not depend on α, while in the classical formulae for the L₂-discrepancy N²/2 calculation steps are necessary. The fastest algorithm so far was found by S. Heinrich [3] and works (for all sequences) in O(N log N) steps. Dedicated to Prof. W. G. Nowak on the occasion of his 50th birthday.     

The panconnectivity and the pancycle-connectivity of the generalized base-<Emphasis Type="Italic">b</Emphasis> hypercube

The interconnection network considered in this paper is the generalized base-b hypercube that is an attractive variant of the well-known hypercube. The generalized base-b hypercube is superior to the hypercube in many criteria, such as diameter, connectivity, and fault diameter. In this paper, we study the panconnectivity and pancycle-connectivity of the generalized base-b hypercube. We show that a generalized base-b hypercube is panconnected for b≥3. That is, for each pair of distinct vertices x and y of the n-dimensional generalized base-b hypercube GH(b,n) and for any integer l, where Dist(x,y)≤l≤N−1, there exists a path of the length l joining x and y, where N is the order of the graph GH(b,n) and Dist(x,y) is the distance between x and y. We also show that a generalized base-b hypercube is pancycle-connected for b≥3. That is, every two distinct vertices x and y of the graph GH(b,n) are contained by a cycle of every length ranging from the length of the smallest cycle that contains x and y to N.     

Solving the generalized sylvester matrix equation Σ i=1p AiXBi + Σ j=1q CjYDj=E over reflexive and anti-reflexive matrices

A matrix P ∈ ℝ ^n×n is called a generalized reflection if P ^T = P and P ²=I. An n×n matrix A is said to be a reflexive (anti-reflexive) with respect to P if A PAP (A = −PAP). In the present paper, two iterative methods are derived for solving the generalized Sylvester matrix equation Σ _i=1 ^p A _i XB _i + Σ _j=1 ^q C _j YD _j =E (including the Sylvester and Lyapunov matrix equations as special cases) over reflexive and anti-reflexive matrices respectively. It is proven that the iterative methods, respectively, consistently converge to the reflexive and anti-reflexive solutions of the matrix equation for any initial reflexive and anti-reflexive matrices. Finally, a numerical example is given to demonstrate the effectiveness of the derived methods.     

Local noncuppability in R/M

Given any [c],[a],[d]∈R/M such that [d]≤[a]≤[c], [a] is locally noncuppable between [c] and [d] if [d]<[a]≤[c]and [a] ∨ [b] < [c] for any [b]∈R/M such that [d]≤ [ b ] < [ c ]. It will be shown that given any nonzero [ c ] ∈ R/M, there are [ a ], [ d ] ∈R/M such that [d]<[a]≤[c] and[a] is locally noncuppable between [c] and[d].     

Learning Matrix Functions over Rings

Let R be a commutative Artinian ring with identity and let X be a finite subset of R . We present an exact learning algorithm with a polynomial query complexity for the class of functions representable as f(x) = Π _i=1 ⁿ A _i (x _i ), where, for each 1 ≤ i ≤ n , A _i is a mapping A _i : X → R ^{mi× mi+1} and m ₁ = m _n+1 = 1 . We show that the above algorithm implies the following results: 1. Multivariate polynomials over a finite commutative ring with identity are learnable using equivalence and substitution queries. 2. Bounded degree multivariate polynomials over Z _n can be interpolated using substitution queries. 3. The class of constant depth circuits that consist of bounded fan-in MOD gates, where the modulus are prime powers of some fixed prime, is learnable using equivalence and substitution queries. Our approach uses a decision tree representation for the hypothesis class which takes advantage of linear dependencies. This paper generalizes the learning algorithm for automata over fields given in [BBB+]. Received January 28, 1997; revised May 29, 1997, June 18, 1997, and June 26, 1997.     

The Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems

In this paper we separate many-one reducibility from truth-table reducibility for distributional problems in DistNP under the hypothesis that P ≠ NP . As a first example we consider the 3-Satisfiability problem (3SAT) with two different distributions on 3CNF formulas. We show that 3SAT with a version of the standard distribution is truth-table reducible but not many-one reducible to 3SAT with a less redundant distribution unless P = NP . We extend this separation result and define a distributional complexity class C with the following properties: (1) C is a subclass of DistNP, this relation is proper unless P = NP. (2) C contains DistP, but it is not contained in AveP unless DistNP \subseteq AveZPP. (3) C has a ≤ ^p _m -complete set. (4) C has a ≤ ^p _tt -complete set that is not ≤ ^p _m -complete unless P = NP. This shows that under the assumption that P ≠ NP, the two completeness notions differ on some nontrivial subclass of DistNP.     

Resource scheduling with variable requirements over time

The problem of scheduling resources for tasks with variable requirements over time can be stated as follows. We are given two sequences of vectors A=A ₁,…,A _n and R=R ₁,…,R _m . Sequence A represents resource availability during n time intervals, where each vector A _i has q elements. Sequence R represents resource requirements of a task during m intervals, where each vector R _i has q elements. We wish to find the earliest time interval i, termed latency, such that for 1≤k≤m, 1≤j≤q: A _i+k−1 ^j ≥R _k ^j , where A _i+k−1 ^j and R _k ^j are the jth elements of vectors A _i+k−1 and R _k , respectively. One application of this problem is I/O scheduling for multimedia presentations. The fastest known algorithm to compute the optimal solution of this problem has computation time (Amir and Farach, in Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), San Francisco, CA, pp. 212–223, 1991; Inf. Comput. 118(1):1–11, 1995). We propose a technique that approximates the optimal solution in linear time: . We evaluated the performance of our algorithm when used for multimedia I/O scheduling. Our results show that 95% of the time, our solution is within 5% of the optimal.     

Pinwheel Scheduling: Achievable Densities

Abstract. A pinwheel schedule for a vector v= (v ₁ , v ₂ , . . ., v _n ) of positive integers 2 ≤ v ₁ ≤ v ₂ ≤ ⋅s ≤ v _n is an infinite symbol sequence {S _j : j ∈ Z } with each symbol drawn from [n] = {1,2, . . ., n } such that each i ∈ [n] occurs at least once in every v _i consecutive terms (S _j+1 , S _j+2 , . ., S _j+vi ) . The density of v is d(v) = 1/v ₁ + 1/v ₂ + ⋅s + 1/v _n . If v has a pinwheel schedule, it is schedulable . It is known that v(2,3,m) with m ≥ 6 and density d(v) = 5/6 + 1/m is unschedulable, and Chan and Chin [2] conjecture that every v with d(v) ≤ 5/6 is schedulable. They prove also that every v with d(v) ≤ 7/10 is schedulable. We show that every v with d(v) ≤ 3/4 is schedulable, and that every v with v ₁ =2 and d(v) ≤ 5/6 is schedulable. The paper also considers the m -pinwheel scheduling problem for v , where each i ∈ [n] is to occur at least m times in every mv _i consecutive terms (S _j+1 , . ., S _j+mvi ) , and shows that there are unschedulable vectors with d(v) =1- 1/[(m+1)(m+2)] + ɛ for any ɛ > 0 .     

Fast Dynamic Transitive Closure with Lookahead

In this paper we consider the problem of dynamic transitive closure with lookahead. We present a randomized one-sided error algorithm with updates and queries in O(n ^{ω(1,1,ε)−ε} ) time given a lookahead of n ^ε operations, where ω(1,1,ε) is the exponent of multiplication of n×n matrix by n×n ^ε matrix. For ε≤0.294 we obtain an algorithm with queries and updates in O(n ^2−ε ) time, whereas for ε=1 the time is O(n ^ω−1). This is essentially optimal as it implies an O(n ^ω ) algorithm for boolean matrix multiplication. We also consider the offline transitive closure in planar graphs. For this problem, we show an algorithm that requires O(n^\fracw2)O(n^{\frac{\omega}{2}}) time to process n^\frac12n^{\frac{1}{2}} operations. We also show a modification of these algorithms that gives faster amortized queries. Finally, we give faster algorithms for restricted type of updates, so called element updates. All of the presented algorithms are randomized with one-sided error. All our algorithms are based on dynamic algorithms with lookahead for matrix inverse, which are of independent interest.     

Extending the cooper minimal pair theorem

In the study of cappable and noncappable properties of the recursively enumerable(r.e.)degrees.Lempp suggested a conjecture which asserts that for all r.e.degrees and b,if a ≮b then there exists an r.e.degree c such that c≤a and c≮b and c is cappable.We shall prove in this paper that this conjecture holds under the condition that a is high.Working below a high r.e.degree h,we show that for any r.e.degree b with h≮b,there exist r.e.degrees a0 and a1 and such that a0,a1≮b,a0,a1≤h,and a0 and a1 from a minimal pair.     

On Constrained Facility Location Problems

Given m facilities each with an opening cost, n demands, and distance between every demand and facility, the Facility Location problem finds a solution which opens some facilities to connect every demand to an opened facility such that the total cost of the solution is minimized. The k-Facility Location problem further requires that the number of opened facilities is at most k, where k is a parameter given in the instance of the problem. We consider the Facility Location problems satisfying that for every demand the ratio of the longest distance to facilities and the shortest distance to facilities is at most ω, where ω is a predefined constant. Using the local search approach with scaling technique and error control technique, for any arbitrarily small constant > 0, we give a polynomial-time approximation algorithm for the ω-constrained Facility Location problem with approximation ratio 1 + ω + 1 + ε, which significantly improves the previous best known ratio (ω + 1)/α for some 1≤α≤2, and a polynomial-time approximation algorithm for the ω-constrained k- Facility Location problem with approximation ratio ω+1+ε. On the aspect of approximation hardness, we prove that unless NP■DTIME(nO(loglogn)), the ω-constrained Facility Location problem cannot be approximated within 1 + lnω - 1, which slightly improves the previous best known hardness result 1.243 + 0.316ln(ω - 1). The experimental results on the standard test instances of Facility Location problem show that our algorithm also has good performance in practice.