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

Local Stackelberg Equilibrium Seeking in Generalized Aggregative Games

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2022年第2期67卷 965-970页

作者： Fabiani, Filippo Tajeddini, Mohammad Amin Kebriaei, Hamed Grammatico, Sergio Univ Oxford Dept Engn Sci Oxford OX1 3PJ England Univ Tehran Sch Elect & Comp Engn Coll Engn Tehran 14395515 Iran Delft Univ Technol Delft Ctr Syst & Control NL-2628 CD Delft Netherlands

We propose a two-layer, semidecentralized algorithm to compute a local solution to the Stackelberg equilibrium problem in aggregative games with coupling constraints. Specifically, we focus on a single-leader, multiple-follower problem, and after equivalently recasting the Stackelberg game as a mathematical program with complementarity constraints (MPCC), we iteratively convexify a regularized version of the MPCC as the inner problem, whose solution generates a sequence of feasible descent directions for the original MPCC. Thus, by pursuing a descent direction at every outer iteration, we establish convergence to a local Stackelberg equilibrium. Finally, the proposed algorithm is tested on a numerical case study, a hierarchical instance of the charging coordination problem of plug-in electric vehicles.

关键词： Games Cost function Couplings Standards approximation algorithms Convergence Wireless networks Game theory hierarchical systems optimization Stackelberg equilibrium

来源：评论

学校读者我要写书评

暂无评论

An Evaluation-Focused Framework for Visualization Recommendation algorithms

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2022年第1期28卷 346-356页

作者： Zeng, Zehua Moh, Phoebe Du, Fan Hoffswell, Jane Lee, Tak Yeon Malik, Sana Koh, Eunyee Battle, Leilani Univ Maryland College Pk MD 20742 USA Adobe Res San Jose CA USA Korea Adv Inst Sci & Technol Seoul South Korea Univ Washington Seattle WA 98195 USA

Although we have seen a proliferation of algorithms for recommending visualizations, these algorithms are rarely compared with one another, making it difficult to ascertain which algorithm is best for a given visual analysis scenario. Though several formal frameworks have been proposed in response, we believe this issue persists because visualization recommendation algorithms are inadequately specified from an evaluation perspective. In this paper, we propose an evaluation-focused framework to contextualize and compare a broad range of visualization recommendation algorithms. We present the structure of our framework, where algorithms are specified using three components: (1) a graph representing the full space of possible visualization designs, (2) the method used to traverse the graph for potential candidates for recommendation, and (3) an oracle used to rank candidate designs. To demonstrate how our framework guides the formal comparison of algorithmic performance, we not only theoretically compare five existing representative recommendation algorithms, but also empirically compare four new algorithms generated based on our findings from the theoretical comparison. Our results show that these algorithms behave similarly in terms of user performance, highlighting the need for more rigorous formal comparisons of recommendation algorithms to further clarify their benefits in various analysis scenarios.

关键词： Data visualization Visualization Machine learning algorithms approximation algorithms Task analysis Encoding Clustering algorithms Visualization Tools Visualization Recommendation algorithms

来源：评论

学校读者我要写书评

暂无评论

On approximation algorithm for the edge metric dimension problem

引用

THEORETICAL COMPUTER SCIENCE 2021年 853卷 2-6页

作者： Huang, Yufei Hou, Bo Liu, Wen Wu, Lidong Rainwater, Stephen Gao, Suogang Hebei Normal Univ Sch Math Sci Shijiazhuang 050024 Hebei Peoples R China Univ Texas Tyler Dept Comp Sci Tyler TX 75799 USA

In this paper, we study the edge metric dimension problem (EMDP). We establish a potential function and give a corresponding greedy algorithm with approximation ratio 1 + lnn + ln(log(2) n), where nis the number of ve... 详细信息

关键词： Edge metric generator Edge metric dimension approximation algorithms Submodular function

来源：评论

学校读者我要写书评

暂无评论

A Note on Approximating Weighted Nash Social Welfare with Additive Valuations 51

A Note on Approximating Weighted Nash Social Welfare with Ad...

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Feng, Yuda Li, Shi Department of Computer Science and Technology Harbin Institute of Technology Heilongjiang China Department of Computer Science and Technology Nanjing University Jiangsu China

ISBN: (纸本)9783959773225

We give the first O(1)-approximation for the weighted Nash Social Welfare problem with additive valuations. The approximation ratio we obtain is e1/e + ϵ ≈ 1.445 + ϵ, which matches the best known approximation ratio for the unweighted case [3]. Both our algorithm and analysis are simple. We solve a natural configuration LP for the problem, and obtain the allocation of items to agents using a randomized version of the Shmoys-Tardos rounding algorithm developed for unrelated machine scheduling problems [30]. In the analysis, we show that the approximation ratio of the algorithm is at most the worst gap between the Nash social welfare of the optimum allocation and that of an EF1 allocation, for an unweighted Nash Social Welfare instance with identical additive valuations. This was shown to be at most e1/e ≈ 1.445 by Barman et al. [3], leading to our approximation ratio. © Yuda Feng and Shi Li.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

