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

10th International Conference on Antenna Theory and Techniques (ICATT)

作者： Prijmenko, S. D. Bondarenko, L. A. NSC KIPT Inst Plasma Elect & New Methods Accelerat Kharkov Ukraine

ISBN: (纸本)9781479985579

The approximation algorithm to the tensor Green's function calculation in the D'Alembert equation for the polarization potential in the circular waveguide is proposed. The tensor Green's function is presented in the sourcewise form as the sum of the Green's function for free space and the regular part caused by reflections from the waveguide walls. The circular waveguide is a circular cylinder with a directrix in the form of a circle. The directrix in the form of a circle is approximated by a broken line in the form of an inscribed rectilinear polygon. This approximation allows one to use the method of specular reflections and get the tensor Green's function as an infinite sum of tensor divergent spherical waves with a delta-shaped front. The resulting representation of the Green's function can be used to solve the nonstationary intrinsic boundary-value problems of electrodynamics in the case of a circular waveguide with consideration for the reflections from the walls.

关键词： Sourcewise tensor Green's function circular waveguide D'Alembert equation approximation algorithm specular reflections

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the dynamic k-level facility location problems

引用

THEORETICAL COMPUTER SCIENCE 2021年 853卷 43-56页

作者： Wang, Limin Zhang, Zhao Wu, Chenchen Xu, Dachuan Zhang, Xiaoyan Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Nanjing Normal Univ Sch Math Sci Nanjing 210023 Jiangsu Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Jiangsu Peoples R China

In this paper, we first consider a dynamic k-level facility location problem, which is a generalization of the k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for this problem which finds a constant factor approximate solution. Then, we investigative the dynamic k-level facility location problem with submodular penalties and outliers, which extend the existing problem on two fronts, namely from static to dynamic and from without penalties (outliers) to penalties (outliers) allowed. Based on primal-dual technique and the triangle inequality property, we also give two constant factor approximation algorithms for the dynamic problem with submodular penalties and outliers, respectively. (C) 2020 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Primal-dual Dynamic Facility location Submodular penalties Outliers

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for two clustered arc routing problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第5期47卷 88-88页

作者： Bao, Xiaoguang Ni, Xinhao Shanghai Ocean Univ Coll Informat Technol Shanghai 201306 Peoples R China

