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

LP-Rounding Based algorithm for Capacitated Uniform Facility Location Problem with Soft Penalties

Tsinghua Science and Technology 2025年第1期30卷 279-289页

作者： Runjie Miao Chenchen Wu Jinjiang Yuan School of Mathematics and Statistics Zhengzhou UniversityZhengzhou 450001China Institute of Operations Research and Systems Engineering Tianjin University of TechnologyTianjin 300384China

Capacitated facility location problem(CFLP)is a classical combinatorial optimization problem that has various applications in operations research,theoretical computer science,and management *** the CFLP,we have a potential facilities set and a clients *** facility has a certain capacity and an open cost,and each client has a spliitable demand that need to be *** goal is to open some facilities and assign all clients to these open facilities so that the total cost is as low as *** CFLP is NP-hard(non-deterministic polynomial-hard),and a large amount of work has been devoted to designing approximation algorithms for CFLP and its *** this vein,we introduce a new variant of CFLP called capacitated uniform facility location problem with soft penalties(CUFLPSP),in which the demand of each client can be partially rejected by paying penalty *** a result,we present a linear programming-rounding(LP-rounding)based 5.5122-approximation algorithm for the CUFLPSP.

关键词： capacitated facility location problem approximation algorithm soft penalties linear program

来源：评论

学校读者我要写书评

暂无评论

An advanced Successive Derivative Shortest Path algorithm for concave cost network flow problems

引用

OPERATIONS RESEARCH PERSPECTIVES 2025年 14卷

作者： Yang, Lu Yang, Zhouwang Univ Sci & Technol China Hefei Peoples R China

As production scales up, transportation networks increasingly involve nonlinear costs, leading to the concave cost network flow problem (CCNFP), which is notably challenging due to its nonlinearity. Existing nonlinear programming methods addressing the CCNFP often suffer from low efficiency and high computational cost, limiting their practical application. To overcome these limitations, this paper proposes the Successive Derivative Shortest Path (SDSP) algorithm, an efficient approach that combines a sequential linear approximation framework with regional first-order information of the objective function. By integrating regional first-order information and employing an interval reduction mechanism, the SDSP algorithm effectively avoids premature convergence to suboptimal solutions, thereby achieving higher-quality solutions. Numerical experiments, including parameter selection, validation, and comparative analysis, demonstrate that the SDSP algorithm outperforms existing methods in terms of both solution quality and convergence speed. This research offers a robust and efficient solution for the CCNFP, with potential applications in various fields, including logistics and supply chain networks, where concave cost network flow issues are common.

关键词： Network flow Non-convex problem approximation algorithm Regional first-order information Interval reduction

来源：评论

学校读者我要写书评

暂无评论

FENDI: Toward High-Fidelity Entanglement Distribution in the Quantum Internet

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2024年第6期32卷 5033-5048页

作者： Gu, Huayue Li, Zhouyu Yu, Ruozhou Wang, Xiaojian Zhou, Fangtong Liu, Jianqing Xue, Guoliang North Carolina State Univ Dept Comp Sci Raleigh NC 27606 USA Arizona State Univ Sch Comp & Augmented Intelligence Tempe AZ 85281 USA

A quantum network distributes quantum entanglements between remote nodes, and is key to many applications in secure communication, quantum sensing and distributed quantum computing. This paper explores the fundamental trade-off between the throughput and the quality of entanglement distribution in a multi-hop quantum repeater network. Compared to existing work which aims to heuristically maximize the entanglement distribution rate (EDR) and/or entanglement fidelity, our goal is to characterize the maximum achievable worst-case fidelity, while satisfying a bound on the maximum achievable expected EDR between an arbitrary pair of quantum nodes. This characterization will provide fundamental bounds on the achievable performance region of a quantum network, which can assist with the design of quantum network topology, protocols and applications. However, the task is highly non-trivial and is NP-hard as we shall prove. Our main contribution is a fully polynomial-time approximation scheme to approximate the achievable worst-case fidelity subject to a strict expected EDR bound, combining an optimal fidelity-agnostic EDR-maximizing formulation and a worst-case isotropic noise model. The EDR and fidelity guarantees can be implemented by a post-selection-and-storage protocol with quantum memories. By developing a discrete-time quantum network simulator, we conduct simulations to show the characterized performance region (the approximate Pareto frontier) of a network, and demonstrate that the designed protocol can achieve the performance region while existing protocols exhibit a substantial gap.

