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

20th International Symposium on Experimental algorithms, SEA 2022

作者： D’Ascenzo, Andrea D’Emidio, Mattia Flammini, Michele Monaco, Gianpiero Department of Computer Science Information Engineering and Mathematics University of L’Aquila Italy Gran Sasso Science Institute L’Aquila Italy

ISBN: (纸本)9783959772518

We study digraph k-coloring games where agents are vertices of a directed unweighted graph and arcs represent agents’ mutual unidirectional idiosyncrasies or conflicts. Each agent can select one of k different colors, and her payoff in a given state is given by the number of outgoing neighbors with a different color. Such games model lots of strategic real-world scenarios and are related to several fundamental classes of anti-coordination games. Unfortunately, the problem of understanding whether an instance of the game admits a pure Nash equilibrium is NP-complete [33]. Therefore, in the last few years a relevant research focus has been that of designing polynomial time algorithms able to compute approximate Nash equilibria, i.e., states in which no agent, changing her strategy, can improve her payoff by some bounded multiplicative factor. The only two known algorithms in this respect are those in [14]. While they provide theoretical guarantees, their practical performance over real-world instances so far has not been investigated. In this paper, under the further motivation of the lack of practical approximation algorithms for the problem, we experimentally evaluate the above algorithms with the conclusion that, while they were suitably designed for achieving a bounded worst case behavior, they generally have a poor performance. Therefore, we next focus on classical best-response dynamics, and show that, despite of the fact that they might not always converge, they are very effective in practice. In particular, we provide a strong empirical evidence that they outperform existing methods, since surprisingly they quickly converge to exact Nash equilibria in almost all instances arising in practice. This also shows that, while this class of games is known to not always possess pure Nash equilibria, in almost all cases such equilibria exist and can be efficiently computed, even in a distributed uncoordinated way by a decentralized interaction of the agents. © Andrea D

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimally Tracking Labels on an Evolving Tree 34

Optimally Tracking Labels on an Evolving Tree

引用

34th Canadian Conference on Computational Geometry, CCCG 2022

作者： Acharya, Aditya Mount, David M. Department of Computer Science University of Maryland College ParkMD United States Department of Computer Science Institute for Advanced Computer Studies University of Maryland College ParkMD United States

Motivated by the problem of maintaining data structures for a large sets of points that are evolving over the course of time, we consider the problem of maintaining a set of labels assigned to the vertices of a tree. We study the problem in the evolving data framework, where labels continuously change over time due to the action of an agent called the evolver. An algorithm, which can only track these changes by explicitly probing the individual vertices, is tasked with maintaining an approximate sketch of the underlying tree. Such a framework necessitates an algorithm which is fast enough to keep up with the changes, while simultaneously being accurate enough to maintain a close approximation. We present an algorithm that allows for both randomized and adversarial evolution of the data, subject to allowing a constant speedup factor over the evolver. We show that in the limit, it is possible to maintain labels to within an average distance of O(1) of their actual locations. We also present nearly matching lower bounds, both on the distance, and the speed-up factor. © 2022 Yeganeh Bahoo and Konstantinos Georgiou.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive-Adversary-Robust algorithms via Small Copy Tree Embeddings 30

Adaptive-Adversary-Robust Algorithms via Small Copy Tree Emb...

引用

30th Annual European Symposium on algorithms, ESA 2022

作者： Haepler, Bernhard Hershkowitz, D. Ellis Zuzic, Goran Carnegie Mellon University PittsburghPA United States ETH Zürich Switzerland

ISBN: (纸本)9783959772471

Embeddings of graphs into distributions of trees that preserve distances in expectation are a cornerstone of many optimization algorithms. Unfortunately, online or dynamic algorithms which use these embeddings seem inherently randomized and ill-suited against adaptive adversaries. In this paper we provide a new tree embedding which addresses these issues by deterministically embedding a graph into a single tree containing O(log n) copies of each vertex while preserving the connectivity structure of every subgraph and O(log2 n)-approximating the cost of every subgraph. Using this embedding we obtain the first deterministic bicriteria approximation algorithm for the online covering Steiner problem as well as the first poly-log approximations for demand-robust Steiner forest, group Steiner tree and group Steiner forest. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Coded Computation Over Heterogeneous Workers With Random Task Arrivals

