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

DOI10.1007/978-3-031-38906-1_47arXiv2207.05985MaRDI QIDQ6139054

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

realizabilityquery complexityunique sink orientation

Mathematics Subject Classification ID

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

Cites Work

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