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.     

Synthesis of space optimal systolic arrays for band matrix-vector multiplication

In this paper, we consider the implementation of a product c=A b, where A is N ₁×N ₃ band matrix with bandwidth ω and b is a vector of size N ₃×1, on bidirectional and unidirectional linear systolic arrays (BLSA and ULSA, respectively). We distinguish the cases when the matrix bandwidth ω is 1≤ω≤N ₃ and N ₃≤ω≤N ₁+N ₃−1. A modification of the systolic array synthesis procedure based on data dependencies and space-time transformations of data dependency graph is proposed. The modification enables obtaining both BLSA and ULSA with an optimal number of processing elements (PEs) regardless of the matrix bandwidth. The execution time of the synthesized arrays has been minimized. We derive explicit formulas for the synthesis of these arrays. The performances of the designed arrays are discussed and compared to the performances of the arrays obtained by the standard design procedure.     

Weak Derandomization of Weak Algorithms: Explicit Versions of Yao��s Lemma

A simple averaging argument shows that given a randomized algorithm A and a function f such that for every input x, Pr[A(x) = f(x)] ≥ 1 − ρ (where the probability is over the coin tosses of A), there exists a non-uniform deterministic algorithm B “of roughly the same complexity” such that Pr[B(x) = f(x)] ≥ 1 − ρ (where the probability is over a uniformly chosen input x). This implication is often referred to as “the easy direction of Yao’s lemma” and can be thought of as “weak derandomization” in the sense that B is deterministic but only succeeds on most inputs. The implication follows as there exists a fixed value r′ for the random coins of A such that “hardwiring r′ into A” produces a deterministic algorithm B. However, this argument does not give a way to explicitly construct B.     

Impurity Heat Capacity and its Relation to Entanglement in Dilute Magnetic Alloys

Using an asymptotic solution of the thermodynamics of a dilute s-d system comprising M magnetic impurities interacting with the electron gas, the impurity energy and impurity heat capacity ΔC(T) are derived for dilute magnetic alloys with spin 1/2 and spin 3/2 impurities. ΔC(T) can be viewed as a measure of entanglement between impurities and electrons in a dilute magnetic alloy. The parameters which enter ΔC are adjusted to fit experimental data on impurity heat capacity of CuCr and (La_1-x Ce _x ) Al₂. Agreement is satisfactory for CuCr, at temperatures below 1K, and good for (La_1-x Ce _x ) Al₂. The magnitude of theoretical ΔC(T) agrees with experiment and does not require scaling as in previous s-d theories. Nonlinear dependence of ΔC(T) on impurity concentration has been accounted for the first time.     

Embedding of Cycles in Twisted Cubes with Edge-Pancyclic

In this paper, we study the embedding of cycles in twisted cubes. It has been proven in the literature that, for any integer l, 4≤l≤2 ⁿ , a cycle of length l can be embedded with dilation 1 in an n-dimensional twisted cube, n≥3. We obtain a stronger result of embedding of cycles with edge-pancyclic. We prove that, for any integer l, 4≤l≤2 ⁿ , and a given edge (x,y) in an n-dimensional twisted cube, n≥3, a cycle C of length l can be embedded with dilation 1 in the n-dimensional twisted cube such that (x,y) is in C in the twisted cube. Based on the proof of the edge-pancyclicity of twisted cubes, we further provide an O(llog l+n ²+nl) algorithm to find a cycle C of length l that contains (u,v) in TQ _n for any (u,v)∈E(TQ _n ) and any integer l with 4≤l≤2 ⁿ .     

Il metodo di Treffiz-Fichera per i semigruppi. potenziale di tipo potenza

A variation of the Trefftz-Fichera method is presented to compute lower bounds for the eigenvalues of a positive self-adjoint operator with discrete spectrum with grow at least in a logarithmic way as the index diverges. As suggested by Barnes et al. [2] to compute ground state, the semigroupe ^−βH, β>0, is used rather than the iterated resolvent(H+β) ⁻ⁿ,n=1,2,... As an example, the method is applied to the operatorH=−Δ+|x|^γ. inL ²(R), 1≤γ≤4.      