Given a strongly connected mixed graph G=(V,E,A)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G=(V,E,A)$$\end{document}, where V represents the vertex set, E is the undirected edge set, and A is the directed arc set, R subset of E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R \subseteq E$$\end{document} is a subset of required edges and is divided into p clusters R1,R2,& ctdot;,Rp\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R_1,R_2,\dots ,R_p$$\end{document}, and A is a set of required arcs and is partitioned into q clusters A1,A2,& mldr;,Aq\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A_1,A_2,\ldots ,A_q$$\end{document}. Each edge in E and each arc in A are associated with a nonnegative weight and the weight function satisfies the triangle inequality. In this paper we consider two clustered arc routing problems. The first is the Clustered Rural Postman Problem, in which A is empty and the objective is to find a minimum-weight closed walk such that all the edges in R are serviced and the edges in Ri\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R_i$$\end{document

关键词： Arc routing Rural postman problem Stacker crane problem Cluster approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for profit maximisation in multicast D2D networks

引用

INTERNATIONAL JOURNAL OF AD HOC AND UBIQUITOUS COMPUTING 2021年第1期36卷 8-19页

作者： Bhat, Jagadeesha R. Sheu, Jang-Ping Hon, Wing-Kai Yang, Cian-You St Joseph Engn Coll Dept ECE Mangalore India Natl Tsing Hua Univ Dept Comp Sci Hsinchu Taiwan

As the demand for mobile data services increases, telecom companies need to develop wise strategies to retain existing customers. For instance, in a multicast scenario, satisfying individual user's quality of service (QoS), data demand at varying rates, etc. are complicated tasks. Earlier works on device-to-device (D2D) multicast have majorly discussed the cases of throughput maximisation without considering the individual user's data request rates. In this paper, we propose two algorithms to maximise the telecom operator's profit collected from the users in a two-hop D2D multicast network, when users have different channel qualities and data request rates while receiving multicast data through a single transmission session. First, we model our multicast scheme for the proposed scenario as a budgeted maximum coverage problem. Later, we propose two approximation algorithms that guarantee approximation ratios of 1-1/root e and 1 - 1/e, respectively, where e denotes the base of the natural logarithm. Numerical results show that the proposed algorithms perform better than the other candidate algorithms and nearly approximates the optimal solution.

关键词： mobile data multicast approximation algorithm device-to-device D2D

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for some position-dependent scheduling problems

引用

DISCRETE APPLIED MATHEMATICS 2021年 289卷 22-31页

作者： Yang, Liya Lu, Xiwen East China Univ Sci & Technol Sch Sci Dept Math Shanghai 200237 Peoples R China

The general position-dependent scheduling problems are studied in this paper. A 2-approximation algorithm is proposed for the learning scheduling problem on a single machine with release time to minimize the makespan. To minimize the total completion time on a single machine with release time and learning effect, we design a 2-approximation algorithm and a PTAS. Moreover, for the deteriorating scheduling problem to minimize the makespan on parallel machines, a 2-approximation algorithm is provided. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Scheduling Position-dependent Learning scheduling Deteriorating scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Clever Steady Strategy algorithm: A simple and efficient approximation algorithm for minimum vertex cover problem 13

<i>Clever Steady Strategy Algorithm</i>: A simple and effici...

引用

13th International Conference Frontiers Information Technology (FIT 2015)

作者： Fayaz, Muhammad Arshad, Shakeel Univ Malakand Dept Comp Sci & Informat Technol Kpk Pakistan

ISBN: (纸本)9781509003297

This paper presents a simple and fast polynomial time algorithm, the clever, steady strategy algorithm (CSSA). The proposed algorithm consists of three stages which produces optimal or approximate vertex cover for any unknown un-weighted and undirected G = (V, E). In the first step the degree of each node of the given graph is calculated. In second step the minimum degree node(s) is find and also the adjacent nodes of minimum degree nodes are find. In the third stage the minimum degree node in all adjacent nodes of minimum degree is searched out and is selected as a candidate for MVC and all its edges are deleted. These three steps are processed repeatedly until no edge remains in the graph. The CSSA is tested on small as well as on large benchmark instances. The experimental results and comparative analysis show that the CSSA yields better and fast solution than those approximation algorithms found in literature for solving minimum vertex cover problem.

关键词： Minimum vertex cover (MVC) maximum independent set (MIS) NP-complete problem optimization problem approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for fuzzy C-means problem based on seeding method

引用

THEORETICAL COMPUTER SCIENCE 2021年 885卷 146-158页

作者： Liu, Qian Liu, Jianxin Li, Min Zhou, Yang Shandong Normal Univ Sch Math & Stat Jinan Peoples R China

As a kind of important soft clustering model, the fuzzy C-means method is widely applied in many fields. In this method, instead of the strict distributive ability in the classical k-means method, all the sample points are endowed with degrees of membership to each center to depict the fuzzy clustering. In this paper, we show that the fuzzy C-means++ algorithm, which introduces the k-means++ algorithm as a seeding strategy, gives a solution for which the approximation guarantee is O(k(2) ln k). A novel seeding algorithm is then designed based on the contribution of the fuzzy potential function, which improves the approximation ratio to O(k lnk). Preliminary numerical experiments are proposed to support the theoretical results of this paper. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Fuzzy C-means problem Seeding algorithm approximation algorithm approximation ratio

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Maximally Balanced Connected Graph Partition

引用

algorithmICA 2021年第12期83卷 3715-3740页

作者： Chen, Yong Chen, Zhi-Zhong Lin, Guohui Xu, Yao Zhang, An Hangzhou Dianzi Univ Dept Math Hangzhou Peoples R China Tokyo Denki Univ Div Informat Syst Design Saitama Japan Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Georgia So Univ Dept Comp Sci Statesboro GA 30460 USA

Given a connected graph G = (V, E), we seek to partition the vertex set V into k non-empty parts such that the subgraph induced by each part is connected, and the partition is maximally balanced in the way that the maximum cardinality of these k parts is minimized. We refer this problem to as min-max balanced connected graph partition into k parts and denote it as k-BGP. The vertex-weighted version of this problem on trees has been studied since about four decades ago, which admits a linear time exact algorithm. The vertex-weighted 2-BGP and 3-BGP admit a 5/4-approximation and a 3/2-approximation, respectively. When k >= 4, no approximability result exists for k-BGP, i.e., the vertex unweighted variant, except a trivial k-approximation. In this paper, we present another 3/2-approximation for the 3-BGP and then extend it to become a k/2-approximation for k-BGP, for any fixed k >= 3. Furthermore, for 4-BGP, we propose an improved 24/13-approximation. To these purposes, we have designed several local improvement operations, which could find more applications in related graph partition problems.

关键词： Graph partition Induced subgraph Connected component Local improvement approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the Two-Stage Distributionally Robust Facility Location Problem 3

An Approximation Algorithm for the Two-Stage Distributionall...

引用

3rd World Congress of Global Optimization (WCGO)

作者： Wu, Chenchen Du, Donglei Xu, Dachuan Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China Beijing Univ Technol Dept Appl Math Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 9Y2 Canada

ISBN: (纸本)9783319083773;9783319083766

In this paper, we introduce a model of distributionally robust facility location problem (DRFLP) under moment constraints up to the second order. We show, via duality theory of moment problems, that the linear relaxation of the DRFLP is equivalent to that of the standard uncapacitated facility location problem (UFLP). Consequently, any LP-based approximation algorithm for the UFLP implies an approximation algorithm for the DRFLP with the same approximation ratio.

关键词： Facility location problem approximation algorithm Distributionally robust optimization

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the multiprocessor scheduling with submodular penalties

引用

OPTIMIZATION LETTERS 2021年第6期15卷 2165-2180页

作者： Liu, Xiaofei Li, Weidong Peking Univ Sch Elect Engn & Comp Sci Beijing Peoples R China Yunnan Univ Sch Math & Stat Kunming Yunnan Peoples R China

In this paper, we consider multiprocessor scheduling with submodular penalties to extend multiprocessor scheduling with rejection to submodular function. An instance of the problem is given by n jobs and m machines with each job having a certain processing time on a machine. We aim to find a subset R of rejected jobs, and assign each of other jobs to one of the m machines. The objective is to minimize the sum of the makespan of the m machines and the rejection penalty R, where the rejection penalty is determined by a submodular function. For this problem, we design a non-combinatorial Lovasz rounding algorithm that achieves a worst-case guarantee of 3+52. Then, we consider a special case of this problem in which all the machines are identical, i.e. each job has the same processing time on any machine, and we design a combinatorial (2-1m-approximation algorithm based on the greedy method and list scheduling (LS) algorithm.

关键词： Multiprocessor scheduling Submodular penalties approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：