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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Approximability of Edge-Vertex Domination in Unit Disk Graphs 2nd

Approximability of Edge-Vertex Domination in Unit Disk Gra...

引用

2nd International Conference on Applied algorithms, ICAA 2025

作者： Singireddy, Vishwanath R. Basappa, Manjanna Geethanjali College of Engineering and Technology Cheeryala Keesara Hyderabad501301 India National Institute of Technology Karnataka Surathkal Mangaluru575025 India

ISBN: (纸本)9783031845420

Given an undirected graph G=(V,E), a vertex v∈V is edge-vertex (ev) dominated by an edge e∈E if v is either incident to e or incident to an adjacent edge of e. A set Sev⊆E is an edge-vertex dominating set (referred to as ev-dominating set and in short as EVDS) of G if every vertex of G is ev-dominated by at least one edge of Sev. The minimum cardinality of an ev-dominating set is the ev-domination number. The edge-vertex dominating set problem is to find a minimum ev-domination number. The EVDS problem finds applications in handling security issues in the communication network by identifying a minimum number of critical edges to implement additional security measures to safeguard key components of the network. In this paper, we prove that this problem admits a polynomial-time approximation scheme in unit disk graphs. We also give a simple 5-factor linear-time approximation algorithm. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.

关键词： 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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficient approximation of Two-Terminal Networks Reliability Polynomials Using Cubic Splines

引用

IEEE TRANSACTIONS ON RELIABILITY 2021年第3期70卷 1193-1203页

作者： Cristescu, Gabriela Dragoi, Vlad-Florin Aurel Vlaicu Univ Arad Dept Math & Comp Sci Arad 310032 Romania

In this article, two new techniques of approximation of the reliability of a two-terminal network are developed based on the constructive theory of functions and related methods. Two methods of generating an approximation cubic spline are used: Lagrange-type interpolation procedures and Bernstein approximation operator. A possibility of minimizing the total error of approximation, based on keeping some properties invariant, is described in case of a large class of pairs of dual two-terminal networks. Simulations are included, showing that the error of approximation is negligible in case of some special initial data.

关键词： Reliability Computer network reliability Telecommunication network reliability Splines (mathematics) Reliability theory approximation algorithms Integrated circuit reliability Bernstein polynomial cubic spline approximation interpolation reliability polynomial two-terminal network (2TN)

来源：评论

学校读者我要写书评

暂无评论

An approximation Algorithm for Unrelated Parallel Machine Scheduling Under TOU Electricity Tariffs

引用

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING 2021年第2期18卷 743-756页

作者： Pei, Zhi Wan, Mingzhong Jiang, Zhong-Zhong Wang, Ziteng Dai, Xu Zhejiang Univ Technol Coll Mech Engn Hangzhou 310023 Peoples R China Northeastern Univ Sch Business Adm Shenyang 110167 Peoples R China Northeastern Univ Inst Behav & Serv Operat Management Shenyang 110167 Peoples R China Northeastern Univ Key Lab Data Analyt & Optimizat Smart Ind Minist Educ Shenyang 110167 Peoples R China Northern Illinois Univ Dept Ind & Syst Engn De Kalb IL 60115 USA

In an era of sustainable development, considerable emphasis has been put onto energy saving, environment friendly, and social welfare as well as productivity in the manufacturing sector. In this work, an unrelated parallel manufacturing setting with time-of-use (TOU) electricity price is explored, with an aim to reduce the electricity cost and increase productivity simultaneously. A nonlinear mathematical programming model is formulated to exploit the special structure of the scheduling problem, where the quadratic constraints are reformulated as second-order-cone (SOC) constraints, and several tailored cutting planes are introduced to further tighten the feasible region of the problem. Then, the original scheduling problem is transformed into several single-machine scheduling problems with TOU electricity price, which could be relaxed as a single-objective programming problem, and it could be solved rapidly via commercial solvers, such as CPLEX. Based on the optimal solution of the relaxed problem, an approximate algorithm is proposed, where a special rounding technique is employed to assign jobs to the unrelated parallel machines in a local search manner. Furthermore, a lower bound model is constructed by eliminating the nonpreemption constraint, and an iteration-based algorithm is devised to obtain the optimal solution of the lower bound problem. Meanwhile, a dispatch rule-based approach is proposed to provide an upper bound of the scheduling problem with TOU constraint. In the numerical analysis section, the proposed approximate algorithm is validated through extensive testing on various scales of instances, different emphasis on productivity and electricity price, and under two typical TOU electricity pricing policies. It is observed that the gap between the proposed approximate algorithm and CPLEX is mostly within 4%, and the lower/upper bound methods could obtain a relaxed/feasible solution within 0.01 s. Note to Practitioners-Energy saving together with prod

关键词： Job shop scheduling Parallel machines approximation algorithms Single machine scheduling Pricing Productivity Approximate algorithm cutting plane lower bound second-order-cone (SOC) time-of-use (TOU) unrelated parallel machine scheduling

来源：评论

学校读者我要写书评

暂无评论

TOWARD TIGHT approximation BOUNDS FOR GRAPH DIAMETER AND ECCENTRICITIES

引用