Exponential Stability of Slowly Time-Varying Nonlinear Systems

Let be a time-varying vector field depending on t containing a regular and a slow time scale (α large). Assume there exist a k (τ)≥1 and a γ(τ) such that ∥x _τ(t, t ₀, x ₀)∥≤k(τ) e ^{−γ(τ)(t−t0)}∥x ₀∥, with x _τ(t, t ₀, x ₀) the solution of the parametrized system with initial state x ₀ at t ₀. We show that for α sufficiently large is exponentially stable when “on average”γ(τ) is positive. The use of this result is illustrated by means of two examples. First, we extend the circle criterion. Second, exponential stability for a pendulum with a nonlinear slowly time-varying friction attaining positive and negative values is discussed. Date received: January 22, 2000. Date revised: April 14, 2001.     

On Centralized Smooth Scheduling

This paper studies evenly distributed sets of natural numbers and their applications to scheduling in a centralized environment. Such sets, called smooth sets, have the property that their quantity within each interval is proportional to the size of the interval, up to a bounded additive deviation; namely, for ρ,Δ∈ℝ a set A of natural numbers is (ρ,Δ)-smooth if abs(|I|⋅ρ−|I∩A|)<Δ for any interval I⊂ℕ.     

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.     

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.     

Panconnectivity of Cartesian product graphs

A graph G of order n (≥2) is said to be panconnected if for each pair (x,y) of vertices of G there exists an xy-path of length ℓ for each ℓ such that d _G (x,y)≤ℓ≤n−1, where d _G (x,y) denotes the length of a shortest xy-path in G. In this paper, we consider the panconnectivity of Cartesian product graphs. As a consequence of our results, we prove that the n-dimensional generalized hypercube Q _n (k ₁,k ₂,…,k _n ) is panconnected if and only if k _i ≥3 (i=1,…,n), which generalizes a result of Hsieh et al. that the 3-ary n-cube Q³_nQ^{3}_{n} is panconnected.     

An analytic approach to the problem of separability of quantum states based upon the theory of cones

Exploiting the cone structure of the set of unnormalized mixed quantum states, we offer an approach to detect separability independently of the dimensions of the subsystems. We show that any mixed quantum state can be decomposed as ρ = (1−λ)C _ρ  + λE _ρ , where C _ρ is a separable matrix whose rank equals that of ρ and the rank of E _ρ is strictly lower than that of ρ. With the simple choice C_r=M₁?M₂{C_{\rho}=M_{1}\otimes M_{2}} we have a necessary condition of separability in terms of λ, which is also sufficient if the rank of E _ρ equals 1. We give a first extension of this result to detect genuine entanglement in multipartite states and show a natural connection between the multipartite separability problem and the classification of pure states under stochastic local operations and classical communication. We argue that this approach is not exhausted with the first simple choices included herein.     

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.     

Approximation Algorithms for Bounded Degree Phylogenetic Roots

