四牛在弯曲
发表于 2025-3-23 10:05:59
http://reply.papertrans.cn/17/1605/160456/160456_11.png
grenade
发表于 2025-3-23 17:24:23
http://reply.papertrans.cn/17/1605/160456/160456_12.png
单色
发表于 2025-3-23 19:58:49
Packing Element-Disjoint Steiner Treesre . denotes |.|. We present a randomized .(log.)-approximation algorithm for this problem, thus matching the hardness lower bound. Moreover, we show a tight upper bound of .(log.) on the integrality ratio of a natural linear programming relaxation.
enormous
发表于 2025-3-24 01:57:47
The Complexity of Making Unique Choices: Approximating 1-in-, SATo have size exactly .. Our results show that the 1-in-.SAT problem exhibits some rather peculiar phenomena in the realm of constraint satisfaction problems. Specifically, the problem becomes . easier to approximate with perfect completeness as well as when negations of literals are not allowed.
信徒
发表于 2025-3-24 04:31:06
Approximating the Distortionstrating that, when the distortion is large, it is hard to approximate within large factors, even for 1-dimensional point sets. We also introduce additive distortion, and show that it can be easily approximated within a factor of two.
轻打
发表于 2025-3-24 07:54:10
http://reply.papertrans.cn/17/1605/160456/160456_16.png
MORPH
发表于 2025-3-24 13:59:24
The anaphylatoxin-forming system,ting..We also consider the problem of finding an ultrametric . that minimizes ..elative: the sum of the factors by which each input distance is stretched. For the latter problem, we give a factor .(log..) approximation.
Minuet
发表于 2025-3-24 18:37:34
https://doi.org/10.1007/BFb0115462ll as all predicates on 2. binary inputs, that have at most 2.+1 accepting inputs..We also prove a large number of predicates to be approximation resistant. In particular, all predicates of arity 2.+.. with less than . non-accepting inputs are proved to be approximation resistant, as well as almost 1/5 of the predicates on four binary inputs.
badinage
发表于 2025-3-24 22:21:28
K. Kramer,O. Krayer,H. H. Weber.... The cost of the cover is given by ∑ ...... Our objective is to find a cover with minimum cost. We provide an algorithm with the same performance guarantee as for regular partial vertex cover. In this case no algorithm for the problem was known.
ALT
发表于 2025-3-25 01:00:05
http://reply.papertrans.cn/17/1605/160456/160456_20.png