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

37th Conference on Neural Information Processing Systems, NeurIPS 2023

作者： Chen, Wenjing Crawford, Victoria G. Department of Computer Science & Engineering Texas A&M University United States

ISBN: (纸本)9781713899921

In this paper, we consider the optimization problem Submodular Cover (SCP), which is to find a minimum cardinality subset of a finite universe U such that the value of a submodular function f is above an input threshold τ. In particular, we consider several variants of SCP including the general case, the case where f is additionally assumed to be monotone, and finally the case where f is a regularized monotone submodular function. Our most significant contributions are that: (i) We propose a scalable algorithm for monotone SCP that achieves nearly the same approximation guarantees as the standard greedy algorithm in significantly faster time;(ii) We are the first to develop an algorithm for general SCP that achieves a solution arbitrarily close to being feasible;and finally (iii) we are the first to develop algorithms for regularized SCP. Our algorithms are then demonstrated to be effective in an experimental section on data summarization and graph cut, two applications of SCP. © 2023 Neural information processing systems foundation. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

New approximation algorithms for Touring Regions 39

New Approximation Algorithms for Touring Regions

引用

39th International Symposium on Computational Geometry, SoCG 2023

作者： Qi, Benjamin Qi, Richard Massachusetts Institute of Technology CambridgeMA United States

ISBN: (纸本)9783959772730

We analyze the touring regions problem: find a (1 + ϵ)-approximate Euclidean shortest path in d-dimensional space that starts at a given starting point, ends at a given ending point, and visits given regions R1, R2, R3, ..., Rn in that order. Our main result is an (Equation presented) -time algorithm for touring disjoint disks. We also give an (Equation presented)-time algorithm for touring disjoint two-dimensional convex fat bodies. Both of these results naturally generalize to larger dimensions;we obtain (Equation presented) and (Equation presented)-time algorithms for touring disjoint d-dimensional balls and convex fat bodies, respectively. © Benjamin Qi and Richard Qi;licensed under Creative Commons License CC-BY 4.0.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Design of Self-Stabilizing approximation algorithms via a Primal-Dual Approach 26

Design of Self-Stabilizing Approximation Algorithms via a Pr...

引用

26th International Conference on Principles of Distributed Systems, OPODIS 2022

作者： Emek, Yuval Gil, Yuval Harlev, Noga Technion Israel Institute of Technology Haifa Israel

ISBN: (纸本)9783959772655

Self-stabilization is an important concept in the realm of fault-tolerant distributed computing. In this paper, we propose a new approach that relies on the properties of linear programming duality to obtain self-stabilizing approximation algorithms for distributed graph optimization problems. The power of this new approach is demonstrated by the following results: A self-stabilizing 2(1 + Ε)-approximation algorithm for minimum weight vertex cover that converges in O(log ∆/(Ε log log ∆)) synchronous rounds. A self-stabilizing ∆-approximation algorithm for maximum weight independent set that converges in O(∆ + log∗ n) synchronous rounds. A self-stabilizing ((2ρ + 1)(1 + Ε))-approximation algorithm for minimum weight dominating set in ρ-arboricity graphs that converges in O((log ∆)/Ε) synchronous rounds. In all of the above, ∆ denotes the maximum degree. Our technique improves upon previous results in terms of time complexity while incurring only an additive O(log n) overhead to the message size. In addition, to the best of our knowledge, we provide the first self-stabilizing algorithms for the weighted versions of minimum vertex cover and maximum independent set. © Yuval Emek, Yuval Gil, and Noga Harlev.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Graph Burning on Cactus and Directed Trees

arXiv

引用

arXiv 2023年

作者： Gautam, Rahul Kumar Kare, Anjeneya Swami Bhavani, S. Durga School of Computer and Information Sciences University of Hyderabad Hyderabad India

