珐琅
发表于 2025-3-23 11:23:06
http://reply.papertrans.cn/17/1605/160425/160425_11.png
整体
发表于 2025-3-23 14:51:27
Precedence-Constrained Scheduling and Min-Sum Set Cover, set cover. For min-sum set cover, Feige, Lovàsz and Tetali [.] showed that the greedy algorithm has an approximation guarantee of 4, and obtaining a better approximation ratio is NP-hard. For precedence-constrained min-sum set cover, McClintock, Mestre and Wirth [.] proposed an .-approximation algo
aristocracy
发表于 2025-3-23 20:59:34
http://reply.papertrans.cn/17/1605/160425/160425_13.png
运动吧
发表于 2025-3-24 00:08:38
Greedy Is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs,two problems are in close analogy but the objective functions are different. We show that the greedy algorithm is an optimal online algorithm for both problems. Typically, an online algorithm is proved to be an optimal online algorithm through bounding its competitive ratio and showing a lower bound
SPECT
发表于 2025-3-24 05:18:42
http://reply.papertrans.cn/17/1605/160425/160425_15.png
河流
发表于 2025-3-24 10:30:17
Conference proceedings 2020A 2019, held in Munich, Germany, in September 2019 as part of ALGO 2019..The 16 revised full papers presented together with one invited paper in this book were carefully reviewed and selected from 38 submissions. Topics of interest for WAOA 2018 were: graph algorithms; inapproximability results; net
痛恨
发表于 2025-3-24 12:44:37
Conference proceedings 2020problems; algorithmic game theory; algorithmic trading; coloring and partitioning; competitive analysis; computational advertising; computational finance; cuts and connectivity; geometric problems; mechanism design; resource augmentation; and real-world applications..
granite
发表于 2025-3-24 18:52:21
https://doi.org/10.1007/978-3-662-33025-8 maximum demand value. They also found (implicitly) an instance of the . with .. Recently, Skutella [.] improved these bounds by showing that ., and there exists an instance with .. We contribute to this line of research by showing that .. We also take a first step towards lower and upper bounds for small instances.
Constant
发表于 2025-3-24 19:26:28
,Neuere Arbeiten über Variola und Vaccine,hat (i) the two instances admit the same optimal offline schedule; (ii) the cost of the online algorithm is at least that of the greedy algorithm on the respective job instance. With these properties, we can show that the competitive ratio of the greedy algorithm is the smallest possible.
纬度
发表于 2025-3-25 00:41:22
http://reply.papertrans.cn/17/1605/160425/160425_20.png