Perineum
发表于 2025-3-23 11:19:02
An Approximation Scheme for Terrain Guardinggorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled and Mustafa and Ray . Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.
Pituitary-Gland
发表于 2025-3-23 16:03:13
http://reply.papertrans.cn/17/1605/160461/160461_12.png
cyanosis
发表于 2025-3-23 20:07:53
Improved Inapproximability Results for Maximum ,-Colorable Subgraphrs so that a maximum fraction of edges are properly colored (i.e. their endpoints receive different colors). A random .-coloring properly colors an expected fraction . of edges. We prove that given a graph promised to be .-colorable, it is NP-hard to find a .-coloring that properly colors more than
humectant
发表于 2025-3-23 23:42:43
Improved Absolute Approximation Ratios for Two-Dimensional Packing Problemsr bins or a strip of minimal height, respectively. All packings have to be non-overlapping and orthogonal, i.e., axis-parallel. Our algorithm for strip packing has an absolute approximation ratio of 1.9396 and is the first algorithm to break the approximation ratio of 2 which was established more th
conceal
发表于 2025-3-24 04:43:40
http://reply.papertrans.cn/17/1605/160461/160461_15.png
ATRIA
发表于 2025-3-24 09:05:45
On Hardness of Pricing Items for Single-Minded Biddersers, each with a budget and an intention to buy a fixed subset of items. Given prices on the items, each buyer buys his subset of items, at the given prices, provided the total price of the subset is at most his budget. The objective of the seller is to determine the prices such that her total profi
规范就好
发表于 2025-3-24 12:43:14
Real-Time Message Routing and Schedulingcheduling decisions. In order for messages to arrive on time, one has to determine a suitable (short) origin-destination path for each message and resolve conflicts between messages whose paths share a communication link of the network. We provide efficient routing strategies yielding origin-destina
检查
发表于 2025-3-24 17:45:18
http://reply.papertrans.cn/17/1605/160461/160461_18.png
PANIC
发表于 2025-3-24 22:47:30
http://reply.papertrans.cn/17/1605/160461/160461_19.png
冰河期
发表于 2025-3-25 02:12:35
Structure Theory for p.m.p. Actions is to find a maximum cardinality set of element-disjoint trees such that each tree contains every terminal node. An . means a non-terminal node or an edge. (Thus, each non-terminal node and each edge must be in at most one of the trees.) We show that the problem is .-hard when there are only three