The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of length within a factor of (1 + c) of optimal in the non-preemptive model.
Given a collection of sets of cardinality at most k, with weights for each set, the maximum weighted packing problem is that of finding a collection of disjoint sets of maximum total weight. We study the worst case behavior of the t-local search heuristic for this problem proving a tight bound of k - 1+ 1/t. This continues the work of Hurkens and Schrijver for unweighted packing problems.
We consider the problem of scheduling a sequence of jobs to m parallel machines as to maximize the minimum load over the machines. This situation corresponds to a case that a system which consists of the m machines is alive (i.e. productive) only when all the machines are alive, and the system should be maintained alive as long as possible. It is well known that any on-line deterministic algorithm...
In this paper, we present algorithms to produce orthogonal drawings of arbitrary graphs. As opposed to most known algorithms, we do not restrict ourselves to graphs with maximum degree 4. The best previous result gave an $$(m - 1) \times \left( {\tfrac{m}{2} + 1} \right)$$ -grid for graphs with n nodes and m edges. We present algorithms for two scenarios. In the static scenario, the graph...
Given a nested radical α involving only dth roots we show how to compute an optimal or near optimal depth denesting of α by a nested radical that only involves Dth roots, where D is an arbitrary multiple of d. As a special case the algorithm computes denestings as in
Given a graph G = (V, E) and two vertices s, t ∈ V, s ≠ t, the Menger problem is to find a maximum number of disjoint paths connecting s and t. Depending on whether the input graph is directed or not, and what kind of disjointness criterion is demanded, this general formulation is specialized to the directed or undirected vertex, and the edge or arc disjoint Menger problem, respectively. For...
In this note we show that, for each chordal graph G, there is a tree T such that T is a spanning tree of the square G2 of G and, for every two vertices, the distance between them in T is not larger than the distance in G plus two. Moreover, we prove that, if G is a strongly chordal graph or even a dually chordal graph, then there exists a spanning tree T of G which is an additive 3-spanner...
In this paper we investigate techniques for decomposing the matrix of coefficients of a family of integer programs. From a more practical point of view, these techniques are useful to design a primal algorithm that solves the integer program via generating sets. In this con text our approach is applied to the Frobenius problem and to integer programming instances that seem to be difficult for LP-based...
Given a connected graph G, let a ΔT-spanning tree of G be a spanning tree of G of maximum degree bounded by ΔT. It is well known that for each ΔT ≥ 2 the problem of deciding whether a connected graph has a ΔT-spanning tree is NP-complete. In this paper we investigate this problem when additionally connectivity and maximum degree of the graph are given. A...
We consider broadcasting among n processors, f of which can be faulty. A fault-free processor, called the source, holds a piece of information which has to be transmitted to all other fault-free processors. We assume that the fraction f /n of faulty processors is bounded by a constant ,γ < 1. Transmissions are fault free. Faults are assumed of crash, type: faulty processors do not send or receive...
We prove separator theorems in which the size of the separator is minimized with respect to non-negative vertex costs. We show that for any planar graph G there exists a vertex separator of total sum of vertex costs at most $$c\sqrt {\Sigma _{v \in V(G)} (cost(v))^2 }$$ and that this bound is optimal to within a constant factor. Moreover such a separator can be found in linear time. This theorem...
The d-dimensional orthogonal knapsack problem (OKP) has a wide range of practical applications, including packing, cutting, and scheduling. We present a new approach to this problem, using a graph theoretical characterization of feasible packings. This characterization allows us to deal with classes of packings that share a certain combinatorical structure, instead of single ones. Combining the use...
We present a data structure problem which describes the requirements of a simple variant of fully dynamic walk-through animation: We assume the scene to consist of unit size balls in ℝ2 or higher dimensions. The scene may be arbitrarily large and has to be stored in secondary memory (discs) with relatively slow access. We allow a visitor to walk in the scene, and a modeler to update the scene by insertions...
The rectilinear Steiner tree problem asks for a shortest tree connecting given points in the plane with rectilinear distance. The best theoretically analyzed algorithm for this problem with a fairly practical behaviour bases on dynamic programming and has a running time of O(n2·.2.62n) (Ganley/Cohoon). The best implementation can solve random problems of size 35 (Salowe/Warme) within a...
We consider graphs whose vertices may be in one of two different states: either on or off. We wish to maintain dynamically such graphs under an intermixed sequence of updates and queries. An update may reverse the status of a vertex, by switching it either on or off, and may insert a new edge or delete an existing edge. A query tests properties of the subgraph induced by the vertices that are on....
Sequential lists are a frequently used data structure for implementing dictionaries. Recently, self-organizing sequential lists have been proposed for “engines” in efficient data compression algorithms. In this paper, we investigate the problem of list accessing from the perspective of competitive analysis. We establish a connection between randomized list accessing algorithms and Markov chains, and...
We present a new technique, which we refer to as implicit updates, based on which we obtain: (a) an algorithm for the on-line construction of the Lsuffix tree of an n x n matrix A — this data structure, described in [13], is the two-dimensional analog of the suffix tree of a string; (b) simple algorithms implementing primitive operations for LZ1-type on-dine lossless image compression methods. Those...
We address the problem of scheduling a multiclass queueing network on M parallel servers to minimize time-average linear holding costs. We analyze a heuristic priority-index rule, based on Klimov's solution to the single-server model: Compute the indices given by Klimov's adaptive greedy algorithm and, when a server becomes free, select a customer with largest index. We present closed-form performance...
We study the problem of combinatorial search for graphs under the additive model. The main result concerns the reconstruction of bounded degree graphs, i.e. graphs with the degree of all vertices bounded by a constant d. We show that such graphs can be reconstructed in O(dn) non-adaptive queries, that matches the information-theoretic lower bound. The proof is based on the technique of separating...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.