Analytical aspects of tie breaking

摘要

This article describes an analytical framework for reasoning about the issue of tie breaking in algorithm theory. The core of this framework is the concept of robust algorithms. Such kind of algorithms have the convenient property that an arbitrary set of degenerate cases can be ignored without loss of generality during proofs of many important properties, e.g., runtime, space requirements, feasibility, competitive and approximation ratios. Here degeneracy is defined as a set of problem instances satisfying a certain property, and this property is independent from both the algorithm under consideration and the specific combinatorial problem structure. It turns out that robustness is related to the tie breaking policy of algorithms in two different ways. On the one hand, the set of inputs where a tie actually occurs is typically (but not always) a degenerate case. On the other hand, we show that for any algorithm there is a way to break ties such that it becomes robust. In particular, robustness is guaranteed by any tie breaking strategy that can be interpreted as symbolic perturbation. For many typical algorithms the implicit usage of symbolic perturbation can be easily verified and so the consideration of degenerate cases can be avoided during their analysis. The concept of robustness also gives a theoretical explanation of why tie breaking does often not matter at all.