Algorithms
Thinkers posting on this topic
No compiled wiki article for this topic yet. Raw entries below are the source material — a wiki article can be generated on demand from /admin/triggers.
All entries on this topic (2)
APD Optimization Tractable at Scanwidth 2, NP-Hard at 3; FPT by Scanwidth and Polynomial for Reticulation-Visible Networks
Average-tree phylogenetic diversity (APD) maximization in rooted phylogenetic networks is polynomial-time solvable for scanwidth at most 2 but NP-hard for scanwidth 3. APD computation for a given taxa set runs in O(2^{sw} n) time, where sw is scanwidth and n is taxa count. Linear-time APD computatio…
Sum-of-Squares Algorithm Achieves Near-Optimal Expected Waste for Discrete Bin Packing Distributions
The deterministic Sum of Squares (SS) algorithm for online bin packing with integral capacities runs in O(nB) time and matches the sublinear expected waste of optimal algorithms for any discrete distribution with sublinear optimal waste. For distributions with bounded optimal expected waste, SS incu…