From Sorting to Optimization: Coping with ErrorProne Comparisons
dc.contributor.author
Geissmann, Barbara
dc.contributor.supervisor
Widmayer, Peter
dc.contributor.supervisor
Hromkovič, Juraj
dc.date.accessioned
20190125T10:25:36Z
dc.date.available
20190124T13:20:12Z
dc.date.available
20190124T13:42:55Z
dc.date.available
20190125T09:36:33Z
dc.date.available
20190125T10:25:36Z
dc.date.issued
2018
dc.identifier.uri
http://hdl.handle.net/20.500.11850/319422
dc.identifier.doi
10.3929/ethzb000319422
dc.description.abstract
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 nonpersistent 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 comparisonbased 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 nonpersistent 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 errorprone counterparts. The intention behind these “alwayscorrect” 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: alwayscorrect and errorprone, 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 alwayscorrect comparisons, and O(n log n) errorprone comparisons. In particular, the result applies to kextendible systems, which includes several NPhard problems, as well as matroids as a special case.
en_US
dc.format
application/pdf
en_US
dc.language.iso
en
en_US
dc.publisher
ETH Zurich
en_US
dc.rights.uri
http://rightsstatements.org/page/InCNC/1.0/
dc.title
From Sorting to Optimization: Coping with ErrorProne Comparisons
en_US
dc.type
Doctoral Thesis
dc.rights.license
In Copyright  NonCommercial Use Permitted
ethz.size
158 p.
en_US
ethz.identifier.diss
25656
en_US
ethz.publication.place
Zurich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002  ETH Zürich::00012  Lehre und Forschung::00007  Departemente::02150  Dep. Informatik / Dep. of Computer Science::02643  Institut für Theoretische Informatik / Inst. Theoretical Computer Science::03340  Widmayer, Peter (emeritus) / Widmayer, Peter (emeritus)
en_US
ethz.date.deposited
20190124T13:20:16Z
ethz.source
FORM
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
20190125T10:25:43Z
ethz.rosetta.lastUpdated
20190125T10:25:43Z
ethz.rosetta.exportRequired
true
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.882004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=From%20Sorting%20to%20Optimization:%20Coping%20with%20ErrorProne%20Comparisons&rft.date=2018&rft.au=Geissmann,%20Barbara&rft.genre=unknown&rft.btitle=From%20Sorting%20to%20Optimization:%20Coping%20with%20ErrorProne%20Comparisons
Files in this item
Publication type

Doctoral Thesis [26052]