faction
发表于 2025-3-30 10:09:19
Throughput Scheduling with Equal Additive Laxityin polynomial time. This contrasts the strong NP-hardness of the problem variant with arbitrary (and even equal multiplicative) laxity. Further, we give a fully polynomial-time approximation scheme for the weakly NP-hard weighted problem. Our single-machine algorithm can be used repeatedly to schedu
盖他为秘密
发表于 2025-3-30 15:17:27
Fragile Complexity of Adaptive Algorithms . is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity . and .. Deterministic sorting has fragile complexity . but it has fragile complexity . regardless of the number of runs.
thalamus
发表于 2025-3-30 19:54:13
FPT and Kernelization Algorithms for the Induced Tree Problem does not admit an . time algorithm. Afterwards, we use Courcelle’s Theorem to prove tractability under cliquewidth, which prompts our investigation into which parameterizations admit single exponential algorithms; we show that such algorithms exist for the unrelated parameterizations treewidth, dis
Brain-Waves
发表于 2025-3-30 23:25:48
A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGsar if its underlying undirected graph is planar) directed graphs is unknown.. We resolve this gap by showing that . is W-hard parameterized by the number . of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA ’03, SIDMA
离开
发表于 2025-3-31 02:21:26
Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-exponential Approximationo .. We finally show that this time-approximation trade-off is tight, up to an arbitrarily small constant in the second exponent: under the randomized ETH, and for any ratio . and ., no algorithm can output an .-approximation in time .. Hence, we completely characterize the approximability of the pr
Isolate
发表于 2025-3-31 08:29:07
On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineeringletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, outperforming a standard CPLEX solver in most instances of an established biological test data set.
Ardent
发表于 2025-3-31 11:31:20
http://reply.papertrans.cn/16/1532/153110/153110_57.png