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

Improved approximation algorithms for k-submodular maximization under a knapsack constraint

COMPUTERS & OPERATIONS RESEARCH 2024年 161卷

作者： Ha, Dung T. K. V. Pham, Canh Tran, Tan D. VNU Univ Engn Technol Hanoi 11300 Vietnam Phenikaa Univ ORLab Hanoi 12116 Vietnam

We investigate the problem of k-submodular maximization under a knapsack constraint over the ground set of size... This problem finds many applications in various fields, such as multi-topic propagation, multi-sensor placement, cooperative games, etc. However, existing algorithms for the studied problem face challenges in practice as the size of instances increases in practical applications. This paper introduces three deterministic and approximation algorithms for the problem that significantly improve both the approximation ratio and query complexity of existing practical algorithms. Our first algorithm, FA, returns an approximation ratio of 1/10 within O(nk) query complexity. The second one, IFA, improves the approximation ratio to 1/4-epsilon in O(nk/epsilon) queries. The last one IFA+ upgrades the approximation ratio to 1/3-epsilon in O(nk log(1/epsilon)/epsilon) query complexity, where.. is an accuracy parameter. Our algorithms are the first ones that provide constant approximation ratios within only O(nk) query complexity, and the novel idea to achieve results lies in two components. Firstly, we divide the ground set into two appropriate subsets to find the near-optimal solution over these ones with O(nk) queries. Secondly, we devise algorithmic frameworks that combine the solution of the first algorithm and the greedy threshold method to improve solution quality. In addition to the theoretical analysis, we have evaluated our proposed ones with several experiments in some instances: Influence Maximization, Information Coverage Maximization, and Sensor Placement for the problem. The results confirm that our algorithms ensure theoretical quality as the cutting-edge techniques, including streaming and non-streaming algorithms, and also significantly reduce the number of queries.

关键词： Combinatorial optimization approximation algorithm k-submodular Knapsack constraint

来源：评论

学校读者我要写书评

暂无评论

A primal-dual 3-approximation algorithm for the stochastic facility location problem with submodular penalties

引用

OPTIMIZATION 2015年第3期64卷 617-626页

作者： Xu, Dachuan Gao, Dongxiao Wu, Chenchen Beijing Univ Technol Dept Appl Math Beijing Peoples R China Nankai Univ Sch Math Sci Tianjin 300071 Peoples R China

In this paper, we consider the stochastic facility location problem with submodular penalties. By exploring the structural properties of submodular function, we present a primal-dual -approximation algorithm for the p... 详细信息

关键词： 90C27 90C10 68W25 approximation algorithm stochastic facility location submodular function

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Analysis of an approximation algorithm for the m-Peripatetic Salesman Problem on Random Instances Unbounded from Above

引用

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS 2015年第1-Sup期289卷 S77-S87页

作者： Gimadi, E. Kh. Istomin, A. M. Rykov, I. A. Tsidulko, O. Yu. Russian Acad Sci Siberian Branch Sobolev Inst Math Novosibirsk 630090 Russia Novosibirsk State Univ Novosibirsk 630090 Russia

The probabilistic analysis of an approximation algorithm for the minimum-weight m-peripatetic salesman problem with different weight functions of their routes (Hamiltonian cycles) is presented. The time complexity of the algorithm is O(mn(2)). It is assumed that the elements of the distance matrix are independent equally distributed random variables with values in an upper unbounded domain [a(n),infinity), where a(n) > 0. The analysis is carried out for the example of truncated normal and exponential distributions. Estimates for the relative error and failure probability, as well as conditions for the asymptotic exactness of the algorithm, are found.

关键词： m-peripatetic salesman problem approximation algorithm time complexity asymptotic optimality random instances density function truncated normal distribution exponential distribution

来源：评论

学校读者我要写书评

暂无评论

Exact and approximation algorithms for the Multi-Depot Capacitated Arc Routing Problems

引用

Tsinghua Science and Technology 2023年第5期28卷 916-928页

作者： Wei Yu Yujie Liao Yichen Yang School of Mathematics East China University of Science and TechnologyShanghai 200237China Sabre Lab Research Team Sabre Inc.SouthlakeTX 76092USA

