3 papers
cs.CC2026
Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
Christoph Grüne, Berit Johannes, James B. Orlin +1
Many natural optimization problems derived from admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objec…
cs.DS2025
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
Daniel Dadush, James B. Orlin, Aaron Sidford +1
We provide faster strongly polynomial time algorithms solving maximum flow in structured -node -arc networks. Our results imply an -time strongly polynomial tim…
cs.SI2025
The Strong Maximum Circulation Algorithm: A New Method for Aggregating Preference Rankings
Nathan Atkinson, Scott C. Ganz, Dorit S. Hochbaum +1
We present a new optimization-based method for aggregating preferences in settings where each voter expresses preferences over pairs of alternatives. Our approach to identifying a…