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

Algorithms for finding the sink in Unique Sink Orientations (USOs) of thehypercube can be used to solve many algebraic and geometric problems, mostimportantly including the P-Matrix Linear Complementarity Problem and LinearProgramming. The realizable USOs are those that arise from the reductions ofthese problems to the USO sink-finding problem. Finding the sink of realizableUSOs is thus highly practically relevant, yet it is unknown whetherrealizability can be exploited algorithmically to find the sink more quickly.However, all (non-trivial) known unconditional lower bounds for sink-findingmake use of USOs that are provably not realizable. This indicates that thesink-finding problem might indeed be strictly easier on realizable USOs.  In this paper we show that this is true for a subclass of all USOs. Weconsider the class of Matou\v{s}ek-type USOs, which are a translation ofMatou\v{s}ek's LP-type problems into the language of USOs. We show a querycomplexity gap between sink-finding in all, and sink-finding in only therealizable $n$-dimensional Matou\v{s}ek-type USOs. We provide concretedeterministic algorithms and lower bounds for both cases, and show that in therealizable case $O(log^2 n)$ vertex evaluation queries suffice, while ingeneral exactly $n$ queries are needed. The Matou\v{s}ek-type USOs are thefirst USO class found to admit such a gap.

Realizability Makes a Difference: A Complexity Gap for Sink-Finding in USOs