The deterministic competitive ratio of the Parking Permit Problem is exactly K; the randomized ratio is at most ln K + ln ln K + O(1) and at least ln K + ln ln K + o(1).
Paths, trees, and flowers
5 Pith papers cite this work, alongside 2,352 external citations. Polarity classification is still indexing.
5
Pith papers citing it
2,352
external citations · OpenAlex
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
unclear 1representative citing papers
Bounded fitting can be extended to expressive description logics while retaining generalization guarantees and implemented practically via SAT solvers.
A near-linear-time algorithm finds a well-spread perfect matching in bridgeless cubic graphs by using a cactus representation of 2-edge-cuts with efficient updates under reductions.
Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.
A topical review unifying statistical mechanics, tensor network, and AI approaches to approximate maximum likelihood decoding for quantum error correction codes.
citing papers explorer
-
Primal-Dual Online Algorithms for the Parking Permit Problem
The deterministic competitive ratio of the Parking Permit Problem is exactly K; the randomized ratio is at most ln K + ln ln K + O(1) and at least ln K + ln ln K + o(1).
-
Bounded Fitting for Expressive Description Logics
Bounded fitting can be extended to expressive description logics while retaining generalization guarantees and implemented practically via SAT solvers.
-
A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
A near-linear-time algorithm finds a well-spread perfect matching in bridgeless cubic graphs by using a cactus representation of 2-edge-cuts with efficient updates under reductions.
-
Flows in Almost Linear Time via Adaptive Preconditioning
Algorithms achieve almost-linear time for ℓ_p-norm flow and dual regression problems on unit-weighted graphs for a range of p, plus applications to max-flow and total variation.
-
Maximum Likelihood Decoding of Quantum Error Correction Codes
A topical review unifying statistical mechanics, tensor network, and AI approaches to approximate maximum likelihood decoding for quantum error correction codes.