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.     

Lattice constants matricial equations for conversion matrices

In this paper we proof a theorem concerning lattice constants and hence three matricial equations for conversion matricesR: if H=Δ^RT we have: i)H ³ =I; ii) H^T Σ H= Σ; iii)(DH) ² =I; where Δ,D, and ε are known when we can enumerate all non-isomorphic graphs withn vertices, we know (for Δ and ε) their edge-number and (for ε) the order of their automorphism group.     

Smooth Scheduling under Variable Rates or the Analog-Digital Confinement Game

This work considers non-terminating scheduling problems in which a system of multiple resources serves clients having variable needs. The system has m identical resources and n clients; in each time slot each resource may serve at most one client; in each such slot t each client γ has a rate, a real number ρ _γ (t), that specifies his needs in this slot. The rates satisfy the restriction ∑ _γ ρ _γ (t)≤m for any slot t. Except of this restriction, the rates can vary in arbitrary fashion. (This contrasts most prior works in this area in which the rates of the clients are constant.) The schedule is required to be smooth as follows: a schedule is Δ -smooth if for all time intervals I the absolute difference between the amount of service received by each client γ to his nominal needs of ∑ _t∈I ρ _γ (t) is less than Δ. Our objective are online schedulers that produce Δ-smooth schedules where Δ is a small constant which is independent of m and n. Our paper constructs such schedulers; these are the first online Δ-smooth schedulers, with a constant Δ, for clients with arbitrarily variable rates in a single or multiple resource system. Furthermore, the paper also considers a non-concurrent environment in which there is an additional restriction that each client is served at most once in each time slot; it presents the first online smooth schedulers for variable rates under this restriction. The above non-concurrent restriction is crucial in some applications (e.g., CPU scheduling). It has been pointed out that this restriction “adds a surprising amount of difficulty” to the scheduling problem. However, this observation was never formalized and, of course, was never proved. Our paper formalizes and proves some aspects of this observation. Another contribution of this paper is the introduction of a complete information, two player game called the analog-digital confinement game. In such a game pebbles are located on the real line; the two players, the analog player and the digital player, take alternating turns and each one, in his turn, moves some of the pebbles; the digital player moves the pebbles backwards by discrete distances while the analog player moves the pebbles forward by analog distances; the aim of the analog player is to cause one pebble (or more) to escape a pre-defined real interval while the aim of the digital player is to confine the pebbles into the interval. We demonstrate that this game is a convenient framework to study the general question of how to approximate an analog process by a digital one. All the above scheduling results are established via this game. In this derivation, the pebbles represent the clients, the analog player generates the needs of the clients and the digital player generates the schedule. Dedicated to the memory of Professor Shimon Even for his inspiration and encouragement     

Measures on MV-algebras

 We study sequentially continuous measures on semisimple M V-algebras. Let A be a semisimple M V-algebra and let I be the interval [0,1] carrying the usual Łukasiewicz M V-algebra structure and the natural sequential convergence. Each separating set H of M V-algebra homomorphisms of A into I induces on A an initial sequential convergence. Semisimple M V-algebras carrying an initial sequential convergence induced by a separating set of M V-algebra homomorphisms into I are called I-sequential and, together with sequentially continuous M V-algebra homomorphisms, they form a category SM(I). We describe its epireflective subcategory ASM(I) consisting of absolutely sequentially closed objects and we prove that the epireflection sends A into its distinguished σ-completion σ _H (A). The epireflection is the maximal object in SM(I) which contains A as a dense subobject and over which all sequentially continuous measures can be continuously extended. We discuss some properties of σ _H (A) depending on the choice of H. We show that the coproducts in the category of D-posets [9] of suitable families of I-sequential M V-algebras yield a natural model of probability spaces having a quantum nature. The motivation comes from probability: H plays the role of elementary events, the embedding of A into σ _H (A) generalizes the embedding of a field of events A into the generated σ-field σ(A), and it can be viewed as a fuzzyfication of the corresponding results for Boolean algebras in [8, 11, 14]. Sequentially continuous homomorphisms are dual to generalized measurable maps between the underlying sets of suitable bold algebras [13] and, unlike in the Loomis–Sikorski Theorem, objects in ASM(I) correspond to the generated tribes (no quotient is needed, no information about the elementary events is lost). Finally, D-poset coproducts lift fuzzy events, random functions and probability measures to events, random functions and probability measures of a quantum nature. Supported by VEGA Grant 2/7193/01     

