A5024529572- Optimization and Search Problems
- Complexity and Algorithms in Graphs
- Scheduling and Optimization Algorithms
- Distributed systems and fault tolerance
- Advanced Graph Theory Research
- Auction Theory and Applications
- Caching and Content Delivery
- Mobile Ad Hoc Networks
- Cooperative Communication and Network Coding
- Computational Geometry and Mesh Generation
- semigroups and automata theory
- Facility Location and Emergency Management
- Algorithms and Data Compression
- Digital Image Processing Techniques
- DNA and Biological Computing
- Advanced Bandit Algorithms Research
- Advanced Wireless Network Optimization
- Optimization and Packing Problems
- Parallel Computing and Optimization Techniques
- Opportunistic and Delay-Tolerant Networks
- Machine Learning and Algorithms
- Distributed and Parallel Computing Systems
- Advanced Manufacturing and Logistics Optimization
- Medical Image Segmentation Techniques
- Interconnection Networks and Systems
University of California, Riverside
2015-2024
University of California System
1989-2014
U.S. National Science Foundation
2010
Polish Academy of Sciences
1984-2006
University of Warsaw
1986-2005
Columbia University
1987-1988
University of Warmia and Mazury in Olsztyn
1986
In the k-server problem, one must choose how k mobile servers will serve each of a sequence requests, making decisions in an online manner. An optimal deterministic strategy is exhibited when requests fall on real line. For weighted-cache which cost moving to x from any other point $w( )$, weight x, algorithm also provided. The nonexistence competitive algorithms for asymmetric two-server problem and memoryless proved. A fast oflline computing schedule given, it shown that finding offline at...
The k-server problem is investigated when the metric space a tree. For this case an on-line k-competitive algorithm for k-servers presented. competitiveness ratio k optimal. memoryless, in sense that it does not use any information from past.
ABSTRACT One of the first steps in characterizing an ecosystem is to describe organisms inhabiting it. For microbial studies, experimental limitations have hindered ability depict diverse communities. Here we oligonucleotide fingerprinting rRNA genes (OFRG), a method that permits identification arrayed (rDNA) through series hybridization experiments using small DNA probes. To demonstrate this strategy, examined bacteria two different soils. Analysis 1,536 rDNA clones revealed 766 clusters...
We consider the problem of embedding vertices a plane graph into small (polynomial size) grid in such way that edges are straight, nonintersecting line segments and faces convex polygons. present linear-time algorithm which, given an n-vertex 3-connected G (with n ≥ 3), finds straight-line (n - 2) × grid.
We establish an O(n log/sup 2/n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches known lower of /spl Omega/(n log n). The fastest previously algorithm this problem works O(n/sup 3/2/). Using our algorithm, we develop 3/2/log/sup gossiping same network model.
Abstract We propose two efficient heuristics for minimizing the number of oligonucleotide probes needed analyzing populations ribosomal RNA gene (rDNA) clones by hybridization experiments on DNA microarrays. Such analyses have applications in study microbial communities. Unlike classical SBH (sequencing hybridization) procedure, where multiple are a chip, our we perform series experiments, each one consisting applying single probe to microarray containing large sample rDNA sequences from...
We consider the problem of packing rectangles height 1 when x-coordinates their left and right edges are specified.In off-line case optimal solution can be trivially found in polynomial time.In on-line no algorithm have performance ratio better than 3.A connection between this dynamic storage allocation is shown.Résumé.-On considère le problème de l'empilage hauteur lorsque les abscisses des côtés gauches et droits sont spécifiées.On vérifie aisément que dans cas «off-line» la optimale est...
We prove strong ${\mathbb {NP}}$ -completeness for the four variants of caching with multi-size pages. These are obtained by choosing either fault cost or bit model, and combining it a forced an optional policy. This resolves two questions in area paging that were open since 1990s.
Pros and cons of the competitive analysis have been discussed in literature by many authors. Continuing this discussion quarter s column, Reza Dorrigiv Alejandro Lopez-Ortiz review compare various performance measures for online algorithms, highlighting their differences with respect to ratio. Many thanks contributing article.
We study the problem of waking up a collection n processors connected by multihop ad hoc ratio network with unknown topology, no access to global clock, and collision detection mechanism available. Each node in either wakes spontaneously or gets activated receiving wake‐up signal from another node. All active nodes transmit signals according given protocol $\calW$. The running time $\calW$ is number steps counted first spontaneous until all become activated. provide two protocols for this...
In queue-based scheduling systems jobs are executed according to a predefined sequential plan. During exe- cution, faults may occur that cause re-execute, thus delaying the whole schedule. It is important determine (in real-time) whether given set of pre- ordered fault-tolerant, is, if all will al- ways meet their deadlines. This allows, for instance, decide online admit new urgent job into queue while still guaranteeing sched- ule remains fault-tolerant. Our goal in this work design...