We propose a novel approach for optimization under uncertainty. Our approach does not assume any particular noise model behind the measurements, and only requires two typical instances. We first propose a measure of similarity of instances (with respect to a given objective). Based on this measure, we then choose a solution randomly among all solutions that are near-optimum for both instances. The exact notion of near-optimum is intertwined with the proposed similarity measure. Our similarity measure also allows us to derive formal statements about the expected quality of the computed solution. Furthermore, we apply our approach to various optimization problems.

Given an urban public transportation network and historic delay information, we consider the problem of computing reliable journeys. We propose new algorithms based on our recently presented solution concept (Böhmová et al., ATMOS 2013), and perform an experimental evaluation using real-world delay data from Zürich, Switzerland. We compare these methods to natural approaches as well as to our recently proposed method which can also be used to measure typicality of past observations. Moreover, we demonstrate how this measure relates to the predictive quality of the individual methods. In particular, if the past observations are typical, then the learning- based methods are able to produce solutions that perform well on typical days, even in the presence of large delays.

We study variants of the vertex disjoint paths problem in plane graphs where paths have to be selected from given sets of paths. We investigate the problem as a decision, maximization, and routing-in-rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the locations of the terminals on the outer face of the given planar embedding of the graph lead to polynomially solvable cases for the decision and maximization versions of the problem. For the routing-in-rounds problem, we obtain a p-approximation algorithm, where p is the maximum number of alternative paths for a terminal pair, when restricting the locations of the terminals to the outer face such that they appear in a counterclockwise traversal of the boundary as a sequence for some permutation . © 2015 Wiley Periodicals, Inc.NETWORKS, Vol. 66(2), 136–144 2015

We consider the exploration of a simple polygon P by a robot that moves from vertex to vertex along edges of the visibility graph of P . The visibility graph has a vertex for every vertex of P and an edge between two vertices if they see each other—that is, if the line segment connecting them lies inside P entirely. While located at a vertex, the robot is capable of ordering the vertices it sees in counterclockwise order as they appear on the boundary, and for every two such vertices, it can distinguish whether the angle between them is convex (⩽ π) or reflex ( > π). Other than that, distant vertices are indistinguishable to the robot. We assume that an upper bound on the number of vertices is known. We obtain the general result that a robot exploring any locally oriented, arc-labeled graph G can always determine the base graph of G . Roughly speaking, this is the smallest graph that cannot be distinguished by a robot from G by its observations alone, no matter how it moves. Combining this result with various other techniques allows the ability to show that a robot exploring a polygon P with the preceding capabilities is always capable of reconstructing the visibility graph of P . We also show that multiple identical, indistinguishable, and deterministic robots of this kind can always solve the weak rendezvous problem in which they need to position themselves such that they mutually see each other—for instance, such that they form a clique in the visibility graph.

In chromatic variants of the art gallery problem, simple polygons are guarded with point guards that are assigned one of k colors each. We say these guards cover the polygon. Here we consider the conflict-free chromatic art gallery problem, first studied by Bärtschi and Suri (Algorithmica 2013): A covering of the polygon is conflict-free if each point of the polygon is seen by some guard whose color appears exactly once among the guards visible to that point. We are interested in the smallest number k(n) of colors that ensure such a covering for every n-vertex polygon.

We study optimization in the presence of uncertainty such as noise in measurements, and advocate a novel approach of tackling it. The main difference to any existing approach is that we do not assume any knowledge about the nature of the uncertainty (such as for instance a probability distribution). Instead, we are given several instances of the same optimization problem as input, and, assuming they are typical w.r.t. the uncertainty, we make use of it in order to compute a solution that is good for the sample instances as well as for future (unknown) typical instances.

Bulk-loading of R-trees has been an important problem in academia and industry for more than twenty years. Current algorithms create R-trees without any information about the expected query profile. However, query profiles are extremely useful for the design of efficient indexes. In this paper, we address this deficiency and present query-adaptive algorithms for building R-trees optimally designed for a given query profile. Since optimal R-tree loading is NP-hard (even without tuning the structure to a query profile), we provide efficient, easy to implement heuristics. Our sort-based algorithms for query-adaptive loading consist of two steps: First, sorting orders are identified resulting in better R-trees than those obtained from standard space-filling curves. Second, for a given sorting order, we propose a dynamic programming algorithm for generating R-trees in linear runtime. Our experimental results confirm that our algorithms generally create significantly better R-trees than the ones obtained from standard sort-based loading algorithms, even when the query profile is unknown.

