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

16th Innovations in Theoretical Computer Science Conference, ITCS 2025

作者： Mahabadi, Sepideh Roghani, Mohammad Tarnawski, Jakub Vakilian, Ali Microsoft Research RedmondWA United States Stanford University CA United States IL United States

ISBN: (纸本)9783959773614

We study the metric Steiner tree problem in the sublinear query model. In this problem, for a set of n points V in a metric space given to us by means of query access to an n × n matrix w, and a set of terminals T ⊆ V, the goal is to find the minimum-weight subset of the edges that connects all the terminal vertices. Recently, Chen, Khanna and Tan [SODA’23] gave an algorithm that uses Oe(n13/7) queries and outputs a (2 - η)-estimate of the metric Steiner tree weight, where η > 0 is a universal constant. A key component in their algorithm is a sublinear algorithm for a particular set cover problem where, given a set system (U, F), the goal is to provide a multiplicative-additive estimate for |U|-SC(U, F). Here U is the set of elements, F is the collection of sets, and SC(U, F) denotes the optimal set cover size of (U, F). In particular, their algorithm returns a (1/4, Ε · |U|)-multiplicative-additive estimate for this set cover problem using Oe(|F|7/4) membership oracle queries (querying whether a set S ∈ S contains an element e ∈ U), where Ε is a fixed constant. In this work, we improve the query complexity of (2 - η)-estimating the metric Steiner tree weight to Oe(n5/3) by showing a (1/2, Ε· |U|)-estimate for the above set cover problem using Oe(|F|5/3) membership queries. To design our set cover algorithm, we estimate the size of a random greedy maximal matching for an auxiliary multigraph that the algorithm constructs implicitly, without access to its adjacency list or matrix. Previous analyses of random greedy maximal matching have focused on simple graphs, assuming access to their adjacency list or matrix. To address this, we extend the analysis of Behnezhad [FOCS’21] of random greedy maximal matching on simple graphs to multigraphs, and prove additional properties that may be of independent interest. © Sepideh Mahabadi, Mohammad Roghani, Jakub Tarnawski, and Ali Vakilian.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Cross Tensor approximation Methods for Compression and Dimensionality Reduction

引用

IEEE ACCESS 2021年 9卷 150809-150838页

作者： Ahmadi-Asl, Salman Caiafa, Cesar F. Cichocki, Andrzej Phan, Anh Huy Tanaka, Toshihisa Oseledets, Ivan Wang, Jun Skolkovo Inst Sci & Technol SKOLTECH ICDISE Moscow 121205 Russia CONICET CIC PBA UNLP Inst Argentino Radioastron CCT La Plata RA-1894 Villa Elisa Argentina RIKEN Ctr Adv Intelligence Project AIP Tokyo 1030027 Japan Tokyo Univ Agr & Technol Dept Elect & Elect Engn Tokyo 1838509 Japan

Cross Tensor approximation (CTA) is a generalization of Cross/skeleton matrix and CUR Matrix approximation (CMA) and is a suitable tool for fast low-rank tensor approximation. It facilitates interpreting the underlying data tensors and decomposing/compressing tensors so that their structures, such as nonnegativity, smoothness, or sparsity, can be potentially preserved. This paper reviews and extends state-of-the-art deterministic and randomized algorithms for CTA with intuitive graphical illustrations. We discuss several possible generalizations of the CMA to tensors, including CTAs: based on fiber selection, slice-tube selection, and lateral-horizontal slice selection. The main focus is on the CTA algorithms using Tucker and tubal SVD (t-SVD) models while we provide references to other decompositions such as Tensor Train (TT), Hierarchical Tucker (HT), and Canonical Polyadic (CP) decompositions. We evaluate the performance of the CTA algorithms by extensive computer simulations to compress color and medical images and compare their performance.

关键词： Tensors approximation algorithms Matrix decomposition Signal processing algorithms Sparse matrices Optimization Licenses CUR algorithms cross approximation tensor decomposition tubal SVD randomization