In this work,we investigate a generalization of the classical capacitated arc routing problem,called the Multi-depot Capacitated Arc Routing Problem(MCARP).We give exact and approximation algorithms for different variants of the ***,we obtain the first constant-ratio approximation algorithms for the MCARP and its nonfixed destination ***,for the multi-depot rural postman problem,i.e.,a special case of the MCARP where the vehicles have infinite capacity,we develop a(2-1/2k+1)-approximation algorithm(k denotes the number of depots).Third,we show the polynomial solvability of the equal-demand MCARP on a line and devise a 2-approximation algorithm for the multi-depot capacitated vehicle routing problem on a ***,we conduct extensive numerical experiments on the algorithms for the multi-depot rural postman problem to show their effectiveness.

关键词： approximation algorithm multi-depot vehicle routing problem arc routing problem rural postman problem

来源：评论

学校读者我要写书评

暂无评论

Fast and accurate approximation algorithms for computing floating point square root

引用

NUMERICAL algorithmS 2024年 1-24页

作者： Kokosinski, Zbigniew Gepner, Pawel Moroz, Leonid Samotyy, Volodymyr Wegrzyn, Mariusz Gavkalova, Nataliia Cracow Univ Technol Dept Automat Control & Comp Engn Warszawska 24 PL-31155 Krakow Poland Warsaw Univ Technol Fac Mech & Ind Engn Narbutta 85 PL-02524 Warsaw Poland

The square root is one of the most used functions in many different engineering and scientific applications. We propose new methods for calculating the square root function that are based on the Newton-Raphson method with Heron iteration. A modification of Heron's formula combined with an improved selection of the magic constants enables a significant reduction of the maximum relative error (MRE). Simple modifications to the Newton-Raphson formula and the magic number method enable implementation on platforms with limited hardware resources, such as microcontrollers and FPGAs, with variable accuracy. Implementations of new approximation algorithms in the C programming language were carefully tested and evaluated against their software and hardware counterparts on the most popular platforms, e.g., CPUs from Intel, AMD and ARM, GPU from Nvidia and IPU from Graphcore. The proposed numerical algorithms are shown to be superior in terms of computational time, the number of clock cycles, accuracy, MRE, and root mean square deviation.

关键词： Numerical algorithm approximation algorithm Function approximation Square root Newton-Raphson method Heron formula

来源：评论

学校读者我要写书评

暂无评论

A Novel approximation algorithm based on genetic programming in digital learning environment 4

A Novel approximation algorithm based on genetic programming...

引用

2015 International Conference of Educational Innovation Through Technology - (EITT)

作者： Li, Yaqin Yuan, Cao Zhang, Cong Li, Shigao Sun, Kaiqiong Wang, Xuan Wuhan Polytech Univ Sch Math & Comp Sci Wuhan 430023 Hubei Peoples R China Cent China Normal Univ Coll Hlth Sci & Nursing Wuhan 430023 Hubei Peoples R China

ISBN: (纸本)9781467380386

With the development of information and the integration of media, it has great practical significance and research value to build a digital learning environment based on the complicated electronic circuit. However, the complicated electronic circuit in real-time need a complex and expensive technology. In order to overcome the high cost and technology, an approach was proposed for simplifying generation by approximating the excitations with rectangular pulses, triangular pulses and cosine waves which can be implemented with a moderate cost in analogical electronics. In this work, we improved a novel approach based on genetic programming, The differences between theoretical excitation signals and the approximation driving pulses, related to their excitation effects, were minimized by genetic programming. From these results, the accuracy of simulation can be improved by the new approach, the difference between theoretical complicated digital signals and the new approach is reduced. A tradeoff is obtained between the costs of implementation of digital processing in digital learning environments.

关键词： genetic programming approximation algorithm digital learning environment

来源：评论

学校读者我要写书评

暂无评论

On parameterized approximation algorithms for balanced clustering

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-14页

作者： Kong, Xiangyan Zhang, Zhen Feng, Qilong Cent South Univ Sch Comp Sci & Engn Changsha 410000 Peoples R China Hunan Univ Technol & Business Sch Frontier Crossover Studies Changsha 410000 Peoples R China