The Degree- Δ Closest Phylogenetic k th Root Problem (ΔCPR _k ) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E ⊕{{u,v} : u,v are leaves of T and d _T (u,v)≤k}|, is minimized, where d _T (u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for Δ CPR ₂ for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR ₃, and a polynomial-time approximation scheme for the maximization version of Δ CPR _k for any fixed Δ and k.     

Injective Colorings of Graphs with Low Average Degree

Let mad (G) denote the maximum average degree (over all subgraphs) of G and let χ _i (G) denote the injective chromatic number of G. We prove that if Δ≥4 and mad(G) < \frac145\mathrm{mad}(G)<\frac{14}{5}, then χ _i (G)≤Δ+2. When Δ=3, we show that mad(G) < \frac3613\mathrm{mad}(G)<\frac{36}{13} implies χ _i (G)≤5. In contrast, we give a graph G with Δ=3, mad(G)=\frac3613\mathrm{mad}(G)=\frac{36}{13}, and χ _i (G)=6.     

On the rate of convergence of 2-term recursions in ℝ d

LetG be a compact set in ℝ ^d d≥1,M=G×G andϕ:M →G a map inC ₃(M). Suppose thatϕ has a fixed pointξ, i.e.ϕ(ξ, ξ)=ξ. We investigate the rate of convergence of the iterationx ⁿ⁺²=φ(x ⁿ⁺¹,x ⁿ) withx ⁰,x ¹∈G andx ⁿ→ξ. Iff _n=Q‖x ⁿ−ξ‖ with a suitable norm and a constantQ depending onξ, an exact representation forf _n is derived. The error terms satisfyf _2m+1≍(ƒ_2m)^γ,f _2m+2≍(ƒ_2m+1)^2γ,m≥0, with 1<gg<2, andγ=γ(x ¹,x ⁰). According to our main result we have lim_n→∞{‖x ⁿ⁺²‖/(‖x ⁿ‖)²}=Q, 0<Q<∞. This paper constitutes an extension of a part of the author’s doctoral thesis realized under the direction of Prof. E. Wirsing and Prof. A. Peyerimhoff, University of Ulm (Germany).     

On the complexity of binary samples

Consider a class of binary functions h: X→{ − 1, + 1} on an interval . Define the sample width of h on a finite subset (a sample) S ⊂ X as ω _S (h) =  min _x ∈ S |ω _h (x)| where ω _h (x) = h(x) max {a ≥ 0: h(z) = h(x), x − a ≤ z ≤ x + a}. Let be the space of all samples in X of cardinality ℓ and consider sets of wide samples, i.e., hypersets which are defined as Through an application of the Sauer-Shelah result on the density of sets an upper estimate is obtained on the growth function (or trace) of the class , β > 0, i.e., on the number of possible dichotomies obtained by intersecting all hypersets with a fixed collection of samples of cardinality m. The estimate is .      

Fault-Tolerant Embedding of Pairwise Independent Hamiltonian Paths on a Faulty Hypercube with Edge Faults

A Hamiltonian path in G is a path which contains every vertex of G exactly once. Two Hamiltonian paths P ₁=〈u ₁,u ₂,…,u _n 〉 and P ₂=〈v ₁,v ₂,…,v _n 〉 of G are said to be independent if u ₁=v ₁, u _n =v _n , and u _i ≠v _i for all 1<i<n; and both are full-independent if u _i ≠v _i for all 1≤i≤n. Moreover, P ₁ and P ₂ are independent starting at u ₁, if u ₁=v ₁ and u _i ≠v _i for all 1<i≤n. A set of Hamiltonian paths {P ₁,P ₂,…,P _k } of G are pairwise independent (respectively, pairwise full-independent, pairwise independent starting at u ₁) if any two different Hamiltonian paths in the set are independent (respectively, full-independent, independent starting at u ₁). A bipartite graph G is Hamiltonian-laceable if there exists a Hamiltonian path between any two vertices from different partite sets. It is well known that an n-dimensional hypercube Q _n is bipartite with two partite sets of equal size. Let F be the set of faulty edges of Q _n . In this paper, we show the following results:

A Decision Procedure for Linear “Big O” Equations

Let F be the set of functions from an infinite set, S, to an ordered ring, R. For f, g, and h in F, the assertion f = g + O(h) means that for some constant C, |f(x) − g(x)| ≤C |h(x)| for every x in S. Let L be the first-order language with variables ranging over such functions, symbols for 0, +, −, min , max , and absolute value, and a ternary relation f = g + O(h). We show that the set of quantifier-free formulas in this language that are valid in the intended class of interpretations is decidable and does not depend on the underlying set, S, or the ordered ring, R. If R is a subfield of the real numbers, we can add a constant 1 function, as well as multiplication by constants from any computable subfield. We obtain further decidability results for certain situations in which one adds symbols denoting the elements of a fixed sequence of functions of strictly increasing rates of growth.     

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.