检索结果-内蒙古大学图书馆

Point enclosure problem for homothetic polygons

THEORETICAL COMPUTER SCIENCE 2025年 1030卷

作者： Akram, Waseem Saxena, Sanjeev Indian Inst Technol Dept Comp Sci & Engn Kanpur 208016 India

In this paper, we investigate the following problem: "given a set S of n homothetic polygons, preprocess S to efficiently report all the polygons of S containing a query point." A set of polygons is said to be homothetic if each polygon can be obtained from any other polygon in the set using scaling and translation operations. The problem is a counterpart of the homothetic range search problem discussed by Chazelle and Edelsbrunner (1987) [9]. We show that after preprocessing a set of homothetic polygons with a constant number of vertices, queries can be answered in O (log n + k) optimal time, where k is the output size. The preprocessing takes O(n log n) space and time. We also study the problem in a dynamic setting where insertion and deletion operations are allowed. The results we obtain also hold for c-oriented triangles, where c is a fixed constant.

关键词： Geometric intersection algorithms Data structures dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic ((1+𝜖) ln 𝑛)-Approximation algorithms for Minimum Set Cover and Dominating Set 2023

Dynamic ((1+𝜖) ln 𝑛)-Approximation Algorithms for Mini...

引用

Proceedings of the 55th Annual ACM Symposium on Theory of Computing

作者： Shay Solomon Amitai Uzrad Tel Aviv University Israel

ISBN: (纸本)9781450399135

The minimum set cover (MSC) problem admits two classic algorithms: a greedy lnn-approximation and a primal-dual f-approximation, where n is the universe size and f is the maximum frequency of an element. Both algorithms are simple and efficient, and remarkably — one cannot improve these approximations under hardness results by more than a factor of (1+є), for any constant є > 0. In their pioneering work, Gupta et al. [STOC’17] showed that the greedy algorithm can be dynamized to achieve O(logn)-approximation with update time O(f logn). Building on this result, Hjuler et al. [STACS’18] dynamized the greedy minimum dominating set (MDS) algorithm, achieving a similar approximation with update time O(Δ logn) (the analog of O(f logn)), albeit for unweighted instances. The approximations of both algorithms, which are the state-of-the-art, exceed the static lnn-approximation by a rather large constant factor. In sharp contrast, the current best dynamic primal-dual MSC algorithms, by Bhattacharya et al. [SODA’21] and Assadi-Solomon [ESA’21], both with update time O(f2) — exceed the static f-approximation by a factor of (at most) 1+є, for any є > 0. This paper aims to bridge the gap between the best approximation factor of the dynamic greedy MSC and MDS algorithms and the static lnn bound. We present dynamic algorithms for weighted greedy MSC and MDS with approximation (1+є)lnn for any є > 0, while achieving the same update time (ignoring dependencies on є) of the best previous algorithms (with approximation significantly larger than lnn). Moreover, we prove that the same algorithms achieve O(min{ logn, logC }) amortized recourse; the recourse measures the number of changes to the maintained structure per update step, and the cost of each set lies in the range [1/C,1].

关键词： dynamic algorithms set cover data structures dominating set

来源：评论

学校读者我要写书评

暂无评论

dynamic Deterministic Constant-Approximate Distance Oracles with n^ε Worst-Case Update Time 65

Dynamic Deterministic Constant-Approximate Distance Oracles ...

引用

65th Symposium on Foundations of Computer Science

作者： Haeupler, Bernhard Long, Yaowei Saranurak, Thatchaphol Univ Sofia St Kliment Ohridski INSAIT Sofia Bulgaria Swiss Fed Inst Technol Zurich Switzerland Univ Michigan Ann Arbor MI USA

ISBN: (纸本)9798331516758;9798331516741

We present a new distance oracle in the fully dynamic setting: given a weighted undirected graph G = (V;E) with n vertices undergoing both edge insertions and deletions, and an arbitrary parameter epsilon is an element of [1/log(c) n, 1] where c > 0 is a small constant, we can deterministically maintain a data structure with O(n(c)) worst-case update time that, given any pair of vertices (u;v), returns a 2(poly(1/epsilon)) -approximate distance between u and v in poly(1/epsilon) log log n query time. Our algorithm significantly advances the state-of-the-art in two aspects, both for fully dynamic algorithms and even decremental algorithms. First, no existing algorithm with worst-case update time guarantees a o(n)-approximation while also achieving an n(2-Omega(1)) update and n(o(1)) query time, while our algorithm offers a constant O-epsilon(1)-approximation with O(n(epsilon)) update time and O-epsilon(log log n) query time. Second, even if amortized update time is allowed, it is the first deterministic constant-approximation algorithm with n(1-Omega(1)) update and query time. The best result in this direction is the recent deterministic distance oracle by Chuzhoy and Zhang [STOC 2023] which achieves an approximation of (log log n)(2O(1/epsilon 3)) with amortized update time of O(n(epsilon)) and query time of 2(poly(1/epsilon)) log n log log n. We obtain the result by dynamizing tools related to lengthconstrained expanders [Haeupler-Racke-Ghaffari, STOC 2022;Haeupler-Hershkowitz-Tan, FOCS 2024]. Our technique completely bypasses the 40-year-old Even-Shiloach tree, which has remained the most pervasive tool in the area but is inherently amortized.