Communication in networks suffers if a link fails. When the links are edges of a tree that has been chosen from an underlying graph of all possible links, a broken link even disconnects the network. Most often, the link is restored rapidly. A good policy to deal with this sort of transient link failures is swap rerouting, where the temporarily broken link is replaced by a single swap link from the underlying graph. A rapid replacement of a broken link by a swap link is only possible if all swap links have been precomputed. The selection of high-quality swap links is essential; it must follow the same objective as the originally chosen communication subnetwork. We are interested in a minimum-diameter tree in a graph with edge weights (so as to minimize the maximum travel time of messages). Hence, each swap link must minimize (among all possible swaps) the diameter of the tree that results from swapping. We propose a distributed algorithm that efficiently computes all of these swap links, and we explain how to route messages across swap edges with a compact routing scheme. Finally, we consider the computation of swap edges in an arbitrary spanning tree, where swap edges are chosen to minimize the time required to adapt routing in case of a failure, and give efficient distributed algorithms for two variants of this problem.

We study variants of the vertex disjoint paths problem in planar graphs where paths have to be selected from a given set of paths. We study the problem as a decision, maximization, and routing-in-rounds problem. Although all considered variants are NP-hard in planar graphs, restrictions on the location of the terminals, motivated by railway applications, lead to polynomially solvable cases for the decision and maximization versions of the problem, and to a $p$-approximation algorithm for the routing-in-rounds problem, where $p$ is the maximum number of alternative paths for a terminal pair.