来源：评论

学校读者我要写书评

暂无评论

An Improved approximation Algorithm for the Minimum k-Edge Connected Multi-subgraph Problem 2022

An Improved Approximation Algorithm for the Minimum k-Edge C...

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Karlin, Anna R. Klein, Nathan Gharan, Shayan Oveis Zhang, Xinzhi Univ Washington Seattle WA 98195 USA

We give a randomized 1 + 5.06/root k -approximation algorithm for the minimum k-edge connected spanning multi-subgraph problem, k-ECSM.

ISBN: (纸本)9781450392648

We give a randomized 1 + 5.06/root k -approximation algorithm for the minimum k-edge connected spanning multi-subgraph problem, k-ECSM.

关键词： approximation algorithms Edge Connectivity Network Design Randomized Rounding Max Entropy Strongly Rayleigh

来源：评论

学校读者我要写书评

暂无评论

A constant-factor approximation algorithm for Nash Social Welfare with submodular valuations 62

A constant-factor approximation algorithm for Nash Social We...

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Li, Wenzheng Vondrak, Jan Stanford Univ Dept Comp Sci Stanford CA 94305 USA Stanford Univ Dept Math Stanford CA 94305 USA

We present a 380-approximation algorithm for the Nash Social Welfare problem with submodular valuations. Our algorithm builds on and extends a recent constant-factor approximation for Rado valuations [15].

ISBN: (纸本)9781665420556

关键词： Nash social welfare approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel Path Progression DAG Scheduling

引用

IEEE TRANSACTIONS ON COMPUTERS 2023年第10期72卷 3002-3016页

作者： Ueter, Niklas Guenzel, Mario Von der Brueggen, Georg Chen, Jian-Jia TU Dortmund Univ Design Automat Embedded Syst Grp D-44227 Dortmund Germany

Increasing performance needs of modern cyber-physical systems leads to multiprocessor architectures being increasingly utilized. To efficiently exploit their potential parallelism in hard real-time systems, appropriate task models and scheduling algorithms that allow to provide timing guarantees are required. Such scheduling algorithms and the corresponding worst-case response time analyses usually suffer from resource over-provisioning due to pessimistic analyses based on worst-case assumptions. Hence, scheduling algorithms and analyses with high resource efficiency are required. A prominent fine-grained parallel task model is the directed-acyclic-graph (DAG) task model that is composed of precedence constrained subjobs. This paper studies the hierarchical real-time scheduling problem of sporadic arbitrary-deadline DAG tasks. We propose a parallel path progression scheduling property that is implemented with only two distinct subtask priorities, which allows to quantify the parallel execution of a user chosen collection of complete paths in the response time analysis. This novel approach significantly improves the state-of-the-art response time analyses for parallel DAG tasks for highly parallel DAG structures and can provably exhaust large core numbers. Two hierarchical scheduling algorithms are designed based on this property, extending the parallel path progression properties and improve the response time analysis for sporadic arbitrary-deadline DAG task sets.

关键词： Real-time DAG scheduling homogeneous multicore platforms hierarchical scheduling approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Joint Embedding Learning and Low-Rank approximation: A Framework for Incomplete Multiview Learning

引用

IEEE TRANSACTIONS ON CYBERNETICS 2021年第3期51卷 1690-1703页

作者： Tao, Hong Hou, Chenping Yi, Dongyun Zhu, Jubo Hu, Dewen Natl Univ Def Technol Coll Liberal Arts & Sci Changsha 410073 Peoples R China Natl Univ Def Technol Coll Mechatron & Automat Changsha 410073 Peoples R China