Balanced clustering is a frequently encountered problem in applications requiring balanced class distributions, which generalizes the standard clustering problem in that the number of clients connected to each facility is constrained by the given lower and upper bounds. It was known that both the problems of balanced k-means and k-median are W[2]-hard if parameterized by k, implying that the existences of FPT(k )-time exact algorithms for these problems are unlikely. In this paper, we give FPT(k)-time (9 + is an element of )-approximation and (3 + is an element of )-approximation algorithms for balanced k-means and k-median respectively, improving upon the previous best approximation ratios of 86.9 + is an element of and 7.2 + is an element of obtained in the same time. Our main technical contribution and the crucial step in getting the improved ratios is a different random sampling method for selecting opened facilities.

关键词： approximation algorithm Parameterized algorithm Clustering

来源：评论

学校读者我要写书评

暂无评论

Combinatorial approximation algorithms for the maximum bounded connected bipartition problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-21页

作者： Liu, Xiaofei Li, Yajie Li, Weidong Yang, Jinhua Yunnan Univ Sch Informat Sci & Engn Kunming 650504 Peoples R China Yunnan Univ Sch Math & Stat Kunming 650504 Peoples R China Yunnan Ctr Appl Math Kunming 650504 Peoples R China Dianchi Coll Kunming 650228 Peoples R China

In this paper, we study the maximum bounded connected bipartition problem: given a vertex-weighted connected graph G = (V, E;w) and an upper bound B, the vertex set V is partitioned into two subsets (V-1, V-2) such that the total weight of the two subgraphs induced by V1 and V2 is maximized, and these subgraphs are connected, where the weight of a subgraph is the minimum of B and the total weight of all vertices in the subgraph. In this paper, we prove that this problem is N P-hard even when G is a completed graph, a grid graph with only 3 rows or an interval graph, and we present an 8/7-approximation algorithm. In particular, we present a 14/13-approximation algorithm for the case of grid graphs, and we present a fully polynomial-time approximation scheme for the case of interval graphs.

关键词： Connected bipartition problem Grid graph Interval graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

GEOMETRIC DUALITY RESULTS AND approximation algorithmS FOR CONVEX VECTOR OPTIMIZATION PROBLEMS\ast

引用

SIAM JOURNAL ON OPTIMIZATION 2023年第1期33卷 116-146页

作者： Ararat, Cagin Tekgul, Imay Ulus, Firdevs Bilkent Univ Dept Ind Engn TR-06800 Ankara Turkiye Univ Edinburgh Sch Math Edinburgh EH9 3FD Scotland

We study geometric duality for convex vector optimization problems. For a primal problem with a q-dimensional objective space, we formulate a dual problem with a (q+1)-dimensional objective space. Consequently, different from an existing approach, the geometric dual problem does not depend on a fixed direction parameter, and the resulting dual image is a convex cone. We prove a one-to-one correspondence between certain faces of the primal and dual images. In addition, we show that a polyhedral approximation for one image gives rise to a polyhedral approximation for the other. Based on this, we propose a geometric dual algorithm which solves the primal and dual problems simultaneously and is free of direction-biasedness. We also modify an existing direction-free primal algorithm in such a way that it solves the dual problem as well. We test the performance of the algorithms for randomly generated problem instances by using the so-called primal error and hypervolume indicator as performance measures.

关键词： convex vector optimization multiobjective optimization approximation algorithm scalarization geometric duality hypervolume indicator

来源：评论

学校读者我要写书评

暂无评论

Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints*,**

引用

THEORETICAL COMPUTER SCIENCE 2023年 941卷 167-179页

作者： Zhang, An Zhang, Liang Chen, Yong Chen, Guangting Wang, Xing Hangzhou Dianzi Univ Dept Math Hangzhou 310018 Peoples R China Zhejiang Univ Water Resources & Elect Power Hangzhou 310018 Peoples R China

We investigate two parallel dedicated machine scheduling with conflict constraints. The problem of minimizing the makespan has been shown to be NP-hard in the strong sense under the assumption that the processing sequence of jobs on one machine is given and fixed a priori. The problem without any fixed sequence was previously recognized as weakly NP-hard. In this paper, we first present a 95-approximation algorithm for the problem with a fixed sequence. Then we show that the tight approximation ratios of the algorithm are 74 and 35 for two subproblems which remain strongly NP-hard. We also root send an improved algorithm with approximation ratio 3 - 2 approximate to 1.586 for one subproblem. Finally, we prove that the problem without any fixed sequence is actually strongly NP-hard, and design a 35-approximation algorithm. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Parallel dedicated machines Conflict graph approximation algorithm NP-hard

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：