Realizability makes a difference: a complexity gap for sink-finding in USOs

DOI10.1007/978-3-031-38906-1_47MaRDI QIDQ6139054zbMATH OpenFDO

Authors Simon Weber, Joel Widmer

Publication date 16 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.05985

zbMATH Keywords

query complexityrealizabilityunique sink orientation

Mathematics Subject Classification ID

Data structures (68P05) Algorithms in computer science (68Wxx)

Abstract: Algorithms for finding the sink in Unique Sink Orientations (USOs) of the hypercube can be used to solve many algebraic and geometric problems, most importantly including the P-Matrix Linear Complementarity Problem and Linear Programming. The realizable USOs are those that arise from the reductions of these problems to the USO sink-finding problem. Finding the sink of realizable USOs is thus highly practically relevant, yet it is unknown whether realizability can be exploited algorithmically to find the sink more quickly. However, all (non-trivial) known unconditional lower bounds for sink-finding make use of USOs that are provably not realizable. This indicates that the sink-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. We consider the class of Matouv{s}ek-type USOs, which are a translation of Matouv{s}ek's LP-type problems into the language of USOs. We show a query complexity gap between sink-finding in all, and sink-finding in only the realizable $n$-dimensional Matouv{s}ek-type USOs. We provide concrete deterministic algorithms and lower bounds for both cases, and show that in the realizable case $O(lo{g}^{2}n)$ vertex evaluation queries suffice, while in general exactly $n$ queries are needed. The Matouv{s}ek-type USOs are the first USO class found to admit such a gap.

Cites work

• Counting unique-sink orientations
• Digraph Models of Bard-Type Algorithms for the Linear Complementarity Problem
• Enumeration of PLCP-orientations of the 4-cube
• Finding the sink takes some time: An almost quadratic lower bound for finding the sink of unique sink oriented cubes
• Fundamentals of Computation Theory
• scientific article; zbMATH DE number 1241841 (Why is no real title available?)
• scientific article; zbMATH DE number 1775049 (Why is no real title available?)
• Linear programming and unique sink orientations
• Lower bounds for a subexponential optimization algorithm
• Mathematical problems for the next century
• Randomized pivot algorithms for \(P\)-matrix linear complementarity problems
• The Random‐Facet simplex algorithm on combinatorial cubes
• Unique end of potential line
• Unique sink orientations of grids

Cited in

(1)

• Realizability in Matoušek unique sink orientations: characterization and complexity gap

This page was built for publication: Realizability makes a difference: a complexity gap for sink-finding in USOs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6139054)