关键词： Graph algorithms dynamic algorithms Distance Oracles

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic k-Clustering with Fast Update Time and Small Recourse 65

Fully Dynamic k-Clustering with Fast Update Time and Small R...

引用

65th Symposium on Foundations of Computer Science

作者： Bhattacharya, Sayan Costa, Martin Garg, Naveen Lattanzi, Silvio Parotsidis, Nikos Univ Warwick Coventry W Midlands England IIT Delhi Delhi India Google Res Zurich Switzerland

ISBN: (纸本)9798331516758;9798331516741

In the dynamic metric k-median problem, we wish to maintain a set of k centers S subset of V in an input metric space (V, d) that gets updated via point insertions/deletions, so as to minimize the objective Sigma(x is an element of V) min(y is an element of S) d(x, y). The quality of a dynamic algorithm is measured in terms of its approximation ratio, "recourse" (the number of changes in S per update) and "update time" (the time it takes to handle an update). The ultimate goal in this line of research is to obtain a dynamic O(1) approximation algorithm with (O) over tilde (1) recourse and (O) over tilde (k) update time. dynamic k-median is a canonical example of a class of problems known as dynamic k-clustering, that has received significant attention in recent years [Fichtenberger et al, SODA'21], [Bateni et al, SODA'23], [Lacki et al, SODA'24]. To the best of our knowledge, however, all these previous papers either attempt to minimize the algorithm's recourse while ignoring its update time, or minimize the algorithm's update time while ignoring its recourse. For dynamic k-median in particular, the state-of-the-art results get (O) over tilde (k(2)) update time and O(k) recourse [Cohen-Addad et al, ICML'19], [Henzinger and Kale, ESA'20], [Bhattacharya et al, NeurIPS'23]. But, this recourse bound of O(k) can be trivially obtained by recomputing an optimal solution from scratch after every update, provided we ignore the update time. In addition, the update time of (O) over tilde (k(2)) is polynomially far away from the desired bound of (O) over tilde (k). We come arbitrarily close to resolving the main open question on this topic, with the following results. (I) We develop a new framework of randomized local search that is suitable for adaptation in a dynamic setting. For every epsilon > 0, this gives us a dynamic k-median algorithm with O(1/epsilon) approximation ratio, (O) over tilde (k(epsilon)) recourse and (O) over tilde (k(1+epsilon)) update time. This framework

关键词： dynamic algorithms clustering k-median k-means fully dynamic

来源：评论

学校读者我要写书评

暂无评论

A Lossless Deamortization for dynamic Greedy Set Cover 65

A Lossless Deamortization for Dynamic Greedy Set Cover

引用

65th Symposium on Foundations of Computer Science

作者： Solomon, Shay Uzrad, Amitai Zhang, Tianyi Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9798331516758;9798331516741

The dynamic set cover problem has been subject to growing research attention in recent years. In this problem, we are given as input a dynamic universe of at most n elements and a fixed collection of m sets, where each element appears in a most f sets and the cost of each set is in [1/C, 1], and the goal is to efficiently maintain an approximate minimum set cover under element updates. Two algorithms that dynamize the classic greedy algorithm are known, providing O(log n) and ((1+epsilon) ln n)-approximation with amortized update times O(f log n) and O(f log n/epsilon(5)), respectively [GKKP (STOC'17);SU (STOC'23)]. The question of whether one can get approximation O(log n) (or even worse) with low worst-case update time has remained open - only the naive O(f . n) time bound is known, even for unweighted instances. In this work we devise the first amortized greedy algorithm that is amenable to an efficient deamortization, and also develop a lossless deamortization approach suitable for the set cover problem, the combination of which yields a ((1 + epsilon) ln n)-approximation algorithm with a worst-case update time of O(f log n/epsilon(2)). Our worst-case time bound - the first to break the naive O(f.n) bound - matches the previous best amortized bound, and actually improves its epsilon-dependence. Further, to demonstrate the applicability of our deamortization approach, we employ it, in conjunction with the primal-dual amortized algorithm of [BHN (FOCS'19)], to obtain a ((1 + epsilon)f)-approximation algorithm with a worst-case update time of O(f log n/epsilon(2)), improving over the previous best bound of O(***(2)(Cn)/epsilon(3)) [BHNW (SODA'21)]. Finally, as direct implications of our results for set cover, we (i) achieve the first nontrivial worst-case update time for the dominating set problem, and (ii) improve the state-of-the-art worst-case update time for the vertex cover problem.

