標(biāo)題: Titlebook: Approximation and Online Algorithms; 17th International W Evripidis Bampis,Nicole Megow Conference proceedings 2020 Springer Nature Switzer [打印本頁] 作者: 宗派 時間: 2025-3-21 16:56
書目名稱Approximation and Online Algorithms影響因子(影響力)
書目名稱Approximation and Online Algorithms影響因子(影響力)學(xué)科排名
書目名稱Approximation and Online Algorithms網(wǎng)絡(luò)公開度
書目名稱Approximation and Online Algorithms網(wǎng)絡(luò)公開度學(xué)科排名
書目名稱Approximation and Online Algorithms被引頻次
書目名稱Approximation and Online Algorithms被引頻次學(xué)科排名
書目名稱Approximation and Online Algorithms年度引用
書目名稱Approximation and Online Algorithms年度引用學(xué)科排名
書目名稱Approximation and Online Algorithms讀者反饋
書目名稱Approximation and Online Algorithms讀者反饋學(xué)科排名
作者: 不溶解 時間: 2025-3-22 00:18 作者: 你正派 時間: 2025-3-22 03:04
,Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(,,?,)-Cutsmost . edges are blocked. The traveller, guided by a strategy, sees an edge is blocked when he visits one of its endpoints. A major result established by Westphal is that the competitive ratio of any deterministic strategy for this problem is at least .. . and . strategies achieve this bound..We ref作者: 不成比例 時間: 2025-3-22 07:46
Robust Online Algorithms for Certain Dynamic Packing Problems, of competitive algorithms for dynamic problems, where objects can also depart from the instance. In this work, we give a general framework to obtain so called robust online algorithms for a variety of dynamic problems: these online algorithms achieve an asymptotic competitive ratio of . with migrat作者: Infusion 時間: 2025-3-22 10:21
Approximation Results for Makespan Minimization with Budgeted Uncertainty, the model we consider, which goes back to?[.], once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs’ processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimi作者: 環(huán)形 時間: 2025-3-22 15:51
Streaming Algorithms for Bin Packing and Vector Scheduling,rial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the co作者: –FER 時間: 2025-3-22 18:06
An Improved Upper Bound for the Ring Loading Problem,d theorists alike. Given an undirected cycle on . nodes together with non-negative demands between any pair of nodes, the . asks for an unsplittable routing of the demands such that the maximum cumulated demand on any edge is minimized. Let . be the value of such a solution. In the relaxed version o作者: indemnify 時間: 2025-3-22 22:01 作者: 小口啜飲 時間: 2025-3-23 04:12 作者: Vital-Signs 時間: 2025-3-23 07:32
On the Cycle Augmentation Problem: Hardness and Approximation Algorithms,links of minimum cardinality whose addition to the graph makes it .-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case . (a.k.a. the Tree Augmentation Problem or TAP) or . (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-作者: 琺瑯 時間: 2025-3-23 11:23 作者: 整體 時間: 2025-3-23 14:51
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 作者: 運動吧 時間: 2025-3-24 00:08
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 作者: 河流 時間: 2025-3-24 10:30
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
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
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
,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 作者: 狗舍 時間: 2025-3-25 04:12
Greedy Is Optimal for Online Restricted Assignment and Smart Grid Scheduling for Unit Size Jobs,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.作者: insular 時間: 2025-3-25 10:13 作者: 永久 時間: 2025-3-25 11:46 作者: 種族被根除 時間: 2025-3-25 16:02
https://doi.org/10.1007/978-3-662-33025-8ze the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a 3-approximation algorithm and an inapproximability ratio of . for the case of unrelated machines.作者: 極大痛苦 時間: 2025-3-25 22:11
0302-9743 ithms, WAOA 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 re作者: Anticonvulsants 時間: 2025-3-26 03:55
Terrain-Like Graphs: PTASs for Guarding Weakly-Visible Polygons and Terrains,om its vertices. We also present PTASs for continuously guarding the boundary of a WV-polygon or WV-terrain, either from its vertices, or, for a WV-terrain, from arbitrary points on the terrain. Finally, we compare between terrain-like graphs and . graphs, and also observe that both families admit PTASs for ..作者: 把…比做 時間: 2025-3-26 05:22
,Improved Deterministic Strategy for the Canadian Traveller Problem Exploiting Small Max-(,,?,)-Cutsine this analysis by focusing on graphs with a maximum (.,?.)-cut size . less than .. A strategy called . is proposed and its competitive ratio is . when . which is strictly less than .. Moreover, when ., the competitive ratio of . is . and is optimal. Therefore, . improves the competitiveness of the deterministic strategies known up?to now.作者: maculated 時間: 2025-3-26 09:50 作者: BUDGE 時間: 2025-3-26 16:25 作者: 煩躁的女人 時間: 2025-3-26 19:00
Fair Coresets and Streaming Algorithms for Fair ,-means,se of two colors (and exact balances). Furthermore, we extend techniques due to Chierichetti et al.?[.] to obtain an approximation algorithm for .-means, which leads to a constant factor algorithm in the streaming model when combined with the coreset.作者: 類人猿 時間: 2025-3-26 22:40 作者: FISC 時間: 2025-3-27 03:51 作者: Brocas-Area 時間: 2025-3-27 07:36
,über Tuberkuloseschutzimpfungen, is .. We present a local-search-based PTAS for . in terrain-like graphs. Then, we observe that, besides the visibility graphs of .-monotone terrains which are terrain-like, so are the visibility graphs of . and ., immediately implying a PTAS for guarding the vertices of such a polygon or terrain fr作者: myocardium 時間: 2025-3-27 09:35 作者: Excise 時間: 2025-3-27 16:06
https://doi.org/10.1007/978-3-662-33025-8most . edges are blocked. The traveller, guided by a strategy, sees an edge is blocked when he visits one of its endpoints. A major result established by Westphal is that the competitive ratio of any deterministic strategy for this problem is at least .. . and . strategies achieve this bound..We ref作者: Paradox 時間: 2025-3-27 21:17
https://doi.org/10.1007/978-3-662-33025-8 of competitive algorithms for dynamic problems, where objects can also depart from the instance. In this work, we give a general framework to obtain so called robust online algorithms for a variety of dynamic problems: these online algorithms achieve an asymptotic competitive ratio of . with migrat作者: 出生 時間: 2025-3-28 01:10
https://doi.org/10.1007/978-3-662-33025-8 the model we consider, which goes back to?[.], once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs’ processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimi作者: carotenoids 時間: 2025-3-28 02:05
https://doi.org/10.1007/978-3-662-33025-8rial optimization. These are well understood in the traditional online and offline cases, but have been less well-studied when the volume of the input is truly massive, and cannot even be read into memory. This is captured by the streaming model of computation, where the aim is to approximate the co作者: inflate 時間: 2025-3-28 07:16
https://doi.org/10.1007/978-3-662-33025-8d theorists alike. Given an undirected cycle on . nodes together with non-negative demands between any pair of nodes, the . asks for an unsplittable routing of the demands such that the maximum cumulated demand on any edge is minimized. Let . be the value of such a solution. In the relaxed version o作者: EXCEL 時間: 2025-3-28 13:15
https://doi.org/10.1007/978-3-642-92389-0nts forms a .-.. For any given time and input sequence, the overall performance is determined by the best of the . individual total results. Problems of this type have been considered for online makespan minimization; they are also related to optimization with . on future events, i.e., a number of b作者: 內(nèi)疚 時間: 2025-3-28 17:46
https://doi.org/10.1007/978-3-642-92389-0points in the Euclidean space. In order to reduce communication costs, the positions of the servers can be adapted by a limited distance . per round for each server. The costs are measured similar to the classical Page Migration Problem, i.e., answering a request induces costs proportional to the di作者: 大火 時間: 2025-3-28 20:00
,Wirksame Eiwei?k?rper und Peptide,links of minimum cardinality whose addition to the graph makes it .-edge-connected. There is an approximation preserving reduction from the mentioned problem to the case . (a.k.a. the Tree Augmentation Problem or TAP) or . (a.k.a. the Cactus Augmentation Problem or CacAP). While several better-than-作者: Keratectomy 時間: 2025-3-29 00:46 作者: 遺忘 時間: 2025-3-29 03:16
Studie zur Serologie der Influenza, 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作者: 元音 時間: 2025-3-29 08:06
https://doi.org/10.1007/978-3-642-92404-0g problem, the objective function incorporates the distance of a point to its .-th closest center chosen in the solution. We combine these two orthogonal generalizations, and consider Fault Tolerant Clustering with Outliers problems for various clustering objectives, such as .-center, .-median, and 作者: Femine 時間: 2025-3-29 12:22
,Neuere Arbeiten über Variola und Vaccine,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作者: Canyon 時間: 2025-3-29 18:52
Die Gewinnung der Schutzpockenlymphe, required to be balanced with respect to it (to counteract any form of data-inherent bias). Previous algorithms for fair clustering do not scale well. We show how to model and compute so-called coresets for fair clustering problems, which can be used to significantly reduce the input data size. We p作者: Hippocampus 時間: 2025-3-29 20:17
A New Lower Bound for Classic Online Bin Packing,time the advantage of branching and the applicability of full adaptivity in the design of lower bounds for the classic online bin packing problem. We apply a new method for weight based analysis, which is usually applied only in proofs of upper bounds. The values of previous lower bounds were approximately 1.5401 and 1.5403.作者: 匍匐 時間: 2025-3-30 03:42
Approximate Strong Edge-Colouring of Unit Disk Graphs,rate, Kumar, Marathe, Thite, and Thulasidasan?[.]. We also show that strong edge-6-colourability is NP-complete for the class of unit disk graphs. Thus there is no polynomial-time .-approximation unless P?=?NP.作者: 協(xié)議 時間: 2025-3-30 07:22 作者: 口音在加重 時間: 2025-3-30 10:18 作者: Gentry 時間: 2025-3-30 14:50 作者: Mucosa 時間: 2025-3-30 19:24 作者: 伸展 時間: 2025-3-30 20:50
https://doi.org/10.1007/978-3-030-39479-0approximation algorithms; approximation ratios; approximation theory; artificial intelligence; bin packi作者: Blanch 時間: 2025-3-31 03:34 作者: 逗留 時間: 2025-3-31 07:10
Robust Online Algorithms for Certain Dynamic Packing Problems,hm..While these criteria are naturally fulfilled by many dynamic problems, they are especially suited for packing problems. In order to show the usefulness of our approach in this area, we improve upon the best known robust algorithms for the dynamic versions of generalizations of Strip Packing and 作者: arcane 時間: 2025-3-31 12:33
Streaming Algorithms for Bin Packing and Vector Scheduling, Our algorithm implies a streaming .-approximation for . in . dimensions, running in space .. For the related . problem, we show how to construct an input summary in space . that preserves the optimum value up?to a factor of ., where . is the number of identical machines.
