1,720,964 research outputs found
A VLSI IMPLEMENTATION OF THE SIMPLEX ALGORITHM
No full textThe use of a special-purpose VLSI chip for solving a linear programming problem is presented. The chip is structured as a mesh of trees and is designed to implemented the well-known simplex algorithm. A high degree of parallelism is introduced in each pivot step, which can be carried out in O(log n) time using an m multiplied by m mesh of trees having an O(mn log m log**3 n) area where m-1 and n-1 are the number of constraints and variables, respectively. Two variants of the simplex algorithm are also considered: the two-phase method and the revised one. The proposed chip is intended as a possible basic block for a VLSI operations research machine
A POLYNOMIAL FEASIBILITY TEST FOR PREEMPTIVE PERIODIC SCHEDULING OF UNRELATED PROCESSORS
No full textWe consider the problem of preemptive scheduling a set of periodically occurring jobs on a set of unrelated processors, that is, processors having different speeds for different jobs. We assume that each occurrence of a job has to be completely processed before the next occurrence of the same job. We provide a system of linear inequalities for testing the existence of a feasible schedule which can be solved in polynomial time. We then use the solution to this linear system, if any, for constructing a feasible schedule in a straightforward way
CODE ASSIGNMENT FOR HIDDEN TERMINAL INTERFERENCE AVOIDANCE IN MULTIHOP PACKET RADIO NETWORKS
No full textHidden terminal interference is caused by the (quasi-) simultaneous transmission of two stations that cannot hear each other, but are both received by the same destination station. This interference lowers the system throughput and increases the average packet delay. Some random access protocols that reduce this interference have been proposed, e.g., BTMA protocol. However, the hidden terminal interference can be totally avoided only by means of code division multiple access (CDMA) schemes. In this paper, we investigate the problem of assigning orthogonal codes to stations so as to eliminate the hidden terminal interference. Since the codes share the fixed channel capacity allocated to the network in the design stage, their number must not exceed a given bound. In this paper, we seek for assignments that minimize the number of codes used. We show that this problem is NP-complete, and thus computationally intractable, even for very restricted but very realistic network topologies. Then, we present optimal algorithms for further restricted topologies, as well as fast suboptimal centralized and distributed heuristic algorithms. The results of extensive simulation set up to derive the average performance of the proposed heuristics on realistic network topologies are presented
A GRACEFULLY DEGRADABLE VLSI SYSTEM FOR LINEAR-PROGRAMMING
No full textThe use of a fault-tolerant VLSI system for storing and solving linear-programming problems is presented. The system can bear multiple faults in processing elements and/or links and still function with an acceptable performance degradation. It is based on an interconnection pattern consisting of a complete binary tree in which spare links between cousin nodes are added so as to reconfigure it as a ternary tree. At any given time of a computation, faulty processing elements and/or links are circumvented by using such spare links. It is shown that the total silicon area required by this structure is only a constant factor higher than that of a complete binary tree. The result is used to give an efficient implementation of the simplex algorithm in which the time required to perform a single pivot step matches a previously established lower bound for tree machines in spite of faults
HAMILTONIAN CIRCUITS IN INTERVAL GRAPH GENERALIZATIONS
No full textWe consider the problem of finding a Hamiltonian circuit in some classes of intersection graphs which generalize interval graphs. We show that the problem is NP-complete for undirected path graphs (and hence chordal graphs), double interval graphs, and rectangle graphs
Assigning codes in wireless networks: bounds and scaling properties
No full textIn the Code Division Multiple Access (CDMA) framework, collisions that can occur in wireless networks are eliminated by assigning orthogonal codes to stations, a problem equivalent to that of coloring graphs associated to the physical network. In this paper we present new upper and lower bounds for two versions of the problem (hidden and primary collision avoidance - HP-CA - or hidden collision avoidance only - H-CA). In particular, optimal assignments for special topologies and heuristics for general topologies are proposed. The schemes show better average results with respect to existing alternatives. Furthermore, the gaps between the upper bound given by the heuristic solution, the lower bound obtained from the maximum-clique problem, and the optimal solution obtained by branch and bound are investigated in the different settings. A scaling law is then proposed to explain the relations between the number of codes needed in Euclidean networks with different station densities and connection distances. The substantial difference between the two versions HP-CA and H-CA of the problem is investigated by studying the probabilistic distribution of connections as a function of the distance, and the asymptotic size of the maximum cliques
SOME PARALLEL ALGORITHMS ON INTERVAL-GRAPHS
No full textParallel algorithms are given for finding a maximum weighted clique, a maximum weighted independent set, a minimum clique cover, and a minimum weighted dominating set of an interval graph. Parallel algorithms are also given for finding a Hamiltonian circuit and the minimum bandwidth of a proper interval graph. The shared memory model (SMM) of parallel computers is used to obtain fast algorithms
STRING MATCHING WITH WEIGHTED ERRORS
No full textAbstractIn the approximate string matching problem, differences are allowed between the pattern string P and each of its occurrences in the text string T, and one is interested in finding all the occurrences of P in T with at most k differences. We consider here weighted differences (errors) between P and T and develop fast sequential and parallel algorithms. In particular, we allow the following types of errors: mismatch whose weight depends on the mismatching characters, extra character with constant weight, missing character with constant weight, and transposition of two consecutive characters with constant weight. A set of theoretical results allows to extend known algorithms to solve this problem with O(kn) sequential time and O(k + log m) parallel time on a 4PRAM model with max{n + k + 1, mp2} processors, where k is the maximum sum of the error weights, n is the length of T, and m is the length of P
- …