Abstract Motivation: Tandem mass spectrometry allows for high-throughput identification of complex protein samples. Searching tandem mass spectra against sequence databases is the main analysis method nowadays. Since many peptide variations are possible, including them in the search space seems only logical. However, the search space usually grows exponentially with the number of independent variations and may therefore overwhelm computational resources. Results: We provide fast, cache-efficient search algorithms to screen large peptide search spaces including non-tryptic peptides, whole genomes, dozens of posttranslational modifications, unannotated point mutations and even unannotated splice sites. All these search spaces can be screened simultaneously. By optimizing the cache usage, we achieve a calculation speed that closely approaches the limits of the hardware. At the same time, we control the size of the overall search space by limiting the combinations of variations that can co-occur on the same peptide. Using a hypergeometric scoring scheme, we applied these algorithms to a dataset of 1 420 632 spectra. We were able to identify a considerable number of peptide variations within a modest amount of computing time on standard desktop computers. Availability: PepSplice is available as a C++ application for Linux, Windows and OSX at www.ti.inf.ethz.ch/pw/software/pepsplice/. It is open source under the revised BSD license. Contact: [email protected] or [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

Let a communication network be modelled by a graph G=(V,E) of n nodes and m edges. Classic communication operations among nodes in the graph (e.g., broadcasting, multicasting, gossiping, etc.) usually take place on a subgraph of G, which is built in such a way that a given objective function is optimized. Among the many possible topologies of such a subgraph, the minimum radius spanning tree (MRST) is a rooted tree which minimizes the distance from the root to a farthest node. The MRST finds a natural application in several facility location problems, since it allows to minimize the maximum delay for reaching the center from the periphery of the tree. In this paper, we consider the problem of computing an MRST in a non-cooperative setting in which each edge of G is controlled by a selfish agent, and the cost she asks for using her edge depends only on her private information. Under these assumptions, we provide a mechanism that computes a true MRST of G in O(mn√n+n3 log n) time and O(n2 √n) space. Interestingly, this is just at most a linear factor away from the time needed to compute an MRST in a canonical centralized framework.

De novo Sequencing of peptides is a challenging task in proteome re- search. While there exist reliable DNA-sequencing methods, the high- throughput de novo sequencing of proteins by mass spectrometry is still an open problem. Current approaches suffer from a lack in precision to detect mass peaks in the spectrograms. In this paper we present a novel method for de novo peptide sequencing based on a hidden Markov model. Experiments effectively demonstrate that this new method signif- icantly outperforms standard approaches in matching quality.

Support for exploratory interaction with databases in applications such as data mining requires that the first few results of an operation be available as quickly as possible. We study the algorithmic side of what can and what cannot be achieved for processing join operations. We develop strategies that modify the strict two-phase processing of the sort-merge paradigm, intermingling join steps with selected merge phases of the sort. We propose an algorithm that produces early join results for a broad class of join problems, including many not addressed well by hash-based algorithms. Our algorithm has no significant increase in the number of I/O operations needed to complete the join compared to standard sort-merge algorithms.

The problem MINIMUM CONVEX COVER of covering a given polygon with a minimum number of (possibly overlapping) convex polygons is known to be NP-hard, even for polygons without holes [J. C. Culberson and R. A. Reckhow, J. Algorithms, 17 (1994), pp. 2--44]. We propose a polynomial-time approximation algorithm for this problem for polygons with or without holes that achieves an approximation ratio of O(log n), where n is the number of vertices in the input polygon. To obtain this result, we first show that an optimum solution of a restricted version of this problem, where the vertices of the convex polygons may lie only on a certain grid, contains at most three times as many convex polygons as the optimum solution of the unrestricted problem. As a second step, we use dynamic programming to obtain a convex polygon which is maximum with respect to the number of "basic triangles" that are not yet covered by another convex polygon. We obtain a solution that is at most a logarithmic factor off the optimum by iteratively applying our dynamic programming algorithm. Furthermore, we show that MINIMUM CONVEX COVER is APX-hard; i.e., there exists a constant $\delta >0$ such that no polynomial-time algorithm can achieve an approximation ratio of $1+\delta$. We obtain this result by analyzing and slightly modifying an already existing reduction [J. C. Culberson and R. A. Reckhow, J. Algorithms, 17 (1994), pp. 2--44].

We propose a new solution to the problem of positioning base station transmitters of a mobile phone network and assigning frequencies to the transmitters, both in an optimal way. Since an exact solution cannot be expected to run in polynomial time for all interesting versions of this problem (they are all NP-hard), our algorithm follows a heuristic approach based on the evolutionary paradigm. For this evolution to be efficient, i.e., goal-oriented and sufficiently random at the same time, problem-specific knowledge is embedded in the operators. The problem requires both the minimization of the cost and of the channel interference. We examine and compare two standard multiobjective techniques and a new algorithm - the steady-state evolutionary algorithm with Pareto tournaments. One major finding of the empirical investigation is a strong influence of the choice of the multiobjective selection method on the utility of the problem-specific recombination leading to a significant difference in the solution quality.

The maintenance of large raster images under spatial operations is still a major performance bottleneck. For reasons of storage space, images in a collection, such as satellite pictures in geographic information systems, are maintained in compressed form. Instead of performing a spatially selective operation on an image by first decompressing the compressed version, we propose to perform queries directly on the compressed version of the image. We suggest a compression technique that allows for the subsequent use of a spatial index structure to guide a spatial search. In response to a window query, our algorithm delivers a compressed partial image, or the exact uncompressed requested image region. In addition to the support of spatial queries on compressed continuous tone images, the new compression algorithm is even competitive in terms of the compression ratio that it achieves, compared to other standard lossless compression techniques.

Presents a new algorithm called the 'bulk index join' that can be applied to a broad class of non-equijoins. Similar to the well-known index nested-loops join algorithm, the bulk index join probes the records of the outer relation against the inner relation by using a pre-existing index structure. Like the index nested-loops join, our algorithm is generic in that any tree-based index structure supporting the join predicate can be used. Moreover, the designer of a new index structure might use our generic code to extend the functionality of the index structure without any additional effort. Our experience indicates that the bulk index join is a generic algorithm that performs very fast, and that its implementation is simple enough to be of immediate practical value.

We present a prototype system for a simple version of electromagnetic wave propagation prediction in rural areas, using a real time exploration environment for very large topographic scenes. The wave propagation prediction algorithm is based on a simple line of sight approach, realized with a modified hidden surface removal algorithm. The system serves as a transmitter management tool for interactively placing transmitters and studying the effects. Improvements according to the propagation prediction and automatic optimized placement of transmitters are current subjects of our research.

Advocates a desktop virtual reality (VR) interface to a geographic information system (GIS). The navigational capability to explore large topographic scenes is a powerful metaphor and a natural way of interacting with a GIS. VR systems succeed in providing visual realism and real-time navigation and interaction, but fail to cope with very large amounts of data and to provide the general functionality of information systems. We suggest a way to overcome these problems. We describe a prototype system, called ViRGIS (Virtual Reality GIS), that integrates two system platforms: a client that runs the VR component interacts via a (local or wide area) network with a server that runs an object-oriented database containing geographic data. For the purpose of accessing data efficiently, we describe how to integrate a geometric index into the database, and how to perform the operations that are requested in a real-time trip through the virtual world.

A distributed counter allows each processor in an asynchronous message passing network to access the counter value and increment it We study the problem of implementing a distributed counter such that no processor is a communication bottleneck We prove a lower bound of k on the number of messages that some processor must exchange in a sequence of n counting operations spread over n processors where kkk n We propose a counter that achieves this bound for the situation it is derived for namely when each processor increments the counter exactly once Hence the lower bound is tight Because most algorithms and data structures count in some way the lower bound holds for many distributed computations We feel that the proposed concept of a communication bottleneck is a relevant measure of eciency for a distributed algorithm and data structure because it indicates the achievable degree of distribution.

Databases are growing steadily, and distributed computer systems are more and more easily available. This provides an opportunity to satisfy the increasingly tighter efficiency requirements by means of distributed data structures. The design and analysis of these structures under efficiency aspects, however, has not yet been studied sufficiently. To our knowledge, a single scalable, distributed data structure has been proposed so far. It is a distributed variant of linear hashing with uncontrolled splits, and, as a consequence, performs efficiently for data distributions that are close to uniform, but not necessarily for others. In addition, it does not support queries that refer to the linear order of keys, such as nearest neighbor or range queries. We propose a distributed search tree that avoids these problems, since it inherits desirable properties from non-distributed trees. Our experiments show that our structure does indeed combine a guarantee for good storage space utilization with high query efficiency. Nevertheless, we feel that further research in the area of scalable, distributed data structures is dearly needed; it should eventually lead to a body of knowledge that is comparable with the non-distributed, classical data structures field.

In this paper, we motivate four different user defined window query classes and derive a probabilistic model for each of them. For each model, we characterize the efficiency of spatial data structures in terms of the expected number of data bucket accesses needed to perform a window query. Our analytical approach exhibits the performance phenomena independent of data structure and implementation details and whether the objects are points or non-point objects.

The design of spatial data structures has made great strides in recent years in response to be increasing importance of applications such as CAD that require great efficiency in spatial database technology and in computational geometry. The variety of spatial data structures and retrieval algorithms known suggests that it is difficult or impossible to design general purpose structures that perform well across the entire spectrum of objects to be stored and queries to be processed—generality comes at the cost of performance and increased algorithm complexity. Thus simple algorithms that perform efficiently on a restricted class of problems are clearly of interest. The guard file is a new data structure, with its access and update algorithms, designed to answer stabbing and intersection queries on a dynamic collection of spatial objects that satisfy a shape constraint. The objects stored must be ‘fat’ in a technical sense, namely convex with an aspect ratio (width/length) ≥f, where f is a constant characteristics of the class, 0

article Spatial priority search: an access technique for scaleless maps Share on Authors: Bruno Becker Institut für Informatik, Universität Freiburg, Rheinstraβe 10-12, D-7800 Freiburg Institut für Informatik, Universität Freiburg, Rheinstraβe 10-12, D-7800 FreiburgView Profile , Hans-Werner Six Praktische Informatik III, FernUniversität Hagen, Postfach 940 D-5800 Hagen Praktische Informatik III, FernUniversität Hagen, Postfach 940 D-5800 HagenView Profile , Peter Widmayer Institut für Informatik, Universität Freiburg, Rheinstraβe 10-12, D-7800 Freiburg Institut für Informatik, Universität Freiburg, Rheinstraβe 10-12, D-7800 FreiburgView Profile Authors Info & Claims ACM SIGMOD RecordVolume 20Issue 2June 1991 pp 128–137https://doi.org/10.1145/119995.115805Online:01 April 1991Publication History 25citation340DownloadsMetricsTotal Citations25Total Downloads340Last 12 Months7Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In many nonstandard database applications, spatial access to geometric objects is very important. A new access structure, the R-file, is presented for geometric objects in a dynamic environment. An extensive performance evaluation reveals that the R-file, which is based on handling axis-parallel rectangles in secondary storage, has higher storage space utilization and a more compact directory, and turns out to be more efficient in exact match and window queries than comparable schemes, e.g. R-trees or grid file variants, for example, for maintaining geometric objects.>

Presents a dynamic, globally order-preserving hashing technique, based on linear hashing, where the spatial proximity of points is preserved beyond data buckets. The method adaptively generates a bucket numbering, which is a flexible variant of the well-known z-ordering. In addition to the standard dictionary operations, the authors' dynamic z-hashing scheme supports the efficient implementation of proximity queries.>

A principle is presented for transforming suitable index structures for points into index structures for k-dimensional intervals. In many applications, these intervals serve as simple geometric keys for nonzero-size objects. The transformation fully preserves the advantages of the selected index structure for points, such as efficient update and retrieval operations, especially range queries, as well as high storage space utilization. The authors have implemented an index structure for rectangles based on the grid file. A performance evaluation with geographic data shows highly encouraging results.>

Storage access schemes for points, supporting spatial searching, usually suffer from an undesirably low storage space utilization. We show how a given set of points can be distributed among two grid files in such a way that storage space utilization is optimal. The optimal twin grid file can be built practically as fast as a standard grid file, i.e., the storage space optimality is obtained at almost no extra cost. We compare the performances of the standard grid file, the optimal static twin grid file, and an efficient dynamic twin grid file, where insertions and deletions trigger the redistribution of points among the two grid files. Twin grid files utilize storage space at roughly 90%, as compared with the 69% of the standard grid file. Typical range queries - the most important spatial search operations - can be answered in twin grid files at least as fast as in the standard grid file.

Given a set of n rectangles with sides parallel to the coordinate axes, we show how to determine whether their union, viewed as a set of disjoint polygons, has a hole. The algorithm presented needs no more than $O( n\log n )$ time and $O( n )$ space, which is shown to be optimal. However, in practice it is also necessary to know the locations of holes, if there are any. We present an algorithm to determine the locations of all h holes in $O( n\log n + h )$ time and $O( n )$ space, which is again optimal. The algorithm computes a point within each hole, representing the location of the hole. The efficiency of these and several other algorithms follows from some simple combinatorial arguments about sets of rectangles in the plane.

In VLSI design, technology requirements often dictate the use of only two orthogonal orientations, determining both the shape of objects and the distance function, the $L_1 $-metric, to be used for wiring objects. More recent VLSI fabrication technology is capable of creating edges and wires in both the orthogonal and diagonal orientations. We generalize the distance concept to the case where any fixed set of orientations is allowed, and introduce a family of naturally induced metrics, and the subsequent generalization of geometrical concepts. A shortest connection between two points is in this case a path composed of line segments with only the given orientations. We derive optimal solutions for various basic planar distance problems in this setting, such as the computation of a Voronoi diagram, a minimum spanning tree, and the (minimum and maximum) distance between two convex polygons. Many other theoretically interesting and practically relevant problems remain to be solved. In particular, the new family of metrics may help bridge the gap between the $L_1 $- and $L_2 $-metrics, as those are the limiting cases for two and infinitely many regularly distributed orientations.

We study the rectilinear shortest paths and minimum spanning tree (MST) problems for a set of points in the plane in the presence of rectilinear obstacles. We use the track graph, a suitably defined grid-like structure, to obtain efficient solutions for both problems. The track graph consists of rectilinear tracks defined by the obstacles and the points for which shortest paths and a minimum spanning tree are sought. We use a growth process like Dijkstra's on the track graph to find shortest paths from any point in the set to all other points (the one-to-all shortest paths problem). For the one-to-all shortest paths problem for n points we derive an O(n min {log n, log e} + (e + k) log t) time algorithm, where e is the total number of edges of all obstacles, t is the number of extreme edges of all obstacles, and k is the number of intersections among obstacle tracks (all bounds are for the worst case). The MST for the points is constructed also in time O(n log n + (e + k) log t) by a hybrid method of searching for shortest paths while simultaneously constructing an MST. An interesting application of the MST algorithm is the approximation of Steiner trees in graphs.

In computational geometry, problems involving only rectilinear objects with edges parallel to the x -and y-axes have attracted great attention. They are often easier to solve than the same problems for arbitrary objects, and solutions are of high practical value, for instance in VLSI design. This is because in VLSI design technology requirements often dictate the use of only two orthogonal orientations for the boundary edges of objects as well as wires.

The purpose of a database concurrency control mechanism is to control a transaction system in such a way that only serializable executions of transactions are possible; that is, safety is enforced. Locking is an appropriate means to achieve safety. In this paper the following problem is considered:Can the set of all serializable schedules (in the sense of conflict-preserving serializability) of a transaction system be defined by locking, i.e., can maximal concurrency be achieved by locking?An efficient algorithm exists for the problem in the case of two-transaction systems, but in general the problem is NP-complete. In the case in which maximal concurrency indeed is achievable by locking a locking policy realizing maximal concurrency can be constructed efficiently. Finally, an easy-to-test sufficient condition under which maximal concurrency is achieved by locking is discussed.