The Heterogeneous Rooted Tree Cover Problem 29th

The Heterogeneous Rooted Tree Cover Problem

引用

29th International Computing and Combinatorics Conference, COCOON 2023

作者： Pan, Pengxiang Lichen, Junran Yang, Ping Li, Jianping School of Mathematics and Statistics Yunnan University East Outer Ring South Road University Town Kunming650504 China School of Mathematics and Physics Beijing University of Chemical Technology No.15 North Third Ring East Road Chaoyang District Beijing100029 China

ISBN: (纸本)9783031491924

We consider the heterogeneous rooted tree cover (HRTC) problem. Concretely, given an undirected complete graph G= (V, E) with a root r∈ V, an edge-weight function w: E→ R+ satisfying the triangle inequality, a vertex-weight function f:V\{r}→R0+, and k construction teams having nonuniform construction speeds λ1, λ2, …, λk, we are asked to find k trees for these k construction teams to cover all vertices in V, each tree starting at the same root r, i.e., k trees having a sole common vertex called root r, the objective is to minimize the maximum completion time, where the completion time of each team is the total construction weight of its related tree divided by its construction speed. In this paper, we first design a 58.3286 (1 + δ) -approximation algorithm to solve the HRTC problem in time O(n3(1+1δ)+log(w(E)+f(V\{r}))) for any δ> 0. In addition, we present a max{2ρ,2+ρ-2k} -approximation algorithm for resolving the HRTC problem in time O(n2), where ρ is the ratio between the maximum and minimum speed of these k teams. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Smooth Polynomial Approach for Microwave Imaging in Sparse Processing Framework

引用

IEEE ACCESS 2022年 10卷 120616-120629页

作者： Singh, Tushar Ninkovic, Darko M. M. Kolundzija, Branko M. M. Stevanovic, Marija Nikolic Univ Belgrade Sch Elect Engn Belgrade 11120 Serbia WIPL D doo Belgrade 11073 Serbia

We developed a novel qualitative imaging algorithm based on a polynomial approximation of the unknown contrast and sparse ( $l_{1}$ ) regularization. Contrary to previously published results, we defined polynomial bas... 详细信息

We developed a novel qualitative imaging algorithm based on a polynomial approximation of the unknown contrast and sparse ( $l_approximation$ ) regularization. Contrary to previously published results, we defined polynomial basis functions on subdomains that divide the investigation domain. Moreover, we formulated constraints that ensure the continuity of the contrast on subdomain borders. We showed that the proposed algorithm improved imaging resolution, particularly in multiple target scenarios. We demonstrated that partitioning the investigation domain together with contrast continuity formulation enhanced the numerical stability and reduced the computation time. The obtained results were significantly less sensitive to the regularization parameter values than those obtained using the standard polynomial approximation. Namely, smaller domains allow lower polynomial orders, which are numerically more favorable. Continuity constraints reduce the search space and mitigate the occurrence of false solutions. Another contribution of this study is a novel strategy for regularization parameter selection. We considered different figures of merit and numerical scenarios to study the influence of various parameters involved in the imaging process, such as the polynomial order and number of subdomains. An extensive analysis proved the robustness of the approach against noise. The proposed algorithm was designed for two-dimensional geometry. However, generalization to three-dimensional space is straightforward. The algorithm can also be used with other types of regularization such as the $l_{2}$ regularization. Potential applications include medical microwave imaging, in which high resolution and noise immunity are vital features.

关键词： Imaging Microwave imaging approximation algorithms Permittivity Microwave theory and techniques Image reconstruction Scattering Inverse scattering microwave imaging polynomial approximation sparse processing

来源：评论

学校读者我要写书评

暂无评论

Joint Beamforming for IRS-Aided Multi-Cell MISO System: Sum Rate Maximization and SINR Balancing

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2022年第9期21卷 7536-7549页

作者： Qiu, Jing Yu, Jiguo Dong, Anming Yu, Kan Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China Qilu Univ Technol Big Data Inst Jinan 250353 Shandong Peoples R China Shandong Lab Comp Networks Jinan 250014 Peoples R China Qilu Univ Technol Sch Math & Stat Shandong Acad Sci Jinan 250353 Shandong Peoples R China Qilu Univ Technol Big Data Inst Shandong Acad Sci Jinan 250353 Shandong Peoples R China Qufu Normal Univ Sch Comp Sci Rizhao 276826 Peoples R China

