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.
The Traveling Salesman Problem (TSP) is a classical prob- lem in discrete optimization. Its paradigmatic character makes it one of the most studied in computer science and operations research and one for which an impressive amount of algorithms (in particular heuristics and approximation algorithms) have been proposed. While in the general case the problem is known not to allow any constant ratio...
A minimum spanning tree (MST) with a small diameter is required in numerous practical situations. It is needed, for example, in distributed mutual exclusion algorithms in order to minimize the number of messages communicated among processors per critical section. The Diameter- Constrained MST (DCMST) problem can be stated as follows: given an undirected, edge-weighted graph G with n nodes and a positive...
We consider algorithms for a simple one-dimensional point placement problem: given N points on a line, and noisy measurements of the distances be- tween many pairs of them, estimate the relative positions of the points. Problems of this flavor arise in a variety of contexts. The particular motivating example that inspired this work comes from molecular biology; the points are markers on a chromosome...
We present certain dualities occuring in problems of design of virtual path layouts in ATM networks. We concentrate on the one- to-many problem on a chain network, in which one constructs a set of paths, that enable connecting one vertex with all others in the network. We consider the parameters of load (the maximum number of paths that go through any single edge) and hop count (the maximum number...
It is proved, sharpening previous results of Scheinerman and by analysing an algorithm, that the independence number of the random interval graph, defined as the intersection graph of n intervals whose end points are chosen at random on [0,1], concentrates around $$ 2\sqrt {\frac{n} {\pi }} $$ .
We consider strategies for full backups from the viewpoint of competitive analysis of online problems. We concentrate upon the re- alistic case that faults are rare, i.e. the cost of work between two faults is typically large compared to the cost of one backup. Instead of the (worst- case) competitive ratio we use a refined and more expressive quality measure, in terms of the average fault frequency...
The investigation of the possibility to efficiently compute approximations of hard optimization problems is one of the central and most fruitful areas of current algorithm and complexity theory. The aim of this paper is twofold. First, we introduce the notion of stability of approximation algorithms. This notion is shown to be of practical as well as of theoretical importance, especially for the real...
Counting functions can be defined syntactically or seman- tically depending on whether they count the number of witnesses in a non-deterministic or in a deterministic computation on the input. In the Turing machine based model, these two ways of defining counting were proven to be equivalent for many important complexity classes. In the circuit based model, it was done for #P and #L, but for low-level...
Map labeling is a classical key problem. The interest in this problem has grown over the last years, because of the need to churn out different types of maps from a growing and altering set of data. We will show that the problem of placing street names without conflicts in a rectangular grid of streets is NP-complete and APX-hard. This is the first result of this type in this area. Further importance...
American cities, especially their central regions usually have a very regular street pattern: We are given a rectangular grid of streets, each street has to be labeled with a name running along its street, such that no two labels overlap. For this restricted but yet realistic case an efficient algorithmic solution for the generally hard labeling problem gets in reach. The main contribution...
In this paper, we analyze algorithms for the online dial-a- ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that...
In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. We consider the online traveling salesman problem when restricted...
We present a practically efficient algorithm for the internal sorting problem. Our algorithm works in-place and, on the average, has a running-time of O(n log n) in the length n of the input. More specifically, the algorithm performs n log n + 3n comparisons and n log n + 2.65n element moves on the average. An experimental comparison of our proposed algorithm with the most efficient variants...
It is known that some triangulation graphs admit straight-line drawings realizing certain characteristics, e.g., greedy triangulation, minimum- weight triangulation, Delaunay triangulation, etc.. Lenhart and Liotta [12] in their pioneering paper on “drawable” minimum-weight triangulations raised an open problem: ‘Does every triangulation graph whose skeleton is a forest admit a minimum-weight drawing?’...
Given a boolean 2CNF formula F, the Max2Sat problem is that of finding the maximum number of clauses satisfiable simultaneously. In the corresponding decision version, we are given an additional parameter k and the question is whether we can simultaneously satisfy at least k clauses. This problem is NP-complete. We improve on known upper bounds on the worst case running time of Max2Sat, implying also...
In this paper, we propose an improved algorithm for dynam- ically maintaining the widest k-dense corridor as proposed in [6]. Our algorithm maintains a data structure of size O(n2), where n is the num- ber of points present on the floor at the current instant of time. For each insertion/deletion of points, the data structure can be updated in O(n) time, and the widest k-dense corridor in...
The problem of reconstructing a discrete set from its X-rays in a finite number of prescribed directions is NP-complete when the number of prescribed directions is greater than two. In this paper, we consider an interesting subclass of discrete sets having some connectivity and convexity properties and we provide a polynomial-time algorithm for reconstructing a discrete set of this class from its...
We consider a new method to retrieve keys in a static table. The keys of the table are stored in such a way that a binary search can be performed more efficently. An analysis of the method is performed and empirical evidence is given that it actually works.
We present an efficient algorithm for the approximate median selection problem. The algorithm works in-place; it is fast and easy to implement. For a large array it returns, with high probability, a very close estimate of the true median. The running time is linear in the length n of the input. The algorithm performs fewer than $$ \frac{4} {3}n $$ comparisons and $$ \frac{1} {3}n $$ exchanges...
A resource-free characterization of some complexity classes is given by means of the predicative recursion and constructive diagonal- ization schemes, and of restrictions to substitution. Among other classes, we predicatively harmonize in the same hierarchy PTIMEF, the class ε of the elementary functions, and classes DTIMESPACEF(np,nq...
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.