In real-world applications, not all instances in the multiview data are fully represented. To deal with incomplete data, incomplete multiview learning (IML) rises. In this article, we propose the joint embedding learning and low-rank approximation (JELLA) framework for IML. The JELLA framework approximates the incomplete data by a set of low-rank matrices and learns a full and common embedding by linear transformation. Several existing IML methods can be unified as special cases of the framework. More interestingly, some linear transformation-based complete multiview methods can be adapted to IML directly with the guidance of the framework. Thus, the JELLA framework improves the efficiency of processing incomplete multiview data, and bridges the gap between complete multiview learning and IML. Moreover, the JELLA framework can provide guidance for developing new algorithms. For illustration, within the framework, we propose the IML with the block-diagonal representation (IML-BDR) method. Assuming that the sampled examples have an approximate linear subspace structure, IML-BDR uses the block-diagonal structure prior to learning the full embedding, which would lead to more correct clustering. A convergent alternating iterative algorithm with the successive over-relaxation optimization technique is devised for optimization. The experimental results on various datasets demonstrate the effectiveness of IML-BDR.

关键词： Clustering algorithms Optimization Bridges Cameras Cybernetics approximation algorithms Iterative methods Block-diagonal representation (BDR) embedding learning incomplete multiview learning (IML) low-rank approximation

来源：评论

学校读者我要写书评

暂无评论

Optimizing Resource Allocation With High-Reliability Constraint for Multicasting Automotive Messages in 5G NR C-V2X Networks

引用

IEEE Transactions on Vehicular Technology 2023年第4期72卷 4792-4804页

作者： Chen, Kuan-Lin Chen, Wei-Yu Hwang, Ren-Hung National Chung Cheng University Department of Computer Science and Informational Engineering Chiayi621 Taiwan Taipei115 Taiwan National Yang Ming Chiao Tung University College of Artificial Intelligence Tainan711 Taiwan

Cellular vehicle-to-everything (C-V2X) has been continuously evolving since Release 14 of the 3rd Generation Partnership Project (3GPP) for future autonomous vehicles. Apart from automotive safety, 5G NR further bring new capabilities to C-V2X for autonomous driving, such as real-time local update, and coordinated driving. These capabilities rely on the provision of low latency and high reliability from 5G NR. Among them, a basic demand is broadcasting or multicasting environment update messages, such as cooperative perception data, with high reliability and low latency from a Road Side Unit (RSU) or a base station (BS). In other words, broadcasting multiple types of automotive messages with high reliability and low latency is one of the key issues in 5G NR C-V2X. In this work, we consider how to select Modulation and Coding Scheme (MCS), RSU/BS, Forward Error Correction (FEC) code rate, to maximize the system utility, which is a function of message delivery reliability. We formulate the optimization problem as a nonlinear integer programming problem. Since the optimization problem is NP-hard, we propose an approximation algorithm, referred to as the Hyperbolic Successive Convex approximation (HSCA) algorithm, which uses the successive convex approximation to find the optimal solution. In our simulations, we compare the performance of HSCA with those of three algorithms respectively, including the baseline algorithm, the heuristic algorithm, and the optimal solution. Our simulation results show that HSCA outperforms the baseline and the heuristic algorithms and is very competitive to the optimal solution. © 1967-2012 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Dual-Objective Personalized Federated Service System With Partially-Labeled Data Over Wireless Networks

引用

IEEE Transactions on Services Computing 2023年第5期16卷 3265-3279页

作者： Ching, Cheng-Wei Chang, Jia-Ming Kuo, Jian-Jhih Wang, Chih-Yu Ucsc Department of Computer Science and Engineering Santa CruzCA95064 United States Academia Sinica Research Center for Information Technology Innovation Taipei City11529 Taiwan National Chung Cheng University Department of Computer Science and Information Engineering Chiayi62102 Taiwan Advanced Institute of Manufacturing with Hightech Innovations National Chung Cheng University Chiayi62102 Taiwan