This paper studies joint beamforming problems for an intelligent reflecting surface (IRS)-aided multi-cell multiple-input single-output (MISO) system, and the goal is to maximize the sum rate by jointly optimizing the transmit beamforming vectors at BSs and the reflective beamforming vector at the IRS, subject to the individual maximum transmit power constraints at BSs, and the reflection constraints at the IRS. Due to the formulated optimization problem is highly non-convex, we propose an alternating optimization (AO) algorithm based on successive convex approximation (SCA) such that the transmit and reflective beamforming vectors can be optimized alternately. We further consider the SINR balancing beamforming design scheme by maximizing the minimum SINR among all users to enhance the fairness among users, in which the transmit and reflective beamforming vectors are optimized in an alternating manner. The transmit beamforming vectors are optimized by the second-order-cone programming (SOCP) based on bisection method and the reflective beamforming vector is updated based on the technique of semidefinite relaxation (SDR). Simulation results show that the two proposed algorithms considerably outperform the benchmark zero-forcing (ZF) scheme. Moreover, the AO algorithm based on SCA has good communication performance than the other two schemes. And the AO algorithm based on bisection search guarantees the fairness for all users.

关键词： Wireless communication Array signal processing Simulation Interference MISO communication Benchmark testing approximation algorithms Beamforming intelligent reflecting surface (IRS) multiple-input single-output (MISO) alternating optimization (AO) successive convex approximation (SCA) bisection method

来源：评论

学校读者我要写书评

暂无评论

Shapley Values for Explanation in Two-sided Matching Applications 27

Shapley Values for Explanation in Two-sided Matching Applica...

引用

27th International Conference on Extending Database Technology, EDBT 2024

作者： Shetiya, Suraj Swift, Ian P. Asudeh, Abolfazl Das, Gautam University of Texas Arlington United States University of Illinois Chicago United States

ISBN: (纸本)9783893180950

In this paper, we initiate research in explaining matchings. In particular, we consider the large-scale two-sided matching applications where preferences of the users are specified as (ranking) functions over a set of attributes and matching recommendations are derived as top-k. We consider multiple natural explanation questions, concerning the users of these systems. Observing the competitive nature of these environments, we propose multiple Shapley-based approaches for explanation. Besides exact algorithms, we propose a sampling-based approximation algorithm with provable guarantees to overcome the combinatorial complexity of the exact Shapley computation. Our extensive experiments on real-world and synthetic data sets validate the usefulness of our proposal and confirm the efficiency and accuracy of our algorithms. © 2024 Copyright held by the owner/author(s).

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Toward Efficient Online Scheduling for Distributed Machine Learning Systems

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2022年第4期9卷 1951-1969页

作者： Yu, Menglu Liu, Jia Wu, Chuan Ji, Bo Bentley, Elizabeth S. Iowa State Univ Dept Comp Sci Ames IA 50011 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA Univ Hong Kong Dept Comp Sci Hong Kong 999077 Peoples R China Air Force Res Lab Informat Directorate Rome NY 13441 USA

Recent years have witnessed a rapid growth of distributed machine learning (ML) frameworks, which exploit the massive parallelism of computing clusters to expedite ML training. However, the proliferation of distributed ML frameworks also introduces many unique technical challenges in computing system design and optimization. In a networked computing cluster that supports a large number of training jobs, a key question is how to design efficient scheduling algorithms to allocate workers and parameter servers across different machines to minimize the overall training time. Toward this end, in this paper, we develop an online scheduling algorithm that jointly optimizes resource allocation and locality decisions. Our main contributions are three-fold: i) We develop a new analytical model that considers both resource allocation and locality;ii) Based on an equivalent reformulation and observations on the worker-parameter server locality configurations, we transform the problem into a mixed packing and covering integer program, which enables approximation algorithm design;iii) We propose a meticulously designed approximation algorithm based on randomized rounding and rigorously analyze its performance. Collectively, our results contribute to the state of the art of distributed ML system optimization and algorithm design.

关键词： Servers Training Optimization Scheduling algorithms Resource management approximation algorithms Heuristic algorithms Online resource scheduling distributed machine learning approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Solving Influence Maximization Problem Under Deterministic Linear Threshold Model Using Metaheuristic optimization 47

Solving Influence Maximization Problem Under Deterministic L...

引用

47th ICT and Electronics Convention, MIPRO 2024

作者： Andreev, A. Chukharev, K. Kochemazov, S. Semenov, A. Itmo University St. Petersburg Russia

ISBN: (纸本)9798350382495

In the paper we consider the discrete variant of the well-known Influence Maximization Problem (IMP). Given some influence model, it consists in finding a so-called seed set of influential users of fixed size, that maximizes the total spread of influence over the network. We limit our study to the influence model called Deterministic Linear Threshold Model (DLTM). It is well known that IMP under DLTM is computationally hard and there are no approximate algorithms for its solving with a constant approximation ratio if P≠ NP. Therefore, it makes sense to apply metaheuristic algorithms to this problem. In the present research we propose new algorithms for solving IMP under DLTM, which are based on a technique that combines evolutionary and genetic strategies for pseudo-Boolean optimization with a greedy algorithm which is used to find some initial approximation. We use the proposed strategy to solve another well-known combinatorial problem for networks called Target Set Selection (TSS). We propose to solve TSS as a sequence of IMPs with gradually decreasing of target set size. In the experimental part of the paper we demonstrate that our new strategy outperforms the previous ways to solve TSS, yielding smaller target sets of good quality. © 2024 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：