English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In analyses of algorithms, a substantial amount of effort has often to bespent on the discussion of special cases. For example, when the analysisconsiders the cases X<Y and X>Y separately, one might have to be especiallycareful about what happens when X=Y. On the other hand, experience tells usthat when a yet unregarded special case of this kind is discovered, one nearlyalways finds a way to handle it. This is typically done by modifying theanalysis and/or the algorithm very slightly.  In this article we substantiate this observation theoretically. Weconcentrate on deterministic algorithms for weighted combinatorial optimizationproblems. A problem instance of this kind is defined by its structure and avector of weights. The concept of a null case is introduced as set of probleminstances whose weight vectors constitute a nowhere open set (or null set) inthe space of all possible weight configurations. An algorithm is called robustif any null case can be disregarded in the analysis of both its solutionquality and resource requirements.  We show that achieving robustness is only a matter of breaking ties the rightway. More specifically, we show that the concept of symbolic perturbation knownfrom the area of geometric algorithms guarantees that no surprises will happenin null cases. We argue that for a huge class of combinatorial optimizationalgorithms it is easy to verify that they implicitly use symbolic perturbationfor breaking ties and thus can be analyzed under the assumption that somearbitrary null case never occurs. Finally, we prove that there exists asymbolic perturbation tie breaking policy for any algorithm.

Simpler Proofs by Symbolic Perturbation