溃烂
发表于 2025-3-23 12:03:31
http://reply.papertrans.cn/17/1663/166240/166240_11.png
MAIM
发表于 2025-3-23 17:02:35
Exact Weight Subgraphs and the ,-Sum Conjecturest to the minimum-weight and (unweighted) detection versions, which can be solved easily in time .(..). We also show that a faster algorithm for any of the following three problems would yield faster algorithms for the others: 3-., ., and ..
Panther
发表于 2025-3-23 18:51:02
http://reply.papertrans.cn/17/1663/166240/166240_13.png
Paleontology
发表于 2025-3-24 00:35:51
Space–Time Tradeoffs for Subset Sum: An Improved Worst Case Algorithman be almost fully parallelized. Our strategy for dealing with arbitrary instances is to instead inject the randomness into the dissection process itself by working over a carefully selected but random composite modulus, and to introduce explicit space–time controls into the algorithm by means of a “bailout mechanism”.
Anemia
发表于 2025-3-24 05:06:54
Approximation Algorithms for the Joint Replenishment Problem with Deadlineselaxation, giving a lower bound of 1.207, and an upper bound and approximation ratio of 1.574. The best previous upper bound and approximation ratio was 1.667; no lower bound was previously published. For the special case when all demand periods are of equal length we give an upper bound of 1.5, a lower bound of 1.2, and show APX-hardness.
发现
发表于 2025-3-24 09:13:10
A Pseudo-Polynomial Algorithm for Mean Payoff Stochastic Games with Perfect Information and a Few Rae with a few random nodes |..| = .(1), a saddle point in pure stationary strategies can be found in time polynomial in |..| + |..|, the maximum absolute local reward ., and the common denominator of the transition probabilities.
天空
发表于 2025-3-24 11:56:12
https://doi.org/10.1007/978-3-322-94717-8ounting the number of solutions of the CSP is in . (resp., ..-complete)..Also, we conjecture that a CSP instance is testable in sublinear time if its Gaifman graph has bounded treewidth. We confirm the conjecture when a near-unanimity operation is a polymorphism of the CSP.
needle
发表于 2025-3-24 17:25:16
Elementare Integrationsmethoden,ted graphs, respectively, where ..(.) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.
Gudgeon
发表于 2025-3-24 19:07:24
http://reply.papertrans.cn/17/1663/166240/166240_19.png
superfluous
发表于 2025-3-25 00:20:47
Optimal Orthogonal Graph Drawing with Convex Bend Coststed graphs, respectively, where ..(.) denotes the time to compute a minimum-cost flow in a planar network with multiple sources and sinks. Our result is the first polynomial-time bend-optimization algorithm for general 4-planar graphs optimizing over all embeddings. Previous work considers restricted graph classes and unit costs.