半导体
发表于 2025-3-23 10:24:49
Online Scheduling of Jobs with Fixed Start Times on Related Machinesaximizing the total weight of completed jobs. Every job has a size and a weight associated with it. A newly released job must be either assigned to start running immediately on a machine or otherwise it is dropped. It is also possible to drop an already scheduled job, but only completed jobs contrib
confederacy
发表于 2025-3-23 17:16:40
A Systematic Approach to Bound Factor Revealing LPs and Its Application to the Metric and Squared Meand that each such program can be solved by a computer to bound the approximation factor. Obtaining an UPFRP is straightforward, and can be used as an alternative to analytical proofs, that are usually very long and tedious. We apply this technique to the Metric Facility Location Problem (MFLP) and
LAVA
发表于 2025-3-23 21:04:46
http://reply.papertrans.cn/17/1605/160464/160464_13.png
ARC
发表于 2025-3-23 22:33:17
On the NP-Hardness of Max-Not-2 constraints. This, up to the existence of ., matches the approximation ratio obtained by the trivial algorithm that just picks an assignment at random and thus the result is tight. Said equivalently the result proves that Max-NTW is approximation resistant on satisfiable instances and this makes ou
MOTTO
发表于 2025-3-24 03:35:15
http://reply.papertrans.cn/17/1605/160464/160464_15.png
脱毛
发表于 2025-3-24 09:32:24
Approximation Algorithms for Generalized and Variable-Sized Bin Covering. has size ... A bin of type . is said to be covered if the set of items assigned to it has total size of at least ... For earning profit .. a bin of type . has to be covered. The objective is to maximize the total profit. Only the cases .. = .. = 1 (.) and .. = .. (.) have been treated before. We s
Insufficient
发表于 2025-3-24 12:00:42
Approximating Minimum Linear Ordering Problemsh that the sum of the function values for all the suffixes is minimized. This problem generalizes well-known problems such as the Minimum Linear Arrangement, Min Sum Set Cover, Minimum Latency Set Cover, and Multiple Intents Ranking. Extending a result of Feige, Lovász, and Tetali (2004) on Min Sum
Flatter
发表于 2025-3-24 18:54:11
New Approximation Results for Resource Replication Problems of fundamental interest in the areas of P2P networks, sensor networks and ad hoc networks, where optimal placement of replicas is the main bottleneck on performance. We observe that the threshold graph technique, which has been applied to several .-center type problems, yields simple and efficient
宫殿般
发表于 2025-3-24 22:37:32
https://doi.org/10.1007/978-3-642-32512-0NP-hardness; approximation algorithms; graphs; online scheduling; random combinatorial structures; algori
埋伏
发表于 2025-3-25 00:17:58
http://reply.papertrans.cn/17/1605/160464/160464_20.png