引用

IEEE COMMUNICATIONS LETTERS 2021年第7期25卷 2338-2342页

作者： Zhang, Fan Sun, Yuxuan Zhou, Sheng Tsinghua Univ Beijing Natl Res Ctr Informat Sci & Technol Dept Elect Engn Beijing 100084 Peoples R China

Considering the scheduling and allocation of tasks among multiple servers, distributed machine learning faces the problem of the straggler effect as well as system heterogeneity, e.g., the computation time of the slowest worker can be much longer than that of the normal workers. This letter studies the distributed online tasks assignment problem under heterogeneous conditions where different workers have different computing capacities, in order to minimize the task completion time. We consider the task scheduling with random task arrivals, and introduce task cancellation after completion scheme to clear the unfinished parts after the completion of the task to further reduce redundant calculations. To address the challenge of finding the optimal solution, we propose an approximate online algorithm based on convex optimization and time recursion. Simulation results show that the proposed algorithm can reduce the completion delay by over 30x0025;as compared with the one-shot counterpart, and maintain a relatively stable delay in the case of fluctuating arrival rates.

关键词： Task analysis Encoding Delays approximation algorithms Machine learning Computational modeling Sun Coded computation online task assignment heterogeneous system convex optimization

来源：评论

学校读者我要写书评

暂无评论

On the Hardness of Category Tree Construction 25

On the Hardness of Category Tree Construction

引用

25th International Conference on Database Theory, ICDT 2022

作者： Gershtein, Shay Avron, Uri Guy, Ido Milo, Tova Novgorodov, Slava Tel Aviv University Israel Ben-Gurion University of the Negev Beer Sheva Israel eBay Research Netanya Israel

ISBN: (纸本)9783959772235

Category trees, or taxonomies, are rooted trees where each node, called a category, corresponds to a set of related items. The construction of taxonomies has been studied in various domains, including e-commerce, document management, and question answering. Multiple algorithms for automating construction have been proposed, employing a variety of clustering approaches and crowdsourcing. However, no formal model to capture such categorization problems has been devised, and their complexity has not been studied. To address this, we propose in this work a combinatorial model that captures many practical settings and show that the aforementioned empirical approach has been warranted, as we prove strong inapproximability bounds for various problem variants and special cases when the goal is to produce a categorization of the maximum utility. In our model, the input is a set of n weighted item sets that the tree would ideally contain as categories. Each category, rather than perfectly match the corresponding input set, is allowed to exceed a given threshold for a given similarity function. The goal is to produce a tree that maximizes the total weight of the sets for which it contains a matching category. A key parameter is an upper bound on the number of categories an item may belong to, which produces the hardness of the problem, as initially each item may be contained in an arbitrary number of input sets. For this model, we prove inapproximability bounds, of order Θ(√n) or Θ(n), for various problem variants and special cases, loosely justifying the aforementioned heuristic approach. Our work includes reductions based on parameterized randomized constructions that highlight how various problem parameters and properties of the input may affect the hardness. Moreover, for the special case where the category must be identical to the corresponding input set, we devise an algorithm whose approximation guarantee depends solely on a more granular parameter, allowing improved wo

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Asymptotically Optimal Bounds for Estimating H-Index in Sublinear Time with Applications to Subgraph Counting 25

Asymptotically Optimal Bounds for Estimating H-Index in Subl...

引用

25th International Conference on approximation algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022

作者： Assadi, Sepehr Nguyen, Hoai-An Department of Computer Science Rutgers University PiscatawayNJ United States

ISBN: (纸本)9783959772495