关键词： Quantum network entanglement routing entanglement fidelity network optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

AoI-Aware Service Provisioning in Edge Computing for Digital Twin Network Slicing Requests

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2024年第12期23卷 14607-14621页

作者： Li, Jing Guo, Song Liang, Weifa Wang, Jianping Chen, Quan Hong, Zicong Xu, Zichuan Xu, Wenzheng Xiao, Bin City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Peoples R China Guangdong Univ Technol Sch Comp Guangzhou 510006 Peoples R China Hong Kong Polytech Univ Dept Comp Hong Kong Peoples R China Dalian Univ Technol Sch Software Dalian 116024 Peoples R China Sichuan Univ Coll Comp Sci Chengdu 610065 Peoples R China

Digital twins are poised to enter our lives with Industry 4.0. The Digital Twin Network (DTN) paradigm is projected to deliver upon the promise of efficient collaboration among digital twins to enable complicated and systematic services across many domains, through depicting an overall picture of a group of physical objects. To achieve timely data processing of digital twins, Mobile Edge Computing (MEC) shifts the computational power towards the network edge, and network slicing is well-suited to bundle heterogeneous physical resources to build logical networks based on edge servers for accommodating DTNs. In light of this, in this paper we investigate DTN slicing-enabled service provisioning in MEC, where each DTN slice consists of one master digital twin and a set of worker digital twins, and each worker digital twin is synchronized through collecting data from a respective object periodically. The master digital twin aggregates the processed data from worker digital twins to model the DTN continuously for user query services, whilst meeting delay requirements of users. We capture the utility gain of a DTN slicing request based on the DTN model quality at its master digital twin that is impacted by the Age of Information (AoI), and we focus on two novel optimization problems: the utility maximization problem for a single DTN slicing request, and the dynamic utility maximization problem for multiple DTN slicing requests. We propose an approximation algorithm for the former, and an online algorithm with a provable competitive ratio for the latter. We also evaluate the performance of the proposed algorithms through simulations. Experimental results demonstrate that the proposed algorithms are promising, outperforming their counterparts by at least 10.2%.

关键词： Digital twins Heuristic algorithms approximation algorithms Network slicing Delays Data models Synchronization Digital twin mobile edge computing network slicing request age of information approximation algorithm online algorithm and resource allocation

来源：评论

学校读者我要写书评

暂无评论

approximation and Fixed Parameter algorithms for the Approximate Cover Problem 1

引用

30th International Symposium on String Processing and Information Retrieval (SPIRE) / 18th Workshop on Compression, Text, and algorithms (WCTA)

作者： Blin, Guillaume Popa, Alexandru Raffinot, Mathieu Uricaru, Raluca Univ Bordeaux LaBRI CNRS Bordeaux INPUMR 5800 F-33400 Talence France Univ Bucharest Fac Math & Comp Sci Bucharest Romania

ISBN: (数字)9783031439803

ISBN: (纸本)9783031439797;9783031439803

