Search

In real world applications, important resources like energy are saved by deliberately using so-called low-cost operations that are less reliable. Some of these approaches are based on a dual mode technology where it is possible to choose between high-energy operations (always correct) and low-energy operations (prone to errors), and thus enable to trade energy for correctness. In this work we initiate the study of algorithms for solving optimization problems that in their computation are allowed to choose between two types of operations: high-energy comparisons (always correct but expensive) and low-energy comparisons (cheaper but prone to errors). For the errors in low-energy comparisons, we assume the persistent setting, which usually makes it impossible to achieve optimal solutions without high-energy comparisons. We propose to study a natural complexity measure which accounts for the number of operations of either type separately. We provide a new family of algorithms which, for a fairly large class of maximization problems, return a constant approximation using only polylogarithmic many high-energy comparisons and only O(n log n) low-energy comparisons. This result applies to the class of p-extendible system s [Mestre, 2006], which includes several NP-hard problems and matroids as a special case (p=1). These algorithmic solutions relate to some fundamental aspects studied earlier in different contexts: (i) the approximation guarantee when only ordinal information is available to the algorithm; (ii) the fact that even such ordinal information may be erroneous because of low-energy comparisons and (iii) the ability to approximately sort a sequence of elements when comparisons are subject to persistent errors. Finally, our main result is quite general and can be parametrized and adapted to other error models., Leibniz International Proceedings in Informatics (LIPIcs), 149, ISSN:1868-8969, 30th International Symposium on Algorithms and Computation (ISAAC 2019), ISBN:978-3-95977-130-6

We present robust, adaptive routing policies for time-varying networks (temporal graphs) in the presence of random edge-failures. Such a policy answers the following question: How can a traveler navigate a time-varying network where edges fail randomly in order to maximize the traveler's preference with respect to the arrival time? Our routing policy is computable in near-linear time in the number of edges in the network (for the case when the edges fail independently of each other). Using our robust routing policy, we show how to travel in a public transit network where the vehicles experience delays. To validate our approach, we present experiments using real-world delay data from the public transit network of the city of Zurich. Our experiments show that we obtain significantly improved outcomes compared to a purely schedule-based policy: The traveler is on time 5-11 percentage points more often for most destinations and 20-40 percentage points more often for certain remote destinations. Our implementation shows that the approach is fast enough for real-time usage. It computes a policy for 1-hour long journeys in around 0.1 seconds., OpenAccess Series in Informatics (OASIcs), 75, ISSN:2190-6807, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), ISBN:978-3-95977-128-3