The h-index is a metric used to measure the impact of a user in a publication setting, such as a member of a social network with many highly liked posts or a researcher in an academic domain with many highly cited publications. Specifically, the h-index of a user is the largest integer h such that at least h publications of the user have at least h units of positive feedback. We design an algorithm that, given query access to the n publications of a user and each publication's corresponding positive feedback number, outputs a (1 ±Ε)-approximation of the h-index of this user with probability at least 1 - δ in time O(n·lnΕ2(1·h/δ)), where h is the actual h-index which is unknown to the algorithm a-priori. We then design a novel lower bound technique that allows us to prove that this bound is in fact asymptotically optimal for this problem in all parameters n, h, Ε, and δ. Our work is one of the first in sublinear time algorithms that addresses obtaining asymptotically optimal bounds, especially in terms of the error and confidence parameters. As such, we focus on designing novel techniques for this task. In particular, our lower bound technique seems quite general - to showcase this, we also use our approach to prove an asymptotically optimal lower bound for the problem of estimating the number of triangles in a graph in sublinear time, which now is also optimal in the error and confidence parameters. This latter result improves upon prior lower bounds of Eden, Levi, Ron, and Seshadhri (FOCS'15) for this problem, as well as multiple follow-up works that extended this lower bound to other subgraph counting problems. © Sepehr Assadi and Hoai-An Nguyen.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Privately Estimating Graph Parameters in Sublinear Time 49

Privately Estimating Graph Parameters in Sublinear Time

引用

49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022

作者： Blocki, Jeremiah Grigorescu, Elena Mukherjee, Tamalika Department of Computer Science Purdue University West LafayetteIN United States

ISBN: (纸本)9783959772358

We initiate a systematic study of algorithms that are both differentially-private and run in sublinear time for several problems in which the goal is to estimate natural graph parameters. Our main result is a differentially-private (1 + ρ)-approximation algorithm for the problem of computing the average degree of a graph, for every ρ > 0. The running time of the algorithm is roughly the same (for sparse graphs) as its non-private version proposed by Goldreich and Ron (Sublinear algorithms, 2005). We also obtain the first differentially-private sublinear-time approximation algorithms for the maximum matching size and the minimum vertex cover size of a graph. An overarching technique we employ is the notion of coupled global sensitivity of randomized algorithms. Related variants of this notion of sensitivity have been used in the literature in ad-hoc ways. Here we formalize the notion and develop it as a unifying framework for privacy analysis of randomized approximation algorithms. © Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee;licensed under Creative Commons License CC-BY 4.0

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Counting Simplices in Hypergraph Streams 30

Counting Simplices in Hypergraph Streams

引用

30th Annual European Symposium on algorithms, ESA 2022

作者： Chakrabarti, Amit Haris, Themistoklis Dartmouth College HanoverNH United States

ISBN: (纸本)9783959772471

We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied problem of estimating the number of triangles in a graph stream. Our input is a k-uniform hypergraph H with n vertices and m hyperedges, each hyperedge being a k-sized subset of vertices. A k-simplex in H is a subhypergraph on k + 1 vertices X such that all k + 1 possible hyperedges among X exist in H. The goal is to process the hyperedges of H, which arrive in an arbitrary order as a data stream, and compute a good estimate of Tk(H), the number of k-simplices in H. We design a suite of algorithms for this problem. As with triangle-counting in graphs (which is the special case k = 2), sublinear space is achievable but only under a promise of the form Tk(H) ≥ T. Under such a promise, our algorithms use at most four passes and together imply a space bound of (equation presented) for each fixed k ≥ 3, in order to guarantee an estimate within (1/ϵ)Tk(H) with probability ≥ 1-δ. We also give a simpler 1-pass algorithm that achieves O ) ϵ-2 log δ-1 log n (m/T) ) ΔE + Δ1-1/k V ) space, where ΔE (respectively, ΔV ) denotes the maximum number of k-simplices that share a hyperedge (respectively, a vertex), which generalizes a previous result for the k = 2 case. We complement these algorithmic results with space lower bounds of the form Ω(ϵ-2), Ω(m1+1/k/T ), Ω(m/T1-1/k) and Ω(mΔ1/k V /T ) for multi-pass algorithms and Ω(mΔE/T ) for 1-pass algorithms, which show that some of the dependencies on parameters in our upper bounds are nearly tight. Our techniques extend and generalize several different ideas previously developed for triangle counting in graphs, using appropriate innovations to handle the more complicated combinatorics of hypergraphs. © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Massively Parallel algorithms for Small Subgraph Counting 25

