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

Inductive graph invariants and approximation algorithms

DISCRETE MATHEMATICS algorithms AND APPLICATIONS 2022年第6期14卷

作者： Subramanian, C. R. HBNI Inst Math Sci CIT Campus Chennai 600113 Tamil Nadu India

We introduce and study an inductively defined analogue f(IND)() of any increasing graph invariant f (). An invariant f() is increasing if f (H) = 1. Such a generalization is employed in designing efficient approximati... 详细信息

We introduce and study an inductively defined analogue f(IND)() of any increasing graph invariant f (). An invariant f() is increasing if f (H) <= f (G) whenever H is an induced subgraph of G. This inductive analogue simultaneously generalizes and unifies known notions like degeneracy, inductive independence number, etc., into a single generic notion. For any given increasing f (), this gets us several new invariants and many of which are also increasing. It is also shown that f(IND()) is the minimum (over all orderings) of a value associated with each ordering. We also explore the possibility of computing f(IND)() (and a corresponding optimal vertex ordering) and identify some pairs (C,f()) for which f(IND)() can be computed efficiently for members of C. In particular, it includes graphs of bounded f(IND)() values. Some specific examples (like the class of chordal graphs) have already been studied extensively. We further extend this new notion by (i) allowing vertex weighted graphs, (ii) allowing /0 to take values from a totally ordered universe with a minimum and (iii) allowing the consideration of r-neighborhoods for arbitrary but fixed r >= 1. Such a generalization is employed in designing efficient approximations of some graph optimization problems. Precisely, we obtain efficient algorithms (by generalizing the known algorithm of Ye and Borodin [Y. Ye and A. Borodin, Elimination graphs, ACM Trans. algorithms 8(2) (2012) 1-23] for special cases) for approximating optimal weighted induced P-subgraphs and optimal P-colorings (for hereditary P's) within multiplicative factors of (essentially) k and k/(m - 1), respectively, where k denotes the inductive analogue (as defined in this work) of optimal size of an unweighted induced P-subgraph of the input and m is the minimum size of a forbidden induced subgraph of P. Our results generalize the previous result on efficiently approximating maximum independent sets and minimum colorings on graphs of bounded inductive inde

关键词： approximation algorithms combinatorial optimisation P-colorings P-subgraphs degeneracy graph invariants

来源：评论

学校读者我要写书评

暂无评论

Almost Tight approximation algorithms for Explainable Clustering 33

Almost Tight Approximation Algorithms for Explainable Cluste...

引用

Annual ACM-SIAM Symposium on Discrete algorithms (SODA)

作者： Esfandiari, Hossein Mirrokni, Vahab Narayanan, Shyam Google Res Mountain View CA 94043 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9781611977073

Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal of accuracy and interpretability by humans. In this paper, we study a recent framework of explainable clustering first suggested by Dasgupta et al. [11]. Specifically, we focus on the k-means and k-median problems and provide nearly tight upper and lower bounds. First, we provide an O(log k log log k)-approximation algorithm for explainable k-median, improving on the best known algorithm of O(k) [11] and nearly matching the known Omega(log k) lower bound [11]. In addition, in low-dimensional spaces d << log k, we show that our algorithm also provides an O(d log(2) d)-approximate solution for explainable k-median. This improves over the best known bound of O(d log k) for low dimensions [19], and is a constant for constant dimensional spaces. To complement this, we show a nearly matching Omega(d) lower bound. Next, we study the k-means problem in this context and provide an O(k log k)-approximation algorithm for explainable k-means, improving over the O(k(2)) bound of Dasgupta et al. and the O(dk log k) bound of [19]. To complement this we provide an almost tight Omega(k) lower bound, improving over the Omega(log k) lower bound of Dasgupta et al. Given an approximate solution to the classic k-means and k-median, our algorithm for k-median runs in time O(kd log(2) k) and our algorithm for k-means runs in time O(k(2) d).

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

STABLE approximation algorithms FOR DOMINATING SET AND INDEPENDENT SET

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2025年第2期39卷 921-945页

作者： de Berg, Mark Sadhukhan, Arpan Spieksma, Frits TU Eindhoven Dept Math & Comp Sci NL-5612 DP Eindhoven Netherlands

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: (i) We show that there is a constant epsilon(& lowast;)>0 such that any dynamic (1+epsilon(& lowast;))-approximation algorithm for Dominating Set has stability parameter Omega(n), even for bipartite graphs of maximum degree 4. (ii) 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 algorithm, a 3-stable (9d/2)-approximation algorithm, and an O(d)-stable O(1)-approximation algorithm. (iii) We show that there is a constant epsilon(& lowast;)>0 such that any dynamic (1+epsilon(& lowast;))-approximation algorithm for Independent Set has stability parameter Omega(n), even for bipartite graphs of maximum degree 3. (iv) 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. We extend this latter algorithm to the fully dynamic model where vertices can also be deleted, achieving a 6-stable O(d)-approximation algorithm.

关键词： dynamic algorithms approximation algorithms stability dominating set independent set bounded recourse

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Individually Fair Clustering 25

Improved Approximation Algorithms for Individually Fair Clus...

引用

International Conference on Artificial Intelligence and Statistics

作者： Vakilian, Ali Yalciner, Mustafa Toyota Technol Inst Chicago TTIC Chicago IL 60637 USA Tech Univ Dortmund Dortmund Germany

We consider the k-clustering problem with l(p)-norm cost, which includes k-median, kmeans and k-center, under an individual notion of fairness proposed by Jung et al. [2020]: given a set of points P of size n, a set of k centers induces a fair clustering if every point in P has a center among its n/k closest neighbors. Mahabadi and Vakilian [2020] presented a (p(o(P)), 7)-bicriteria approximation for fair clustering with l(p)-norm cost: every point finds a center within distance at most 7 times its distance to its (n/k)-th closest neighbor and the l(p)-norm cost of the solution is at most p(o(P)) times the cost of an optimal fair solution. In this work, for any epsilon > 0, we present an improved (16(P) + epsilon, 3)-bicriteria for this problem. Moreover, for p = 1 (k-median) and p = infinity (k-center), we present improved cost-approximation factors 7.081 + epsilon and 3 + epsilon respectively. To achieve our guarantees, we extend the framework of [Charikar et al., 2002, Swam3T, 2016] and devise a 16P-approximation algorithm for the facility location with l(p)-norm cost under matroid constraint which might be of an independent interest. Besides, our approach suggests a reduction from our individually fair clustering to a clustering with a group fairness requirement proposed by Kleindessner et al. [2019], which is essentially the median matroid problem [Krishnaswamy et al., 2011].

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Additive approximation algorithms for modularity maximization

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2021年 117卷 182-201页

作者： Kawase, Yasushi Matsui, Tomomi Miyauchi, Atsushi Univ Tokyo Grad Sch Informat Sci & Technol Bunkyo Ku Hongo 7-3-1 Tokyo 1138656 Japan Tokyo Inst Technol Sch Engn Meguro Ku Ookayama 2-12-1 Tokyo 1528552 Japan

The modularity is the best known and widely used quality function for community detection in graphs. We investigate the approximability of the modularity maximization problem and some related problems. We first design a polynomial-time 0.4209-additive approximation algorithm for the modularity maximization problem, which improves the current best additive approximation error of 0.4672. Our theoretical analysis also demonstrates that the proposed algorithm obtains a nearly-optimal solution for any instance with a high modularity value. We next design a polynomial-time 0.1660-additive approximation algorithm for the maximum modularity cut problem. Finally, we extend our algorithm to some related problems. (C) 2020 Elsevier Inc. All rights reserved.

关键词： Networks Community detection Modularity maximization approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Solving High-Order Portfolios via Successive Convex approximation algorithms

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2021年 69卷 892-904页

作者： Zhou, Rui Palomar, Daniel P. Hong Kong Univ Sci & Technol HKUST Elect & Comp Engn Kowloon Clear Water Bay Hong Kong Peoples R China

The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue higher mean and lower variance when designing the portfolios. The two moments can well describe the distribution of the portfolio return when it follows the Gaussian distribution. However, the real world distribution of assets return is usually asymmetric and heavy-tailed, which is far from being a Gaussian distribution. The asymmetry and the heavy-tailedness are characterized by the third and fourth central moments, i.e., skewness and kurtosis, respectively. Higher skewness and lower kurtosis are preferred to reduce the probability of extreme losses. However, incorporating high-order moments in the portfolio design is very difficult due to their non-convexity and rapidly increasing computational cost with the dimension. In this paper, we propose a very efficient and convergence-provable algorithm framework based on the successive convex approximation (SCA) algorithm to solve high-order portfolios. The efficiency of the proposed algorithm framework is demonstrated by the numerical experiments.

关键词： Portfolios Signal processing algorithms approximation algorithms Optimization Computational complexity Gaussian distribution Shape High-order portfolios skewness kurtosis efficient algorithm successive convex approximation

来源：评论

学校读者我要写书评

暂无评论

Inequity aversion pricing over social networks: approximation algorithms and hardness results

引用

THEORETICAL COMPUTER SCIENCE 2021年 871卷 62-78页

作者： Amanatidis, Georgios Fulla, Peter Markakis, Evangelos Sornat, Krzysztof Univ Essex Dept Math Sci Colchester Essex England Univ Amsterdam Inst Log Language & Computat Amsterdam Netherlands Univ Oxford Dept Comp Sci Oxford England Athens Univ Econ & Business Dept Informat Athens Greece Univ Wroclaw Inst Comp Sci Wroclaw Poland

We study a revenue maximization problem in the context of social networks. Namely, we generalize a model introduced by Alon, Mansour, and Tennenholtz [2] that captures inequity aversion, i.e., it captures the fact that prices offered to neighboring nodes should not differ significantly. We first provide approximation algorithms for a natural class of instances, where the total revenue is the sum of single-value revenue functions. Our results improve on the current state of the art, especially when the number of distinct prices is small. This applies, for instance, to settings where the seller will only consider a fixed number of discount types or special offers. To complement our positive results, we resolve one of the open questions posed in [2] by establishing APX-hardness for the problem. Surprisingly, we further show that the problem is NP-complete even when the price differences are allowed to be large, or even when the number of allowed distinct prices is as small as three. Finally, we study extensions of the model regarding the demand type of the clients. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Revenue maximization Inequity aversion Social networks Pricing approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Improvements on approximation algorithms for clustering probabilistic data

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2021年第10期63卷 2719-2740页

作者： Alipour, Sharareh Inst Res Fundamental Sci Sch Comp Sci IPM Tehran Iran

Uncertainty about data appears in many real-world applications and an important issue is how to manage, analyze and solve optimization problems over such data. An important tool for data analysis is clustering. When the data set is uncertain, we can model them as a set of probabilistic points each formalized as a probability distribution function which describes the possible locations of the points. In this paper, we study k-center problem for probabilistic points in a general metric space. First, we present a fast greedy approximation algorithm that builds k centers using a farthest-first traversal in k iterations. This algorithm improves the previous approximation factor of the unrestricted assigned k-center problem from 10 (see [1]) to 6. Next, we restrict the centers to be selected from all the probabilistic locations of the given points and we show that an optimal solution for this restricted setting is a 2-approximation factor solution for an optimal solution of the assigned k-center problem with expected distance assignment. Using this idea, we improve the approximation factor of the unrestricted assigned k-center problem to 4 by increasing the running time. The algorithm also runs in polynomial time when k is a constant. Additionally, we implement our algorithms on three real data sets. The experimental results show that in practice the approximation factors of our algorithms are better than in theory for these data sets. Also we compare the results of our algorithm with the previous works and discuss about the achieved results. At the end, we present our theoretical results for probabilistic k-median clustering.

关键词： k-center problem k-median problem Clustering Uncertain data approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Online Linear Optimization with approximation algorithms

引用

MATHEMATICS OF OPERATIONS RESEARCH 2021年第1期46卷 204-220页

作者： Garber, Dan Technion Israel Inst Technol Fac Ind Engn & Management IL-3200003 Haifa Israel

We revisit the problem of online linear optimization in the case where the set of feasible actions is accessible through an approximated linear optimization oracle with a factor alpha multiplicative approximation guarantee. This setting in particular is interesting because it captures natural online extensions of well-studied offline linear optimization problems that are NP-hard yet admit efficient approximation algorithms. The goal here is to minimize the alpha-regret, which is the natural extension to this setting of the standard regret in online learning. We present new algorithms with significantly improved oracle complexity for both the full-information and bandit variants of the problem. Mainly, for both variants, we present alpha-regret bounds of O(T-1/3), were T is the number of prediction rounds, using only O(log T) calls to the approximation oracle per iteration, on average. These are the first results to obtain both the average oracle complexity of O(log T) (or even polylogarithmic in T) and alpha-regret bound O(T-c) for a constant c > 0 for both variants.

关键词： online learning online linear optimization regret minimization approximation algorithms online algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation algorithms for Minimum Cost Seed Selection with Probabilistic Coverage Guarantee

引用

Proceedings of the ACM on Management of Data 2024年第4期2卷 1-26页

作者： Chen Feng Xingguang Chen Qintian Guo Fangyuan Zhang Sibo Wang The Hong Kong Polytechnic University Hong Kong Hong Kong National University of Singapore Singapore Singapore The Chinese University of Hong Kong Hong Kong Hong Kong

Given a social network G, a cost associated with each user, and an influence threshold η, the minimum cost seed selection problem (MCSS) aims to find a set of seeds that minimizes the total cost to reach η users. Existing works are mainly devoted to providing an expected coverage guarantee on reaching η, classified as MCSS-ECG, where their solutions either rely on an impractical influence oracle or cannot attain the expected influence threshold. More importantly, due to the expected coverage guarantee, the actual influence in a campaign may drift from the threshold evidently. Thus, the advertisers would like to request for a probability guarantee of reaching η. This motivates us to further solve the MCSS problem with a probabilistic coverage guarantee, termed *** this paper, we first propose our algorithm CLEAR to solve MCSS-ECG, which reaches the expected influence threshold without any influence oracle or influence shortfall but a practical approximation ratio. However, the ratio involves an unknown term (i.e., the optimal cost). Thus, we further devise the STAR method to derive a lower bound of the optimal cost and then obtain the first explicit approximation ratio for MCSS-ECG. In MCSS-PCG, it is necessary to estimate the probability that the current seeds reach η, to decide when to stop seed selection. To achieve this, we design a new technique named MRR, which provides efficient probability estimation with a theoretical guarantee. With MRR in hand, we propose our algorithm SCORE for MCSS-PCG, whose performance guarantee is derived by measuring the gap between MCSS-ECG and MCSS-PCG, and applying the theoretical results in MCSS-ECG. Finally, extensive experiments demonstrate that our algorithms achieve up to two orders of magnitude speed-up compared to alternatives while meeting the requirement of MCSS-PCG with the smallest cost.

关键词： approximation algorithms minimum cost seed selection probability estimation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：