Amir et al. (CPM 2017) introduce the approximate string cover problem (ACP) motivated by applications including molecular biology, coding, automata theory, formal language theory and combinatorics. A cover of a string T is a string C for which every letter of T lies within some occurrence of C. The input of the ACP consists of a string T and the goal is to find a string C of length less than the length of T that covers a string T ', which is as close to T as possible (under some predefined distance). Amir et al. study this problem for the Hamming distance and show that it is NP-hard. In this paper we continue the work of Amir et al. and show the following results for the cover length relaxation of the ACP. After observing that the NP-hardness proof by Amir et al. (CPM 2017, TCS 2019) suffers from several lapses, we propose an amendment to the proof. We then introduce an approximation algorithm for a variant of the ACP, in which we aim to maximize the length of the input string minus the distance to the string covered by the approximate cover returned by the algorithm. This problem is naturally as hard as the ACP. We prove an asymptotic approximation ratio of O(root|T|), where |T| is the size of the input string. Finally, we present an FPT algorithm with respect to the alphabet size and the size of the cover based on a dynamic programming framework.

关键词： Approximate Cover NP-hardness approximation algorithm FPT algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Vertex Happiness

引用

Journal of the Operations Research Society of China 2019年第3期7卷 429-448页

作者： Yao Xu Yong Chen Peng Zhang Randy Goebel Department of Computing Science University of AlbertaEdmontonAB T6G 2E8Canada Department of Mathematics Hangzhou Dianzi UniversityHangzhou 310018China School of Computer Science and Technology Shandong UniversityJinan 250101China