关键词： data structures deamortization dynamic algorithms greedy set cover set cover worst-case update time

来源：评论

学校读者我要写书评

暂无评论

Parallel dynamic Maximal Matching 24

Parallel Dynamic Maximal Matching

引用

36th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Ghaffari, Mohsen Trygub, Anton MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9798400704161

We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion or insertion updates to the graph, our parallel algorithm adjusts the maximal matching to these updates in poly(log n) depth and using poly(log n) amortized work per update. That is, the amortized work for processing a batch of k updates is k poly(log n), while all this work is done in poly(log n) depth, with high probability. This can be seen as a parallel counterpart of the sequential dynamic algorithms for constant-approximate and maximal matching [Onak and Rubinfeld STOC'10;Baswana, Gupta, and Sen FOCS'11;and Solomon FOCS'16]. Our algorithm readily generalizes to maximal matching in hypergraphs of rank r-where each hyperedge has at most r endpoints-with a poly(r) increase in work, while retaining the poly(log n) depth.

关键词： Parallel algorithms dynamic algorithms maximal matching

来源：评论

学校读者我要写书评

暂无评论

A Comprehensive Study of Load Balancing Approaches in Real-Time Multi-Core Systems for Mixed Real-Time Tasks

引用

IEEE ACCESS 2024年 12卷 53373-53395页

作者： Jadon, Shruti Kannan, Pradyuman Kavedi Kalaria, Urmil Varsha, K. R. Gupta, Karthik Honnavalli, Prasad B. PES Univ Dept Comp Sci Engn Bengaluru 560085 India

Real-time systems are becoming pervasive with the growing global connectivity and rising consumer demands. The need for real-time processing has become a crucial part of many business applications worldwide. A key factor that determines the time taken for an application to give out the result hinges on its ability to prioritize, manage, and execute real-time workloads. However, there are several difficulties and constraints connected with implementing tasks in a real-time context. This research study primarily focuses on load balancing for mixed real-time tasks on a multi-core system, one of the major challenges for executing real-time workloads. The purpose of load balancing is to distribute the load evenly among the processor(s) and maximize their utility while minimizing overall execution time. The goal of this paper is to present a critical analysis of existing load balancing techniques for both periodic and aperiodic tasks. The paper explores several factors including throughput, performance, migration time, response time, overhead, resource utilization, scalability, fault tolerance, power efficiency, and other variables that play a crucial role in assessing the efficacy of load balancing in real-time systems. The proposed has contributed in four folds. Firstly, the state-of-the-art of various load balancing algorithms are discussed followed by the architecture involved in real-time multi-core systems. Later, different load balancing based scheduling algorithms were compared on the basis of different schemas and metrics for algorithm evaluation is also provided. Finally, the paper also identifies areas that warrant further exploration or investigation, suggesting potential avenues for future research, and highlighting emerging trends or developments that may shape the field.

关键词： Task analysis Real-time systems Heuristic algorithms Scheduling Load management Partitioning algorithms Scheduling algorithms real-time systems priority-driven algorithms EDF (earliest deadline first) RM (rate-monotonic) LBPSA (load balanced partitioning and scheduling algorithm) homogeneous multi-core heterogeneous multi-core static algorithms dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic Kernels for Hitting Sets and Set Packing

引用

ALGORITHMICA 2022年第11期84卷 3459-3488页

作者： Bannach, Max Heinrich, Zacharias Reischuk, Ruediger Tantau, Till Univ Lubeck Inst Theoret Informat Ratzeburger Allee 160 D-23562 Lubeck Germany

Computing small kernels for the hitting set problem is a well-studied computational problem where we are given a hypergraph with n vertices and m hyperedges, each of size d for some small constant d, and a parameter k. The task is to compute a new hypergraph, called a kernel, whose size is polynomial with respect to the parameter k and which has a size-k hitting set if, and only if, the original hypergraph has one. State-of-the-art algorithms compute kernels of size k(d) (which is a polynomial as d is a constant), and they do so in time m . 2(d) poly(d) for a small polynomial poly(d) (which is linear in the hypergraph size for d fixed). We generalize this task to the dynamic setting where hyperedges may continuously be added or deleted and one constantly has to keep track of a size-k(d) kernel. This paper presents a deterministic solution with worst-case time 3(d) poly(d) for updating the kernel upon inserts and time 5(d) poly(d) for updates upon deletions. These bounds nearly match the time 2(d) poly(d) needed by the best static algorithm per hyperedge. Let us stress that for constant d our algorithm maintains a hitting set kernel with constant, deterministic, worst-case update time that is independent of n, m, and the parameter k. As a consequence, we also get a deterministic dynamic algorithm for keeping track of size-k hitting sets in d-hypergraphs with update times O(1) and query times O(c(k)) where c = d - 1 + O(1/d) equals the best base known for the static setting.

关键词： Kernelization dynamic algorithms Hitting Set Set Packings

来源：评论

学校读者我要写书评

暂无评论

Visibility polygons and visibility graphs among dynamic polygonal obstacles in the plane

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第4期44卷 3056-3082页

作者： Agrawal, Sanjana Inkulu, R. Dept Comp Sci & Engn IIT Gauhati India

We devise an algorithm for maintaining the visibility polygon of any query point in a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update the data structures that store the visibility polygon of the query point. After preprocessing the initial input polygonal domain to build a few data structures, our algorithm takes O(k(lg vertical bar V P-P' (q) vertical bar) + (lg n')(2) + h) (resp. O(k (lg n')(2) + (lg vertical bar V P-P' (q) vertical bar) + h)) worst-case time to update data structures that store visibility polygon V P-P' (q) of a query point q when any vertex v is inserted to (resp. deleted from) any obstacle of the current polygonal domain P'. Here, n' is the number of vertices of P', h is the number of obstacles in P', V P-P', (q) is the visibility polygon of q in P' (vertical bar V P-P' (q) vertical bar is the number of vertices of V P-P' (q)), and k is the number of combinatorial changes in V P-P'(q) due to the insertion (resp. deletion) of v. As an application of the above algorithm, we also devise an algorithm for maintaining the visibility graph of a dynamic polygonal domain, i.e., as the polygonal domain is modified with vertex insertions and deletions to its obstacles, we update data structures that store the visibility graph of the polygonal domain. After preprocessing the initial input polygonal domain, our dynamic algorithm takes O(k(lg n')(2) + h) (resp. O(k (lg n')(2) + h) worst-case time to update data structures that store the visibility graph when any vertex v is inserted to (resp. deleted from) any obstacle of the current polygonal domain P'. Here, n' is the number of vertices of P', h is the number of obstacles in P', and k is the number of combinatorial changes in the visibility graph of P' due to the insertion (resp. deletion) of v.

关键词： Computational Geometry Visibility dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic Parameterized Problems and algorithms

引用

ACM TRANSACTIONS ON algorithms 2020年第4期16卷 1–46页

作者： Alman, Josh Mnich, Matthias Williams, Virginia Vassilevska MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA Harvard Univ Cambridge MA 02138 USA TU Hamburg Inst Algorithms & Complex D-21071 Hamburg Germany

Fixed-parameter algorithms and kernelization are two powerful methods to solve NP-hard problems. Yet so far those algorithms have been largely restricted to static inputs. In this article, we provide fixed-parameter algorithms and kernelizations for fundamental NP-hard problems with dynamic inputs. We consider a variety of parameterized graph and hitting set problems that are known to have f(k)n(1+o(1)) time algorithms on inputs of size n, and we consider the question of whether there is a data structure that supports small updates (such as edge/vertex/set/element insertions and deletions) with an update time of.(k)n(o(1));such an update time would be essentially optimal. Update and query times independent of n are particularly desirable. Among many other results, we show that FEEDBACK VERTEX SET and k-PATH admit dynamic algorithms with f (k) log(O(1)) n update and query times for some function f depending on the solution size k only. We complement our positive results by several conditional and unconditional lower bounds. For example, we show that unlike their undirected counterparts, DIRECTED FEEDBACK VERTEX SET and DIRECTED k-PATH do not admit dynamic algorithms with n(o(1)) update and query times even for constant solution sizes k <= 3, assuming popular hardness hypotheses. We also show that unconditionally, in the cell probe model, DIRECTED FEEDBACK VERTEX SET cannot be solved with update time that is purely a function of k.

关键词： Fixed-parameter algorithms dynamic algorithms cell probe lower bounds

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：