Federated learning (FL) emerges to mitigate the privacy concerns in machine learning-based services and applications, and personalized federated learning (PFL) evolves to alleviate the issue of data heterogeneity. However, FL and PFL usually rest on two assumptions: the users' data is well-labeled, or the personalized goals align with sufficient local data. Unfortunately, the two assumptions may not hold in most cases, where data labeling is costly, or most users have no sufficient local data to satisfy their personalized needs. To this end, we first formulate the problem, DoLP, that studies the issue of insufficient and partially-labeled data on FL-based services. DoLP aims to maximize two service objectives: 1) personalized classification objective and 2) the personalized labeling objective for each user within the constraint of training time over wireless networks. Then, we propose a PFL-based service system DoFed-SPP to solve DoLP. The DoFed-SPP's novelty is two-fold. First, we devise an inference-based first-order approximation metric, similarity ratio, to identify the similarity between users' local data. Second, we design an approximation algorithm to determine the appropriate size and set of users for uploading in each round. Extensive experiments show DoFed-SPP outperforms the state-of-the-art in final accuracy and time-to-accuracy performance on CIFAR10/100 and DBPedia. © 2008-2012 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

It is Not 'Accuracy vs. Explainability'-We Need Both for Trustworthy AI Systems

IEEE Transactions on Technology and Society

引用

IEEE Transactions on Technology and Society 2023年第1期4卷 46-53页

作者： Petkovic, Dragutin San Francisco State University Computer Science Department San FranciscoCA94132 United States

We are witnessing the emergence of an 'AI economy and society' where AI technologies and applications are increasingly impacting health care, business, transportation, defense and many aspects of everyday life. Many successes have been reported where AI systems even surpassed the accuracy of human experts. However, AI systems may produce errors, can exhibit bias, may be sensitive to noise in the data, and often lack technical and judicial transparency resulting in reduction in trust and challenges to their adoption. These recent shortcomings and concerns have been documented in both the scientific and general press such as accidents with self-driving cars, biases in healthcare or hiring and face recognition systems for people of color, and seemingly correct decisions later found to be made due to wrong reasons etc. This has resulted in the emergence of many government and regulatory initiatives requiring trustworthy and ethical AI to provide accuracy and robustness, some form of explainability, human control and oversight, elimination of bias, judicial transparency and safety. The challenges in delivery of trustworthy AI systems have motivated intense research on explainable AI systems (XAI). The original aim of XAI is to provide human understandable information of how AI systems make their decisions in order to increase user trust. In this paper we first very briefly summarize current XAI work and then challenge the recent arguments that present 'accuracy vs. explainability' as being mutually exclusive and for focusing mainly on deep learning with its limited XAI capabilities. We then present our recommendations for the broad use of XAI in all stages of delivery of high stakes trustworthy AI systems, e.g., development;validation/certification;and trustworthy production and maintenance. © 2020 IEEE.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Parity-Constrained k-Supplier Problem 18th

Parity-Constrained k-Supplier Problem

引用

18th International Joint Conference on Theoretical Computer Science-Frontier of Algorithmic Wisdom, IJTCS-FAW 2024

作者： Xia, Xinlan Han, Lu Mei, Lili School of Science Beijing University of Posts and Telecommunications Beijing China School of Cyberspace Hangzhou Dianzi University Hangzhou China

ISBN: (纸本)9789819777518

In this paper, we propose and study the parity-constrained k-supplier (PAR k-supplier) problem, generalizing the classical (unconstrained) k-supplier problem. In the PAR k-supplier problem, we are given a set of facilities and a set of clients in a metric space with distances. An integer k is also given. Each facility is associated with an odd or even parity requirement. The goal is to open at most k facilities and assign each client to an opened facility, such that the number of clients assigned to a facility meets its parity requirement, and the maximum distance of any client to its assigned facility is minimized. As our main contribution, we provide a constant-factor approximation algorithm for the PAR k-supplier problem with a ratio of 9. Our algorithm proceeds by first ignoring all parity requirements and constructing an (unconstrained) k-supplier instance. Next, we design an algorithm to solve the constructed instance and obtain a solution that may have some invalid facilities. An invalid facility is an opened facility whose parity requirement is violated. Last, to obtain a feasible solution, we match up all the invalid facilities and make reassignments according to each invalid pair. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：