We consider the problem of sorting n elements in the case of persistent comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (small) probability p, and comparisons cannot be repeated (Braverman and Mossel, SODA'08). Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, maximum dislocation and total dislocation better than Omega(log n) and Omega(n), respectively, regardless of its running time. In this paper, we present the first O(n log n)-time sorting algorithm that guarantees both O(log n) maximum dislocation and O(n) total dislocation with high probability. This settles the time complexity of this problem and shows that comparison errors do not increase its computational difficulty: a sequence with the best possible dislocation can be obtained in O(n log n) time and, even without comparison errors, Omega(n log n) time is necessary to guarantee such dislocation bounds. In order to achieve this optimality result, we solve two sub-problems in the persistent error comparisons model, and the respective methods have their own merits for further application. One is how to locate a position in which to insert an element in an almost-sorted sequence having O(log n) maximum dislocation in such a way that the dislocation of the resulting sequence will still be O(log n). The other is how to simultaneously insert m elements into an almost sorted sequence of m different elements, such that the resulting sequence of 2m elements remains almost sorted., Leibniz International Proceedings in Informatics (LIPIcs), 144, ISSN:1868-8969, 27th Annual European Symposium on Algorithms (ESA 2019), ISBN:978-3-95977-124-5

To cope with errors in computation has an ongoing tradition in computer science. In fact, errors can represent hardware faults, imprecise measurements, mistakes in judgments made by humans, or even may be deliberately introduced in order to save certain resources. In this thesis we consider a model, in which comparisons can fail. In particular, we assume that such comparisons allow us to query the linear order of two given elements but are prone to making errors: with some probability 1−p, the result of the comparison is correct, while with some small probability p, we get back the reverse order of the two queried elements. We distinguish between persistent and non-persistent comparison errors, where the former means that repeating the same comparison several times always yields the same result, whereas the latter means that every repetition of a comparison has again the same probabilities to be correct or wrong. In this regard, we are especially interested in algorithms that only use ordinal information of the elements to compute a solution to a given problem. Prominent examples are combinatorial problems such as comparison-based sorting, one focus in this thesis. But there are also many other optimization problems whose optimum solution or an approximation thereof can be computed without knowing the exact values of the elements. We begin this thesis with considering the problem of sorting in the presence of non-persistent comparison errors. Starting with an input sequence of n distinct elements, we examine two natural sorting strategies that repeatedly compare and swap two elements within the sequence: in the first, we restrict to pairs of elements whose positions in the current sequence are adjacent, while in the second, we allow to compare and swap two arbitrary elements. The sorting strategies can be considered as Markov chains, and we show that restricting to adjacent swaps yields a better “sortedness” of a sequence in stationary distribution than allowing arbitrary swaps, namely O(n) vs. O(n^2) total dislocation in expectation. (The dislocation of an element is the absolute difference between its position and its rank. The total dislocation of a sequence is the sum of all dislocations of the elements.) In regard to persistent comparison errors, we optimally solve the problem of sorting n elements in terms of running time and sortedness. In particular, we present an algorithm that in O(n log n) time returns a permutation of the elements achieving both O(log n) maximum dislocation of any element and O(n) total dislocation with high probability. Additionally, we show that this is the best we can hope for in this error model, as we provide tight lower bounds on the two dislocation measures. The second combinatorial problem that we consider is computing, in the presence of persistent comparison errors, a longest increasing subsequence of a given input sequence containing n distinct elements. Here we present an O(log n)-approximation algorithm that returns in O(n log n) time a subsequence of the input that is guaranteed to be increasing and whose length is at least Ω(1/log n) times the length of the correct answer. Moreover, we provide lower bounds to show that both the running time and the approximation factor are asymptotically tight. We then turn to more general optimization problems and allow algorithms to perform a few comparisons that are always correct, but obviously much more costly than their error-prone counterparts. The intention behind these “always-correct” comparisons is to guarantee that, despite of errors in the other comparisons, an approximation to the optimum solution of such a problem can still be found. We therefore extend our model of computation to have two types of comparisons: always-correct and error-prone, where for the latter we assume that the errors are persistent. In this model, we propose to study a natural complexity measure which accounts for the number of operations of either type of comparisons separately. For a large class of optimization problems, we finally show that a constant approximation can be computed using only a polylogarithmic number of always-correct comparisons, and O(n log n) error-prone comparisons. In particular, the result applies to k-extendible systems, which includes several NP-hard problems, as well as matroids as a special case.

We study very simple sorting algorithms based on a probabilistic comparator model. In our model, errors in comparing two elements are due to (1) the energy or effort put in the comparison and (2) the difference between the compared elements. Such algorithms keep comparing pairs of randomly chosen elements, and they correspond to Markovian processes. The study of these Markov chains reveals an interesting phenomenon. Namely, in several cases, the algorithm which repeatedly compares only adjacent elements is better than the one making arbitrary comparisons: on the long-run, the former algorithm produces sequences that are "better sorted". The analysis of the underlying Markov chain poses new interesting questions as the latter algorithm yields a non-reversible chain and therefore its stationary distribution seems difficult to calculate explicitly.

Counting the number of permutations of a given total displacement is equivalent to counting weighted Motzkin paths of a given area (Guay-Paquet and Petersen, 2014). The former combinatorial problem is still open. In this work, we show that this connection allows to construct efficient algorithms for counting and for sampling such permutations. These algorithms provide a tool to better understand the original combinatorial problem. A by-product of our approach is a different way of counting based on certain building sequences for Motzkin paths, which may be of independent interest., Comment: 19 pages. An extended abstract of this paper will be published at the 27th International Workshop on Combinatorial Algorithms 2016, IWOCA'16

We study very simple sorting algorithms based on a probabilistic comparator model. In our model, errors in comparing two elements are due to (1) the energy or effort put in the comparison and (2) the difference between the compared elements. Such algorithms keep comparing pairs of randomly chosen elements, and they correspond to Markovian processes. The study of these Markov chains reveals an interesting phenomenon. Namely, in several cases, the algorithm which repeatedly compares only adjacent elements is better than the one making arbitrary comparisons: on the long-run, the former algorithm produces sequences that are "better sorted". The analysis of the underlying Markov chain poses new interesting questions as the latter algorithm yields a non-reversible chain and therefore its stationary distribution seems difficult to calculate explicitly.

We study the minimum cut problem in the presence of uncertainty and show how to apply a novel robust optimization approach, which aims to exploit the similarity in subsequent graph measurements or similar graph instances, without posing any assumptions on the way they have been obtained. With experiments we show that the approach works well when compared to other approaches that are also oblivious towards the relationship between the input datasets.