Equivalence Problems for Circuits over Sets of Natural Numbers

We investigate the complexity of equivalence problems for {∪,∩,⁻,+,×}-circuits computing sets of natural numbers. These problems were first introduced by Stockmeyer and Meyer (1973). We continue this line of research and give a systematic characterization of the complexity of equivalence problems over sets of natural numbers. Our work shows that equivalence problems capture a wide range of complexity classes like NL, C ₌ L, P,Π₂^P, PSPACE, NEXP, and beyond. McKenzie and Wagner (2003) studied related membership problems for circuits over sets of natural numbers. Our results also have consequences for these membership problems: We provide an improved upper bound for the case of {∪,∩,⁻,+,×}-circuits.     

Regularity of Interval Matrices and Theorems of the Alternatives

We give several characterizations of regularity of interval matrices. All of them have to do with solvability of certain systems of nonlinear equations or inequalities. The most illustrative of them is the following one: an interval matrix [A_c − Δ, A_c + Δ] is regular if and only if the nonlinear inequality has a solution in each orthant. These results are then applied to derive two theorems of the alternatives for inequalities with absolute values. Dedicated to Professor Miroslav Fiedler on the occasion of his 80th birthday     

A Better Constant-Factor Approximation for Selected-Internal Steiner Minimum Tree

The selected-internal Steiner minimum tree problem is a generalization of original Steiner minimum tree problem. Given a weighted complete graph G=(V,E) with weight function c, and two subsets R ^′ ⊊ R⊆V with |R−R ^′|≥2, selected-internal Steiner minimum tree problem is to find a minimum subtree T of G interconnecting R such that any leaf of T does not belong to R ^′. In this paper, suppose c is metric, we obtain a (1+ρ)-approximation algorithm for this problem, where ρ is the best-known approximation ratio for the Steiner minimum tree problem.     

Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models

