Catálogo de publicaciones - libros

This paper studies online job scheduling on multiprocessors and, in particular, investigates the algorithms SRPT and SJF for minimizing total stretch, where the stretch of a job is its flow time (response time) divided by its processing time. SRPT is perhaps the most well-studied algorithm for minimizing total flow time or stretch. This paper gives the first resource augmentation analysis of the total stretch of SRPT, showing that it is indeed (1)-speed 1-competitive. This paper also gives a simple lower bound result that SRPT is not -speed 1-competitive for any < 1.5.

This paper also makes contribution to the analysis of SJF. Extending the work of [4], we are able to show that SJF is (1)-speed 1-competitive for minimizing total stretch. More interestingly, we find that the competitiveness of SJF can be reduced arbitrarily by increasing the processor speed (precisely, SJF is ()-speed (1/)-competitive for any ≥ 1). We conjecture that SRPT also admits a similar result.

We propose a method to approximate a polygonal object by a deformable smooth surface, namely the -skin defined by Edelsbrunner for all 0< < 1. We guarantee that they are homeomorphic and their Hausdorff distance is at most >0. Such construction makes it possible for fully automatic, smooth and robust deformation between two polygonal objects with different topologies. En route to our results, we also give an approximation of a polygonal object with a union of balls.

We define a basis of solutions of a system of linear inequalities and present a general algorithm for finding such a basis. Our algorithm relies on an algorithm for finding a Hilbert basis for the set of nonnegative solutions of a system of linear inequalities and can be used in conjunction with any such algorithm.

Two mobile agents (robots) having distinct labels and located in nodes of an unknown anonymous connected graph, have to meet. We consider the asynchronous version of this well-studied rendezvous problem and we seek fast deterministic algorithms for it. Since in the asynchronous setting meeting at a node, which is normally required in rendezvous, is in general impossible, we relax the demand by allowing meeting of the agents inside an edge as well. The measure of performance of a rendezvous algorithm is its : for a given initial location of agents in a graph, this is the number of edge traversals of both agents until rendezvous is achieved. If agents are initially situated at a distance in an infinite line, we show a rendezvous algorithm with cost (||) when is known and (( + ||)) if is unknown, where || and || are the lengths of the shorter and longer label of the agents, respectively. These results still hold for the case of the ring of unknown size but then we also give an optimal algorithm of cost (||), if the size of the ring is known, and of cost (||), if it is unknown. For arbitrary graphs, we show that rendezvous is feasible if an upper bound on the size of the graph is known and we give an optimal algorithm of cost (||) if the topology of the graph and the initial positions are known to agents.

The of a set of positive integers is

Dim() = { | () < ∞ },

where

Zeta-dimension serves as a fractal dimension on ℤ that extends naturally and usefully to discrete lattices such as ℤ, where is a positive integer.

This paper reviews the origins of zeta-dimension (which date to the eighteenth and nineteenth centuries) and develops its basic theory, with particular attention to its relationship with algorithmic information theory. New results presented include a gale characterization of zeta-dimension and a theorem on the zeta-dimensions of pointwise sums and products of sets of positive integers.

We study online interval coloring problems with bandwidth. We are interested in some variants motivated by bin packing problems. Specifically we consider open-end coloring, cardinality constrained coloring, coloring with vector constraints and finally a combination of both the cardinality and the vector constraints. We construct competitive algorithms for each of the variants. Additionally, we present a lower bound of 24/7 for interval coloring with bandwidth, which holds for all the above models, and improves the current lower bound for the standard interval coloring with bandwidth.

Recently Glaßer et al. have shown that for many classes including PSPACE and NP it holds that all of its nontrivial many-one complete languages are autoreducible. This immediately raises the question of whether all many-one complete languages are Turing self-reducible for such classes .

This paper considers a simpler version of this question—whether all PSPACE-complete (NP-complete) languages are length-decreasing self-reducible. We show that if all PSPACE-complete languages are length-decreasing self-reducible then PSPACE = P and that if all NP-complete languages are length-decreasing self-reducible then NP = P.

The same type of result holds for many other natural complexity classes. In particular, we show that (1) not all NL-complete sets are logspace length-decreasing self-reducible, (2) unconditionally not all PSPACE-complete languages are logpsace length-decreasing self-reducible, and (3) unconditionally not all PSPACE-complete languages are polynomial-time length-decreasing self-reducible.

In this paper we propose a probabilistic analysis of the fully asynchronous behavior (i.e., two cells are never simultaneously updated, as in a continuous time process) of elementary finite cellular automata (i.e., {0,1} states, radius 1 and unidimensional) for which both states are quiescent (i.e., (0,0,0) ↦ 0 and (1,1,1) ↦ 1). It has been experimentally shown in previous works that introducing asynchronism in the global function of a cellular automaton may perturb its behavior, but as far as we know, only few theoretical work exist on the subject. The cellular automata we consider live on a ring of size and asynchronism is introduced as follows: at each time step one cell is selected uniformly at random and the transition rule is applied to this cell while the others remain unchanged. Among the sixty-four cellular automata belonging to the class we consider, we show that fifty-five other converge almost surely to a random fixed point while nine of them diverge on all non-trivial configurations. We show that the convergence time of these fifty-five automata can only take the following values: either 0, Θ( ln ), Θ(), Θ(), or Θ(2). Furthermore, the global behavior of each of these cellular automata can be guessed by simply reading its code.

In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex in the protein-protein interaction graph of another species with respect to (w.r.t.) orthologous proteins. Two problems are considered: the Exact-(, )-Matching problem and the Max-(, ) problem, where (resp. ) denotes in both problems the maximum number of orthologous proteins in (resp. ) of a protein in (resp. ). Following [FLV04], the Exact-(, )-Matching problem asks for an injective homomorphism of to w.r.t. orthologous proteins. The optimization version is called the Max-(, )-Matching problem and is concerned with finding an injective mapping of a graph to a graph w.r.t. orthologous proteins that matches as many edges of as possible. For both problems, the emphasis here is clearly on bounded degree graphs and extremal small values of parameters and .

We consider three types of locally constrained graph homomorphisms: bijective, injective and surjective. We show that the three orders imposed on graphs by existence of these three types of homomorphisms are partial orders. We extend the well-known connection between degree refinement matrices of graphs and locally bijective graph homomorphisms to locally injective and locally surjective homomorphisms by showing that the orders imposed on degree refinement matrices by our locally constrained graph homomorphisms are also partial orders. We provide several equivalent characterizations of degree (refinement) matrices, e.g. in terms of the dimension of the cycle space of a graph related to the matrix. As a consequence we can efficiently check whether a given matrix is a degree matrix of some graph and also compute the size of a smallest graph for which it is a degree matrix in polynomial time.