Given a graph G = (V;E), the problem of Graph Burning is to find a sequence of nodes from V, called a burning sequence, to burn the whole graph. This is a discrete-step process, and at each step, an unburned vertex is selected as an agent to spread fire to its neighbors by marking it as a burnt node. A burnt node spreads the fire to its neighbors at the next consecutive step. The goal is to find the burning sequence of minimum length. The Graph Burning problem is NP-Hard for general graphs and even for binary trees. A few approximation results are known, including a 3-approximation algorithm for general graphs and a 2-approximation algorithm for trees. The Graph Burning on directed graphs is more challenging than on undirected graphs. In this paper, we propose 1) A 2.75-approximation algorithm for a cactus graph (undirected), 2) A 3-approximation algorithm for multi-rooted directed trees (polytree) and 3) A 1.905-approximation algorithm for single-rooted directed tree (arborescence). We implement all the three approximation algorithms and the results are shown for randomly generated cactus graphs and directed trees. © 2023, CC BY.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Bicriteria approximation algorithms for Priority Matroid Median 26

Bicriteria Approximation Algorithms for Priority Matroid Med...

引用

26th International Conference on approximation algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023

作者： Bajpai, Tanvi Chekuri, Chandra Department of Computer Science University of Illinois Urbana-Champaign UrbanaIL United States

ISBN: (纸本)9783959772969

Fairness considerations have motivated new clustering problems and algorithms in recent years. In this paper we consider the Priority Matroid Median problem which generalizes the Priority k-Median problem that has recently been studied. The input consists of a set of facilities F and a set of clients C that lie in a metric space (F ∪ C, d), and a matroid M = (F, I) over the facilities. In addition, each client j has a specified radius rj ≥ 0 and each facility i ∈ F has an opening cost fi > 0. The goal is to choose a subset S ⊆ F of facilities to minimize Pi∈F fi + Pj∈C d(j, S) subject to two constraints: (i) S is an independent set in M (that is S ∈ I) and (ii) for each client j, its distance to an open facility is at most rj (that is, d(j, S) ≤ rj). For this problem we describe the first bicriteria (c1, c2) approximations for fixed constants c1, c2: the radius constraints of the clients are violated by at most a factor of c1 and the objective cost is at most c2 times the optimum cost. We also improve the previously known bicriteria approximation for the uniform radius setting (rj := L ∀j ∈ C). © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Timeline Cover in Temporal Graphs: Exact and approximation algorithms 1

引用

34th International Workshop on Combinatorial algorithms (IWOCA)

作者： Dondi, Riccardo Popa, Alexandru Univ Bergamo Bergamo Italy Univ Bucharest Dept Comp Sci Bucharest Romania

ISBN: (数字)9783031343476

ISBN: (纸本)9783031343469;9783031343476

In this paper we study a variant of vertex cover on temporal graphs that has been recently introduced for timeline activities summarization in social networks. The problem has been proved to be NP-hard, even in restricted cases. In this paper, we present algorithmic contributions for the problem. First, we present an approximation algorithm of factor O(T log n), on a temporal graph of T timestamps and n vertices. Then, we consider the restriction where at most one temporal edge is defined in each timestamp. For this restriction, which has been recently shown to be NP-hard, we present a 4(T - 1) approximation algorithm and a parameterized algorithm when the parameter is the cost (called span) of the solution.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient and Practical approximation algorithms for Advertising in Content Feeds 25

Efficient and Practical Approximation Algorithms for Adverti...

引用

34th ACM Web Conference, WWW 2025

作者： Zhang, Guangyi Sarpe, Ilie Gionis, Aristides Shenzhen Technology University Shenzhen China KTH Royal Institute of Technology Stockholm Sweden

ISBN: (纸本)9798400712746

Content feeds provided by platforms such as X (formerly Twitter) and TikTok are consumed by users on a daily basis. In this paper, we revisit the native advertising problem in content feeds, initiated by Ieong et al. Given a sequence of organic items (e.g., videos or posts) relevant to a user’s interests or to an information search, the goal is to place ads within the organic content so as to maximize a reward function (e.g., number of clicks), while accounting for two considerations: (1) an ad can only be inserted after a relevant content item;(2) the users’ attention decays after consuming content or ads. These considerations provide a natural model for capturing both the advertisement effectiveness and the user experience. In this paper, we design fast and practical 2-approximation greedy algorithms for the associated optimization problem, improving over the best-known practical algorithm that only achieves an approximation factor of 4. Our algorithms exploit a counter-intuitive observation, namely, while top items are seemingly more important due to the decaying attention of the user, taking good care of the bottom items is key for obtaining improved approximation guarantees. We then provide the first comprehensive empirical evaluation on the problem, showing the strong empirical performance of our methods. © 2025 Copyright held by the owner/author(s).

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Stable approximation algorithms for Dominating Set and Independent Set 26

