We propose a new visualization of family relations, called family metro map, which is inspired by the famous London Underground Map. A family is represented by a metro line, where the parents are the end nodes and the children the intermediate nodes. We introduce family trees as rooted binary trees and consider the problem of automatically drawing a family metro map for a given family tree without crossing line segments, where the successive nodes of a metro line are placed at equal distances. The inter-node distance may be chosen to depend on the generation of the family, such that metro lines of earlier generations are shown more prominently than metro lines of later generations.

Despite, or exactly because of the wealth of video content available on the Web, it is often cumbersome to obtain access to exactly the content you like. It is an active process of filtering and making choices, often requiring searches through long lists of alternatives.

Given a set of objects and their pairwise distances, we wish to determine a visual representation of the data. We use the quartet paradigm to compute a hierarchy of clusters of the objects. The method is based on an NP-hard graph optimization problem called the Minimum Quartet Tree Cost problem. This paper presents and compares several heuristic approaches to approximate the optimal hierarchy. The performance of the algorithms is tested through extensive computational experiments and it is shown that the Reduced Variable Neighborhood Search heuristic is the most effective approach to the problem, obtaining high-quality solutions in short computational running times.

We consider the problem of determining the minimum number Nd of unit disks that is required to block all rays emanating from a point P in the two-dimensional space, where each disk has at least a distance d to point P and to any other disk. We study the asymptotic behavior of Nd, as d tends to infinity. By deriving upper bounds and lower bounds, we prove that pi2/16 ≤ lim_{d -> infinity} N_d/d2 ≤ 18/pi2, where the upper bound is based on establishing an interesting link between unit disks positioned on a regular triangular grid and Farey sequences from number theory. By positioning point P as well as the centers of the disks on the grid points of such a triangular grid, we create hexagonal rings of disks around P. We prove that we need exactly d-1 of these hexagons to block all rays emanating from P.

We consider the problem of orthogonally packing a given set of rectangular-shaped boxes into the minimum number of three-dimensional rectangular bins. The problem is NP-hard in the strong sense and extremely difficult to solve in practice. We characterize relevant subclasses of packing and present an algorithm which is able to solve moderately large instances to optimality. Extensive computational experiments compare the algorithm for the three-dimensional bin packing when solving general orthogonal packings and when restricted to robot packings.

Random redundant data storage strategies have proven to be a good choice for efficient data storage in multimedia servers. These strategies lead to a retrieval problem in which it is decided for each requested data block which disk to use for its retrieval. In this paper, we give a complexity classification of retrieval problems for random redundant storage.

