Lacunar-Stroke
发表于 2025-3-27 00:21:00
http://reply.papertrans.cn/17/1605/160429/160429_31.png
沙漠
发表于 2025-3-27 02:32:39
http://reply.papertrans.cn/17/1605/160429/160429_32.png
跑过
发表于 2025-3-27 07:03:49
,Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems, holds for computationally equivalent .. Our lower bound matches the approximation provided by a trivial algorithm..Our results imply conditional hardness of approximating Maximum Stable Matching with Ties and Incomplete Lists with a constant better than ., which also matches the best known approximation algorithm.
新手
发表于 2025-3-27 12:41:38
http://reply.papertrans.cn/17/1605/160429/160429_34.png
hair-bulb
发表于 2025-3-27 16:22:25
,Constant Factor Approximation for Tracking Paths and Fault Tolerant Feedback Vertex Set,rackers in each path from . to . is unique. In this work, we derive a factor 66-approximation algorithm for . in weighted graphs and a factor 4-approximation algorithm if the input is unweighted. This is the first constant factor approximation for this problem. While doing so, we also study approxim
forebear
发表于 2025-3-27 20:27:00
http://reply.papertrans.cn/17/1605/160429/160429_36.png
Feigned
发表于 2025-3-28 00:47:38
,Tight Inapproximability of Minimum Maximal Matching on Bipartite Graphs and Related Problems,oximate with any constant smaller than 2 even in bipartite graphs, assuming either of two stronger variants of Unique Games Conjecture. The bound also holds for computationally equivalent .. Our lower bound matches the approximation provided by a trivial algorithm..Our results imply conditional hard
领先
发表于 2025-3-28 04:59:40
http://reply.papertrans.cn/17/1605/160429/160429_38.png
逃避责任
发表于 2025-3-28 10:12:36
The Traveling ,-Median Problem: Approximating Optimal Network Coverage,orizon of . steps. The agents start and end at designated nodes, and in each step can hop to an adjacent node to improve coverage. At each time step, we evaluate the coverage cost as the total connection cost of each node to its closest median. Our goal is to minimize the sum of the coverage costs o
Decongestant
发表于 2025-3-28 14:26:14
EPTAS for Load Balancing Problem on Parallel Machines with a Non-renewable Resource, on parallel uniformly related machines. The input defines the speed of machines, size of jobs, the quantity of resource required by the jobs, the replenished quantities, and replenishment dates of the resource. Every job can start processing only after the required quantity of the resource is alloc