SIAM JOURNAL ON COMPUTING 2021年第4期50卷 1155-1199页

作者： Backurs, Arturs Roditty, Liam Segal, Gilad Williams, Virginia Vassilevska Wein, Nicole MIT 77 Massachusetts Ave Cambridge MA 02139 USA Bar Ilan Univ Comp Sci Tel Aviv Israel Bar Ilan Univ Comp Sci Ramat Gan Israel MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA MIT EECS 77 Massachusetts Ave Cambridge MA 02139 USA

Among the most important graph parameters is the diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the diameter exactly. Thus, much research has been devoted to how fast this parameter can be approximated. Chechik et al. [Proceedings of SODA 2014, Portland, OR, 2014, pp. 1041--1052] showed that the diameter can be approximated within a multiplicative factor of 3/2 in (O) over tilde (m(3/2)) time. Furthermore, Roditty and Vassilevska W. [Proceedings of STOC '13, New York, ACM, 2013, pp. 515--524] showed that unless the strong exponential time hypothesis (SETH) fails, no O(n(2-epsilon)) time algorithm can achieve an approximation factor better than 3/2 in sparse graphs. Thus the above algorithm is essentially optimal for sparse graphs for approximation factors less than 3/2. It was, however, completely plausible that a 3/2-approximation is possible in linear time. In this work we conditionally rule out such a possibility by showing that unless SETH fails no O(m(3/2 -epsilon)) time algorithm can achieve an approximation factor better than 5/3. Another fundamental set of graph parameters is the eccentricities. The eccentricity of a vertex v is the distance between v and the farthest vertex from v. Chechik et al. [Proceedings of SODA 2014, Portland, OR, 2014, pp. 1041--1052] showed that the eccentricities of all vertices can be approximated within a factor of 5/3 in O (m(3/2)) time and Abboud, Vassilevska W., and Wang [Proceedings of SODA 2016, Arlington, VA, 2016, pp. 377--391] showed that no O(n(2-epsilon)) algorithm can achieve better than 5/3 approximation in sparse graphs. We show that the runtime of the 5/3 approximation algorithm is also optimal by proving that under SETH, there is no O(m(3/2-epsilon)) algorithm that achieves a better than 9/5 approximation. We also show that no near-linear time algorithm can achieve a better than 2 approximation for the eccentricities. This is the first lower bound

关键词： graph diameter approximation algorithms fine-grained complexity

来源：评论

学校读者我要写书评

暂无评论

A Deep-Network Piecewise Linear approximation Formula

引用

IEEE ACCESS 2021年 9卷 120665-120674页

作者： Zeng, Gengsheng L. Utah Valley Univ Dept Comp Sci Orem UT 84058 USA Univ Utah Dept Radiol & Imaging Sci Salt Lake City UT 84108 USA

The mathematical foundation of deep learning is the theorem that any continuous function can be approximated within any specified accuracy by using a neural network with certain non-linear activation functions. However, this theorem does not tell us what the network architecture should be and what the values of the weights are. One must train the network to estimate the weights. There is no guarantee that the optimal weights can be reached after training. This paper develops an explicit architecture of a universal deep network by using the Gray code order and develops an explicit formula for the weights of this deep network. This architecture is target function independent. Once the target function is known, the weights are calculated by the proposed formula, and no training is required. There is no concern whether the training may or may not reach the optimal weights. This deep network gives the same result as the shallow piecewise linear interpolation function for an arbitrary target function.

关键词： Neurons Reflective binary codes Interpolation Deep learning Training Licenses Adders approximation algorithms artificial neural networks function approximation interpolation multi-layer neural network

来源：评论

学校读者我要写书评

暂无评论

Facility Location on High-Dimensional Euclidean Spaces 16

Facility Location on High-Dimensional Euclidean Spaces

引用

16th Innovations in Theoretical Computer Science Conference, ITCS 2025

作者： Lee, Euiwoong Shin, Kijun University of Michigan Ann ArborMI United States Seoul National University Korea Republic of

ISBN: (纸本)9783959773614

Recent years have seen great progress in the approximability of fundamental clustering and facility location problems on high-dimensional Euclidean spaces, including k-Means and k-Median. While they admit strictly better approximation ratios than their general metric versions, their approximation ratios are still higher than the hardness ratios for general metrics, leaving the possibility that the ultimate optimal approximation ratios will be the same between Euclidean and general metrics. Moreover, such an improved algorithm for Euclidean spaces is not known for Uncapaciated Facility Location (UFL), another fundamental problem in the area. In this paper, we prove that for any γ ≥ 1.6774 there exists Ε > 0 such that Euclidean UFL admits a (γ, 1 + 2e-γ - Ε)-bifactor approximation algorithm, improving the result of Byrka and Aardal [3]. Together with the (γ, 1 + 2e-γ) NP-hardness in general metrics, it shows the first separation between general and Euclidean metrics for the aforementioned basic problems. We also present an (αLi - Ε)-(unifactor) approximation algorithm for UFL for some Ε > 0 in Euclidean spaces, where αLi ≈ 1.488 is the best-known approximation ratio for UFL by Li [15]. © Euiwoong Lee and Kijun Shin.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：