For an unweighted undirected graph G = (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G′ = (V,H), H ⊂eqE, is called an (α,β)-spanner of G if for every pair of vertices u,v ∊ V, dist_G′(u,v) ≤ α ⋅ dist_G(u,v) + β. It was shown in [21] that for any ∊ > 0, κ = 1,2,…, there exists an integer β = β(∊,κ) such that for every n-vertex graph G there exists a (1+∊,β)-spanner G′ with O(n^1+1/κ) edges. An efficient distributed protocol for constructing (1+∊,β)-spanners was devised in [19]. The running time and the communication complexity of that protocol are O(n^1+ρ) and O(|E|n^ρ), respectively, where ρ is an additional control parameter of the protocol that affects only the additive term β. In this paper we devise a protocol with a drastically improved running time (O(n^ρ) as opposed to O(n^1+ρ)) for constructing (1+∊,β)-spanners. Our protocol has the same communication complexity as the protocol of [19], and it constructs spanners with essentially the same properties as the spanners that are constructed by the protocol of [19]. The protocol can be easily extended to a parallel implementation which runs in O(log n + (|E|⋅ n^ρlog n)/p) time using p processors in the EREW PRAM model. In particular, when the number of processors, p, is at least |E|⋅ n^ρ, the running time of the algorithm is O(log n). We also show that our protocol for constructing (1+∊,β)-spanners can be adapted to the streaming model, and devise a streaming algorithm that uses a constant number of passes and O(n^1+1/κ⋅ {log} n) bits of space for computing all-pairs-almost-shortest-paths of length at most by a multiplicative factor (1+∊) and an additive term of β greater than the shortest paths. Our algorithm processes each edge in time O(n^ρ), for an arbitrarily small ρ > 0. The only previously known algorithm for the problem [23] constructs paths of length κ times greater than the shortest paths, has the same space requirements as our algorithm, but requires O(n^1+1/κ) time for processing each edge of the input graph. However, the algorithm of [23] uses just one pass over the input, as opposed to the constant number of passes in our algorithm. We also show that any streaming algorithm for o(n)-approximate distance computation requires Ω(n) bits of space. This work was Supported by the DoD University Research Initiative (URI) administered by the Office of Naval Research under Grant N00014-01-1-0795. Michael Elkin was supported by ONR grant N00014-01-1-0795. Jian Zhang was supported by ONR grant N00014-01-1-0795 and NSF grants CCR-0105337 and ITR-0331548. Preliminary version of this paper was published in PODC’04, see [22]. After the preliminary version of our paper [22] appeared on PODC’04, Feigenbaum et al. [24] came up with a new streaming algorithm for the problem that is far more efficient than [23] in terms of time-per-edge processing. However, our algorithm is still the only existing streaming algorithm that provides an almost additive approximation of distances.     

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.     

Solving Systems of Difference Constraints Incrementally

Difference constraints systems consisting of inequalities of the form x _i - x _j b _i,j occur in many applications, most notably those involving temporal reasoning. Often, it is necessary to maintain a solution to such a system as constraints are added, modified, and deleted. Existing algorithms handle modifications by solving the resulting system anew each time, which is inefficient. The best known algorithm to determine if a system of difference constraints is feasible (i.e., if it has a solution) and to compute a solution runs in Θ (mn) time, where n is the number of variables and m is the number of constraints. This paper presents a new efficient incremental algorithm for maintaining a solution to a system of difference constraints. As constraints are added, modified, or deleted, the algorithm determines if the new system is feasible and updates its solution. When the system becomes infeasible, the algorithm continues to process changes until it becomes feasible again, at which point a feasible solution will be produced. The algorithm processes the addition of a constraint in time O(m + n log n) and the removal of a constraint in constant time when the original system is feasible. More precisely, additions are processed in time O( || Δ || + |Δ| log|Δ| ) , where |Δ| is the number of variables whose values are changed to compute the new feasible solution, and || Δ || is the number of constraints involving the variables whose values are changed. When the original system is infeasible, the algorithm processes any change in O(m + n log n) amortized time. The new algorithm can also be used to check for the existence of negative cycles in dynamic graphs. Received September 25, 1997; revised November 16, 1997.     

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.     

Processing fuzzy set membership functionals as vectors

A framework is presented for processing fuzzy sets for which the universe of discourse X = {x} is a separable Hilbert Space, which, in particular, may be a Euclidian Space. In a given application, X would constitute a feature space. The membership functions of sets in such X are then “membership functionals”, that is, mappings from a vector space to the real line. This paper considers the class Φ of fuzzy sets A, the membership functionals μ _A of which belong to a Reproducing Kernel Hilbert Space (RKHS) F(X) of bounded analytic functionals on X, and satisfy the constraint . These functionals can be expanded in abstract power series in x, commonly known as Volterra functional series in x. Because of the one-to-one relationship between the fuzzy sets A and their respective μ _A , one can process the sets A as objects using their μ _A as intermediaries. Thus the structure of the uncertainty present in the fuzzy sets can be processed in a vector space without descending to the level of processing of vectors in the feature space as usually done in the literature in the field. Also, the framework allows one to integrate human and machine judgments in the definition of fuzzy sets; and to use concepts analogous to probabilistic concepts in assigning membership values to combinations of fuzzy sets. Some analytical and interpretive consequences of this approach are presented and discussed. A result of particular interest is the best approximation of a membership functional μ _A in F(X) based on interpolation on a training set {(v ⁱ , u ⁱ ),i = 1, . . . , q} and under the positivity constraint. The optimal analytical solution comes out in the form of an Optimal Interpolative Neural Network (OINN) proposed by the author in 1990 for best approximation of pattern classification systems in a F(X) space setting. An example is briefly described of an application of this approach to the diagnosis of Alzheimer’s disease.     

On a reduction of the interval coloring problem to a series of bandwidth coloring problems

Given a graph G=(V,E) with strictly positive integer weights ω _i on the vertices i∈V, an interval coloring of G is a function I that assigns an interval I(i) of ω _i consecutive integers (called colors) to each vertex i∈V so that I(i)∩I(j)=∅ for all edges {i,j}∈E. The interval coloring problem is to determine an interval coloring that uses as few colors as possible. Assuming that a strictly positive integer weight δ _ij is associated with each edge {i,j}∈E, a bandwidth coloring of G is a function c that assigns an integer (called a color) to each vertex i∈V so that |c(i)−c(j)|≥δ _ij for all edges {i,j}∈E. The bandwidth coloring problem is to determine a bandwidth coloring with minimum difference between the largest and the smallest colors used. We prove that an optimal solution of the interval coloring problem can be obtained by solving a series of bandwidth coloring problems. Computational experiments demonstrate that such a reduction can help to solve larger instances or to obtain better upper bounds on the optimal solution value of the interval coloring problem.     

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.      

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:

Incidence structures and Stone–Priestley duality

We observe that if R: = (I,ρ, J) is an incidence structure, viewed as a matrix, then the topological closure of the set of columns is the Stone space of the Boolean algebra generated by the rows. As a consequence, we obtain that the topological closure of the collection of principal initial segments of a poset P is the Stone space of the Boolean algebra Tailalg (P) generated by the collection of principal final segments of P, the so-called tail-algebra of P. Similar results concerning Priestley spaces and distributive lattices are given. A generalization to incidence structures valued by abstract algebras is considered.      

Improved Approximate String Matching Using Compressed Suffix Data Structures

Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper we present a space efficient data structure to solve the 1-mismatch and 1-difference problems. Given a text T of length n over an alphabet A, we can preprocess T and give an -bit space data structure so that, for any query pattern P of length m, we can find all 1-mismatch (or 1-difference) occurrences of P in O(|A|mlog log n+occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(nlog ² n) bits. The space of our data structure can be further reduced to O(nlog |A|) with the query time increasing by a factor of log  ^ε n, for 0<ε≤1. Furthermore, our solution can be generalized to solve the k-mismatch (and the k-difference) problem in O(|A| ^k m ^k (k+log log n)+occ) and O(log  ^ε n(|A| ^k m ^k (k+log log n)+occ)) time using an -bit and an O(nlog |A|)-bit indexing data structures, respectively. We assume that the alphabet size |A| is bounded by for the -bit space data structure.     

A Faster Algorithm for Computing the Principal Sequence of Partitions of a Graph

We consider the following problem: given an undirected weighted graph G=(V,E,c) with nonnegative weights, minimize function c(δ(Π))−λ|Π| for all values of parameter λ. Here Π is a partition of the set of nodes, the first term is the cost of edges whose endpoints belong to different components of the partition, and |Π| is the number of components. The current best known algorithm for this problem has complexity O(|V|²) maximum flow computations. We improve it to |V| parametric maximum flow computations. We observe that the complexity can be improved further for families of graphs which admit a good separator, e.g. for planar graphs.     

Sufficient condition for asymptotic stability of discrete interval systems

A counter-example is given to a recent result on the stability analysis of interval matrices by Jiang (1988). A sufficient condition is then presented for the asymptotic stability of the discrete-time interval system X(k + 1) = A _I X(k), by testing the norms of extreme matrices of the interval matrix A _I such that they are all less than one.     

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.