We investigate the maximum happy vertices(MHV)problem and its complement,the minimum unhappy vertices(MUHV)*** order to design better approximation algorithms,we introduce the supermodular and submodular multi-labeling(SUP-ML and SUB-ML)problems and show that MHV and MUHV are special cases of SUP-ML and SUB-ML,respectively,by rewriting the objective functions as set *** convex relaxation on the I ovasz extension,originally presented for the submodular multi-partitioning problem,can be extended for the SUB-ML problem,thereby proving that SUB-ML(SUP-ML,respectively)can be approximated within a factorof2-2/k(2/k,respectively),where k is the number of *** general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2-2/k,respectively,using the same approximation *** the MUHV problem,we also show that it is approximation-equivalent to the hypergraph multiway cut problem;thus,MUHV is Unique Games-hard to achieve a(2-2/k-e)-approximation,for anyε>*** the MHV problem,the 2/k-approximation improves the previous best approximation ratio max{1/k,1/(△+1/g(△)},where△is the maximum vertex degree of the input graph and g(△)=(√△+√△+1)2△>4△*** also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovasz extension for SUP-ML;we then prove an upper bound of 2/k on the integrality gap of this LP relaxation,which suggests that the 2/k-approximation is the best possible based on this LP ***,we prove that it is Unique Games-hard to approximate the MHV problem within a factor of S2(log2 k/k).

关键词： Vertex happiness Multi-labeling Submodular/supermodular set function approximation algorithm Polynomial-time reduction Integrality gap

来源：评论

学校读者我要写书评

暂无评论

Direct Product Multicommodity Max-Concurrent-Flow Min-Sparse-Cut Theorem

引用

JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA 2024年 1-11页

作者： Guan, Rui Liang, Dong-Yue Wang, Wei Yang, Wei-Hua Nankai Univ Sch Math Sci Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China Taiyuan Univ Technol Dept Math Taiyuan 030024 Shanxi Peoples R China Xi An Jiao Tong Univ Sch Math & Stat Xian 710049 Shaanxi Peoples R China

We extend the max-concurrent-flow min-sparse-cut theorem from product multicommodity to direct product multicommodity. We prove that Theta(logk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Theta (\log k)$$\end{document} is the tight gap between the max-concurrent-flow and the min-sparse-cut for direct product multicommodity, where k is the number of commodities. Besides, when the network we consider is centralized, we prove that there is a 1 alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{1}{\alpha }$$\end{document}-approximation algorithm for the sparsest cut problem, where alpha\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document} is the maximum weight ratio of vertices.

关键词： Multicommodity Flow-cut gap Sparsest cut approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

k-Submodular Maximization with a Knapsack Constraint and p Matroid Constraints

引用

Tsinghua Science and Technology 2023年第5期28卷 896-905页

作者： Qian Liu Kemin Yu Min Li Yang Zhou School of Mathematics and Statistics Shandong Normal UniversityJinan 250014China

A k-submodular function is a generalization of a submodular function,its definition domain is extended from the collection of single subsets to the collection of k disjoint *** k-submodular maximization problem has a wide range of *** this paper,we propose a nested greedy and local search algorithm for the problem of maximizing a monotone k-submodular function subject to a knapsack constraint and p matroid constraints.

关键词： k-submodularity knapsack constraint matroid constraint approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Tight approximation bounds for maximum multi-coverage

引用

MATHEMATICAL PROGRAMMING 2022年第1-2期192卷 443-476页

作者： Barman, Siddharth Fawzi, Omar Ghoshal, Suprovat Gurpinar, Emirhan Indian Inst Sci Bangalore Karnataka India Univ Lyon LIP CNRS UCBLENS LyonInria F-69342 Lyon 07 France

In the classic maximum coverage problem, we are given subsets T-1,..., T-m of a universe [n] along with an integer k and the objective is to find a subset S subset of [m] of size k that maximizes C(S) := vertical bar boolean OR(i is an element of S) T-i vertical bar. It is well-known that the greedy algorithm for this problem achieves an approximation ratio of (1- e(-1)) and there is a matching inapproximability result. We note that in themaximum coverage problem if an element e is an element of [n] is covered by several sets, it is still counted only once. By contrast, if we change the problem and count each element e as many times as it is covered, then we obtain a linear objective function, C-(infinity)(S) = Sigma(i is an element of S) vertical bar T-i vertical bar, which can be easily maximized under a cardinality constraint. We study the maximum l-multi-coverage problem which naturally interpolates between these two extremes. In this problem, an element can be counted up to l times but no more;hence, we consider maximizing the function C-(l)( S) = Sigma(e is an element of[n]) min{l, |{i is an element of S : e is an element of T-i}|}, subject to the constraint vertical bar S vertical bar <= k. Note that the case of l = 1 corresponds to the standard maximum coverage setting and l =infinity gives us a linear objective. We develop an efficient approximation algorithm that achieves an approximation ratio of 1 - l(l)e-l/l(l) for the l-multi-coverage problem. In particular, when l = 2, this factor is 1 - 2e(-2) approximate to 0.73 and as l grows the approximation ratio behaves as 1 - 1/root 2 pi l. We also prove that this approximation ratio is tight, i.e., establish a matching hardness-of-approximation result, under the Unique Games Conjecture. This problem is motivated by the question of finding a code that optimizes the list-decoding success probability for a given noisy channel. We show how the multi-coverage problem can be relevant in other contexts, such as

关键词： approximation algorithm Maximum coverage Randomized rounding Convex order

来源：评论

学校读者我要写书评

暂无评论

Approximating(mB,mP)-Monotone BP Maximization and Extensions

引用

Tsinghua Science and Technology 2023年第5期28卷 906-915页

作者： Ruiqi Yang Suixiang Gao Lu Han Gaidi Li Zhongrui Zhao Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing 100124China School of Mathematical Sciences University of Chinese Academy SciencesBeijing 100049China School of Science Beijing University of Posts and TelecommunicationsBeijing 100876China

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular(BP)functions with partial monotonicity under a streaming *** this model,elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular *** goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as *** this work,a threshold-based streaming algorithm is presented for the BP maximization that attains a(1-k)/(2-k)-O(e)-approximation with O(1/e^(4)1og^(3)(1/s)log(2-k)k/(1-k)^(2))memory complexity,where k denotes the parameter of supermodularity *** further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same *** finally investigate this fair model under the streaming fashion and provide a(1-k)^(4)/(2-2k+k^(2))^(2)-O(e)-approximation algorithm.

关键词： submodular maximization streaming model threshold technique approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：