Stable Approximation Algorithms for Dominating Set and Indep...

引用

26th International Conference on approximation algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023

作者： de Berg, Mark Sadhukhan, Arpan Spieksma, Frits Department of Mathematics and Computer Science TU Eindhoven Netherlands

ISBN: (纸本)9783959772969

We study Dominating Set and Independent Set for dynamic graphs in the vertex-arrival model. We say that a dynamic algorithm for one of these problems is k-stable when it makes at most k changes to its output independent set or dominating set upon the arrival of each vertex. We study trade-offs between the stability parameter k of the algorithm and the approximation ratio it achieves. We obtain the following results. We show that there is a constant Ε∗ > 0 such that any dynamic (1 + Ε∗)-approximation algorithm for Dominating Set has stability parameter Ω(n), even for bipartite graphs of maximum degree 4. We present algorithms with very small stability parameters for Dominating Set in the setting where the arrival degree of each vertex is upper bounded by d. In particular, we give a 1-stable (d + 1)2-approximation, and a 3-stable (9d/2)-approximation algorithm. We show that there is a constant Ε∗ > 0 such that any dynamic (1 + Ε∗)-approximation algorithm for Independent Set has stability parameter Ω(n), even for bipartite graphs of maximum degree 3. Finally, we present a 2-stable O(d)-approximation algorithm for Independent Set, in the setting where the average degree of the graph is upper bounded by some constant d at all times. © 2023 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for the Diameter-Bounded Max-Coverage Group Steiner Tree Problem 23

Efficient Approximation Algorithms for the Diameter-Bounded ...

引用

2023 World Wide Web Conference, WWW 2023

作者： Zhang, Ke Wang, Xiaoqing Cheng, Gong State Key Laboratory for Novel Software Technology Nanjing University Nanjing China

ISBN: (纸本)9781450394161

The Diameter-bounded max-Coverage Group Steiner Tree (DCGST) problem has recently been proposed as an expressive way of formulating keyword-based search and exploration of knowledge graphs. It aims at finding a diameter-bounded tree which covers the most given groups of vertices and has the minimum weight. In contrast to its specialization - the classic Group Steiner Tree (GST) problem which has been extensively studied, the emerging DCGST problem still lacks an efficient algorithm. In this paper, we propose Cba, the first approximation algorithm for the DCGST problem, and we prove its worst-case approximation ratio. Furthermore, we incorporate a best-first search strategy with two pruning methods into PrunedCBA, an improved approximation algorithm. Our extensive experiments on real and synthetic graphs demonstrate the effectiveness and efficiency of PrunedCBA. © 2023 ACM.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Quantum Max-d-Cut

arXiv

引用

arXiv 2023年

作者： Carlson, Charlie Jorquera, Zackary Kolla, Alexandra Kordonowy, Steven Wayland, Stuart University of California Santa Barbara United States University of California Santa Cruz United States

We initiate the algorithmic study of the Quantum Max-d-Cut problem, a quantum generalization of the well-known Max-d-Cut problem. The Quantum Max-d-Cut problem involves finding a quantum state that maximizes the expected energy associated with the projector onto the antisymmetric subspace of two, d-dimensional qudits over all local interactions. Equivalently, this problem is physically motivated by the SU(d)-Heisenberg model, a spin glass model that generalized the well-known Heisenberg model over qudits. We develop a polynomial-time randomized approximation algorithm that finds product-state solutions of mixed states with bounded purity that achieve non-trivial performance guarantees. Moreover, we prove the tightness of our analysis by presenting an algorithmic gap instance for Quantum Max-d-Cut with d ≥ 3. © 2023, CC BY.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：