Massively Parallel Algorithms for Small Subgraph Counting

引用

25th International Conference on approximation algorithms for Combinatorial Optimization Problems and the 26th International Conference on Randomization and Computation, APPROX/RANDOM 2022

作者： Biswas, Amartya Shankha Eden, Talya Liu, Quanquan C. Rubinfeld, Ronitt Mitrović, Slobodan CSAIL MIT CambridgeMA United States Boston University MA United States Northwestern University EvanstonIL United States University of California DavisCA United States

ISBN: (纸本)9783959772495

Over the last two decades, frameworks for distributed-memory parallel computation, such as MapReduce, Hadoop, Spark and Dryad, have gained significant popularity with the growing prevalence of large network datasets. The Massively Parallel Computation (MPC) model is the defacto standard for studying graph algorithms in these frameworks theoretically. Subgraph counting is one such fundamental problem in analyzing massive graphs, with the main algorithmic challenges centering on designing methods which are both scalable and accurate. Given a graph G = (V, E) with n vertices, m edges and T triangles, our first result is an algorithm that outputs a (1 + Ε)-approximation to T, with asymptotically optimal round and total space complexity provided any S ≥ max (√m, n2/m) space per machine and assuming T = Ω(pm/n). Our result gives a quadratic improvement on the bound on T over previous works. We also provide a simple extension of our result to counting any subgraph of k size for constant k ≥ 1. Our second result is an Oδ(log log n)-round algorithm for exactly counting the number of triangles, whose total space usage is parametrized by the arboricity α of the input graph. We extend this result to exactly counting k-cliques for any constant k. Finally, we prove that a recent result of Bera, Pashanasangi and Seshadhri (ITCS 2020) for exactly counting all subgraphs of size at most 5 can be implemented in the MPC model in Õδ(√log n) rounds, O(nδ) space per machine and O(mα3) total space. In addition to our theoretical results, we simulate our triangle counting algorithms in real-world graphs obtained from the Stanford Network Analysis Project (SNAP) database. Our results show that both our approximate and exact counting algorithms exhibit improvements in terms of round complexity and approximation ratio, respectively, compared to two previous widely used algorithms for these problems. © Amartya Shankha Biswas, Talya Eden, Quanquan C. Liu, Ronitt Rubinfeld, and Slobodan Mitrović

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On New Approaches of Maximum Weighted Target Coverage and Sensor Connectivity: Hardness and approximation

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2020年第3期7卷 1736-1751页

作者： Nguyen, Tu N. Liu, Bing-Hong Wang, Shih-Yuan Purdue Univ Dept Comp Sci Ft Wayne IN 46805 USA Natl Kaohsiung Univ Sci & Technol Dept Elect Engn Kaohsiung 80778 Taiwan

In mobile wireless sensor networks (MWSNs), because the movement of sensors consumes much more power than that in sensing and communication, the problem of scheduling mobile sensors to cover all targets and maintain network connectivity such that the total movement distance of mobile sensors is minimized has received a great deal of attention. However, network design in fact indicates that there are situations (limited budget, sensor failure, or obstacle in a sensing field) in which the number of active mobile sensors is insufficient to cover all targets or form a connected network. Therefore, targets must be weighted by their importance. The more important a target, the higher the weight of the target. A more general problem for target coverage and network connectivity, termed the Maximum Weighted Target Coverage and Sensor Connectivity with Limited Mobile Sensors (TAR-CC) problem, is studied. In this paper, an approximation algorithm, termed the weighted-maximum-coverage-based algorithm (WMCBA), is proposed for the subproblem of the TAR-CC problem. Based on the WMCBA, the Steiner-tree-based algorithm (STBA) is proposed for the TAR-CC problem. Simulation results demonstrate that the STBA provides better performance than the other methods.

关键词： Sensors Wireless sensor networks approximation algorithms Monitoring Schedules Simulation Security Mobile wireless sensor network target coverage network connectivity NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：