We derive the guaranteed throughput of a multizone disk that repeatedly handles batches of n requests of constant size. Using this guaranteed throughput in the design of multimedia systems, one can admit more streams or get smaller buffer requirements and guaranteed response times than when an existing lower bound is used. We consider the case that nothing can be assumed about the location of the requests on the disk. Furthermore, we assume that successive batches are handled one after the other, where the n requests in a batch are retrieved using a SCAN-based sweep strategy. We show that we only have to consider two successive batches to determine the guaranteed throughput. Using this, we can compute the guaranteed throughput by determining a maximum-weighted path in a directed acyclic graph in O(z/sub max//sup 3/n/sup 2/) time, where z/sub max/ is the number of zones of the disk.

Saha, Mukherjee, and Tripathi (see ibid., vol.6, no.6, p.779-796, 1998) present and analyze an ATM cell scheduling algorithm called carry-over round robin. Unfortunately, one of the basic lemmas in their paper, related to the performance of this algorithm, does not hold. This adversely affects the delay and fairness properties that they subsequently derive. To substantiate this, we describe carry-over round robin and present a counterexample to the lemma. We end with some concluding remarks.

An approach is presented for storing video data in large disk arrays.Video data is stored by assigning a number of copies of each data block to different, randomly chosen disks, where the number of copies may depend on the popularity of the corresponding video data.The approach offers an interesting alternative to the well-known striping techniques.Its use results in smaller response times and lower disk and RAM costs if many continuous variablerate data streams have to be sustained simultaneously.It also offers some practical advantages relating to reliability and extendability.Based on this storage approach, three retrieval algorithms are presented that determine, for a given batch of data blocks, from which disk each of the data blocks should be retrieved.The performance of these algorithms is evaluated from an average-case as well as a worst-case perspective.key words: video serve< striping, disk array, RAID, multimedia, variable rate Pcnllissioll to 11wke dip,iMllnrd copies ofnll or pnr~ oflliis ~~a(erint ror personal or classroom use is granted without fre provided lhl the copi= me ~)ot made or distributed for profit or commrrcinl ad\~nnl~ge.the copyright notlc~, the title of he public;lIiot~ and its dnk nppenr.and notice is give11 ulnt copyright is by penllission 0~1hr ACM.IIIC.To copy ofllenvk to rcptd>lisll, lo post on servem or IO redislribtlle IO lists, reqrlirzs specific permission nnd/or fee.ACM h4ullimedin 97 ~%?C!ll/~ ~'f/nsll~/l~lW'l (I*$4

We consider the problem of nonpreemptively scheduling periodic tasks on a minimum number of identical processors, assuming that some slack is allowed in the time between successive executions of a periodic task. We prove that the problem is NP-hard in the strong sense. Necessary and sufficient conditions are derived for scheduling two periodic tasks on a single processor, and for combining two periodic tasks into one larger task. Based on these results, we propose an approximation algorithm.

We consider the problem of nonpreemptively scheduling periodic tasks on a minimum number of processors, assuming that the tasks have to be executed strictly periodically. We show that the problem is NP-complete in the strong sense, even in the case of a single processor, but that it is solvable in polynomial time if the periods and execution times are divisible. The latter condition generalizes the situation in which all periods and execution times are powers of 2. We also propose an approximation algorithm, which is based on successively assigning tasks to processors according to some priority rule.

We discuss the complexity of a number of high-level synthesis problems that can be viewed as generalizations of the classical retiming problem introduced by Leiserson and Saxe. The generalizations are concerned with additional degrees of freedom resulting from timefolding and multiplexing. The central problem is the design of multicycle and multifunctional processing units. This problem consists of two subproblems known as operator assignment and retiming. In this paper, we are primarily concerned with the construction of appropriate models and their complexity analysis. We show that both operator assignment and retiming are NP-hard in the presence of multiplexing or timefolding. We present a novel proof of the result obtained by Leiserson and Saxe, which states that retiming without multiplexing or timefolding can be solved in polynomial time.

This paper discusses improved force-directed scheduling and its application in the design of high-throughput DSP systems, such as real-time video VLSL circuits. We present a mathematical justification of the technique of force-directed scheduling, introduced by Paulin and Knight (1989), and we show how the algorithm can be used to find cost-effective time assignments and resource allocations, allowing trade-offs between processing units and memories. Furthermore, we present modifications that improve the effectiveness and the efficiency of the algorithm. The significance of the improvements is illustrated by an empirical performance analysis based on a number of problem instances.>

Force-directed scheduling is a technique which schedules operations under time constraints in order to achieve schedules with a minimum number of resources. The worst case time complexity of the algorithm is cubic in the number of operations. This is due to the computation of the changes in the distribution functions needed for the force calculations. An incremental way to compute the changes in the distribution functions, based on gradual time-frame reduction, is presented. This reduces the time complexity of the algorithm to quadratic in the number of operations, without any loss in effectiveness or generality of the algorithm. Implementations show a substantial CPU-time reduction of force-directed scheduling, which is illustrated by means of some industrially relevant examples.>

The authors discuss the problem of mapping algorithms for real-time processing of digital video signals onto a fixed configuration of identical programmable video signal processors. Due to the periodic nature of the algorithms and the small periods that are involved, successive executions of the algorithm have to be interleaved in time. The resulting scheduling problem is mathematically modeled and examined. The authors present a novel solution approach that is based on a divide-and-conquer strategy using phase assignment as the central part. This approach has been implemented and it gives good results for industrially significant video applications. Specifically, the proposed approach has been implemented in only 1300 lines of C and has been applied to a number of problem instances, whose signal flow graphs originate from industrially relevant algorithms, including contour enhancement and progressive scan, noise reduction, 4:3 to 16:9 screen format conversion, and a very elaborate progressive scan algorithm.>

The architecture and programming aspects of a programmable video signal processor are discussed.The processor is an integrated circuit that has a modular architecture with a number of programmable, pipelined processing elements.Networks of these processors can be programmed conveniently with the aid of dedicated programming tools.In this paper the emphasis is on the scheduling of video algorithms and the micro code generation for a network of video signal processors.Due to the periodic nature of the video algorithms and the small periods that are involved, successive executions of the video algorithm have to be interleaved in time.We present a novel solution approach to the scheduling problem using phase assignment as the central part.Results of this approach are presented for industrially significant video applications.