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

Faster Exact Computation of rSPR Distance via Better approximation

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2020年第3期17卷 916-929页

作者： Chen, Zhi-Zhong Harada, Youta Nakamura, Yuna Wang, Lusheng Tokyo Denki Univ Div Informat Syst Design Hatoyama Saitama 3500394 Japan City Univ Hong Kong Dept Comp Sci Kowloon Tat Chee Ave Hong Kong Peoples R China

Due to hybridization events in evolution, studying two different genes of a set of species may yield two related but different phylogenetic trees for the set of species. In this case, we want to measure the dissimilarity of the two trees. The rooted subtree prune and regraft (rSPR) distance of the two trees has been used for this purpose. The problem of computing the rSPR distance of two given trees has many applications but is NP-hard. Accordingly, a number of programs have been developed for solving the problem either exactly or approximately. In this paper, we develop two new programs, one of which solves the problem exactly and outperforms the previous best (namely, Whidden et al.'s rSPR-v1.3.0) significantly, while the other solves the problem approximately and outputs significantly better lower and upper bounds on the rSPR distance of the two given trees than the previous best due to Schalekamp et al. Our programs can be downloaded at http://***/***.

关键词： Phylogeny approximation algorithms Forestry Vegetation Upper bound Java Software Phylogenetic tree rSPR distance approximation algorithm fixed-parameter algorithm

来源：评论

学校读者我要写书评

暂无评论

algorithmic results in Roman dominating functions on graphs

引用

INFORMATION PROCESSING LETTERS 2023年 182卷

作者： Poureidi, Abolfazl Fathali, Jafar Shahrood Univ Technol Fac Math Sci Shahrood Iran

Given a graph G = (V, E), a subset D subset of V (respectively, function f : V -> {0, 1, 2}) is a dominating set (DS) (respectively, Roman dominating function (RDF)) of G if each vertex v is an element of V\D (respectively, v is an element of V with f (v) = 0) is adjacent to a vertex u is an element of D (respectively, u is an element of V with f (u) = 2). The domination number of G is the minimum cardinality of an DS of G and the Roman domination number of G is the minimum weight of an RDF f of G, where the weight of f is Ev is an element of V f (v). The (Roman) domination problem is to compute the (Roman) domination number of a given graph. In this paper, we study the Roman domination problem. We show that the complexity of the problem differs from the complexity of the domination problem and the problem is NP-complete for circle graphs and undirected path graphs and is APX-complete for graphs of degree at most 4. We also propose an integer linear programming (ILP) formulation with polynomial number of constraints for the problem. Additionally, we use the ILP formulation to give an H(Delta(G) + 1)-approximation algorithm for solving the problem for any graph G, where Delta(G) is the maximum degree of G. Furthermore, we show that the optimization version of the problem on split and chordal graphs cannot be approximated in polynomial time within (1/2 - epsilon) ln | V | for any epsilon > 0, unless NP subset of DTIME (| V |O (log log | V |)).(c) 2023 Elsevier B.V. All rights reserved.

关键词： Roman dominating function approximation algorithm Integer linear program NP-complete APX-complete

来源：评论

学校读者我要写书评

暂无评论

Optimizing incremental SDN upgrades for load balancing in ISP networks

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期962卷

作者： Cheng, Yunlong Zhou, Hao Gao, Xiaofeng Zheng, Jiaqi Chen, Guihai Shanghai Jiao Tong Univ Dept Comp Sci & Engn MoE Key Lab Artificial Intelligence Shanghai 200240 Peoples R China Meituan Beijing 100102 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China

Software defined network (SDN) can dynamically and timely reply to the changes of network states, thus enabling advance traffic engineering mechanisms. To enhance the management ability of the network, Internet Service Providers (ISPs) are upgrading traditional network devices to SDN devices incrementally. In this paper, we study the k-LB problem, i.e., upgrading at most k legacy switches to SDN switches to achieve load balance. We prove that k-LB problem is NP-hard and there is no polynomial time (N + M)(1-epsilon) - approximation algorithm for any constant epsilon > 0 unless P = NP, where N(M) is the number of switches (links) in the network. Nevertheless, we propose an effective greedy algorithm and prove that it reaches an approximation guarantee of c(avg)/c(min) M, where c(avg)(c(min)) is the average (minimum) link capacity. Furthermore, we show that the greedy algorithm touches the tight lower bound of approximation ratio by extending the inapproximability result. The simulation results from large-scale ISP network topologies illustrate the effectiveness of our algorithm and show that the maximum link utilization can be decreased by 30% on average compared with the SOTA. (c) 2023 Elsevier B.V. All rights reserved.

关键词： SDN Incremental deployment Load balance approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Off-site protection against service function forwarder failures in NFV

引用

COMPUTER NETWORKS 2023年第1期221卷

作者： Peng, Chengzong Zheng, Danyang Zhong, Yihan Cao, Xiaojun Chengdu Univ Informat Technol Sch Cybersecur Chengdu 610225 Peoples R China Soochow Univ Suzhou Key Lab Adv Opt Commun Network Technol Sch Elect & Informat Engn Suzhou 215006 Peoples R China Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA

Many internet applications in the emerging 5G/6G networks require ultra-reliable and low-latency communi-cations (URLLC) services. To deliver URLLC services flexibly and efficiently, network function virtualization (NFV) is employed to enable network slicing. NFV deploys service function chains (SFCs) consisting of service functions (SFs) and service function forwarders (SFFs) to deliver services. It is possible for SFFs in an SFC to fail when forwarding traffic to specified SF instances. Protecting SFF failures in NFV is challenging since multiple SF instances may fail simultaneously as a result of a single SFF failure. This work investigates how to protect the SF instances against the SFF failures while minimizing the cost of backup computing resources. We formulate a new problem called SFF-driven multi-instance failures and protection (SMFP), and prove its NP-hardness. We propose an efficient heuristic algorithm, namely, SFF-centralized resource optimization (FCRO), which is based on the proposed techniques of backup auxiliary transferring, backup cost-effectiveness selection, and adaptive fit backup. Our experimental results demonstrate that the proposed FCRO is effective and significantly outperforms the schemes directly extended from the existing work.

关键词： Network function virtualization Network reliability Service function forwarder approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Resource Allocation under the Latin Square Constraint 25

Resource Allocation under the Latin Square Constraint

引用

Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems

作者： Yasushi Kawase Bodhayan Roy Mohammad Azharuddin Sanpui The University of Tokyo Tokyo Japan Indian Institute of Technology Kharagpur Kharagpur India

ISBN: (纸本)9798400714269

A Latin square is an n×n matrix filled with n distinct symbols, each appearing exactly once in each row and column. We introduce a problem of allocating n indivisible items among n agents over n rounds while satisfying the Latin square constraint. This constraint ensures that each agent receives no more than one item per round and receives each item at most once. Each agent has an additive valuation on the item--round pairs. Real-world applications like scheduling, resource management, and experimental design require the Latin square constraint to satisfy fairness or balancedness in allocation. Our goal is to find a partial or complete allocation that maximizes the sum of the agents' valuations (utilitarian social welfare) or the minimum of the agents' valuations (egalitarian social welfare). For maximizing utilitarian social welfare, we prove NP-hardness even when the valuations are binary additive. We then provide (1-1/e) and (1-1/e)/4-approximation algorithms for partial and complete settings, respectively. Additionally, we present fixed-parameter tractable (FPT) algorithms with respect to the order of Latin square and the optimum value for both partial and complete settings. For maximizing egalitarian social welfare, we establish that deciding whether the optimum value is at most 1 or at least 2 is NP-hard for both the partial and complete settings, even when the valuations are binary. Furthermore, we prove that checking the existence of a complete allocation satisfying each of envy-free, proportional, equitable, envy-free up to any good, proportional up to any good, or equitable up to any good is NP-hard, even when the valuations are identical.

关键词： approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Permanent Dominating Set Problem on Dynamic Networks 14th

Approximation Algorithms for Permanent Dominating Set Proble...

引用

14th International Conference on Distributed Computing and Internet Technology (ICDCIT)

作者： Mandal, Subhrangsu Gupta, Arobinda Indian Inst Technol Kharagpur Dept Comp Sci & Engn Kharagpur W Bengal India

ISBN: (纸本)9783319723440;9783319723433

A temporal graph is a graph whose node and/or edge set changes with time. Many dynamic networks in practice can be modeled as temporal graphs with different properties. Finding different types of dominating sets in such graphs is an important problem for efficient routing, broadcasting, or information dissemination in the network. In this paper, we address the problems of finding the minimum permanent dominating set and maximum k-dominant node set in temporal graphs modeled as evolving graphs. The problems are first shown to be NP-hard. A ln(n tau)-approximation algorithm is then presented for finding a minimum permanent dominating set, where n is the number of nodes, and tau is the lifetime of the given temporal graph. Detailed simulation results on some real life data sets representing different networks are also presented to evaluate the performance of the proposed algorithm. Finally, a (1-1/e)-approximation algorithm is presented for finding a maximum k-dominant node set.

关键词： Permanent dominating set Maximum k-dominant node set approximation algorithm Temporal graph

来源：评论

学校读者我要写书评

暂无评论

Research on Supply Chain Distribution Network of Bi-Level Programming Model based on Two-way approximation Genetic algorithm 13th

Research on Supply Chain Distribution Network of Bi-Level Pr...

引用

13th Wuhan International Conference on E-Business

作者： Lin, Liping Zhang, Xiaoqing Yuan, Xigang Zhou, Haijun Guangxi Univ Sci & Technol Sch Management Liuzhou 545006 Peoples R China

ISBN: (纸本)9780980051070

This study introduces the opportunity cost of distribution network. The centralized and distributed supply chain distribution network of bi-level programming model were constructed by defining the distribution centers face different stock losses, which include one manufacturer, more distribution centers and multiple retailers. Combined with the traditional genetic algorithm, this study designed approximation algorithm in order to optimize and solve the model, and verify the effectiveness of the model and algorithm through an example

关键词： stock losses distribution network supply chain approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The approximation ratio of the 2-Opt Heuristic for the metric Traveling Salesman Problem

引用

OPERATIONS RESEARCH LETTERS 2020年第4期48卷 401-404页

作者： Hougardy, Stefan Zaiser, Fabian Zhong, Xianghui Univ Bonn Res Inst Discrete Math Lennestr 2 D-53113 Bonn Germany

The 2-Opt heuristic is one of the simplest algorithms for finding good solutions to the metric Traveling Salesman Problem. It is the key ingredient to the well-known Lin-Kernighan algorithm and often used in practice. So far, only upper and lower bounds on the approximation ratio of the 2-Opt heuristic for the metric TSP were known. We prove that for the metric TSP with n cities, the approximation ratio of the 2-Opt heuristic is root n/2 and that this bound is tight. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Traveling Salesman Problem Metric TSP 2-opt approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the Stochastic Fault-Tolerant Facility Location Problem

引用

Journal of the Operations Research Society of China 2013年第4期1卷 511-522页

作者： Chenchen Wu Dachuan Xu Jia Shu School of Mathematical Sciences Nankai UniversityTianjing 300071P.R.China Department of Applied Mathematics Beijing University of Technology100 PingleyuanChaoyang DistrictBeijing 100124P.R.China Department of Management Science and Engineering School of Economics and ManagementSoutheast UniversityNanjing 211189P.R.China

In this paper,we study a stochastic version of the fault-tolerant facility location *** exploiting the stochastic structure,we propose a 5-approximation algorithm which uses the LP-rounding technique based on the revised optimal solution to the linear programming relaxation of the stochastic fault-tolerant facility location problem.

关键词： Facility location problem approximation algorithm LP rounding

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the Risk-Adjusted Two-Stage Stochastic Facility Location Problem with Penalties

引用

Journal of the Operations Research Society of China 2013年第3期1卷 339-346页

作者： Jiating Shao Dachuan Xu Department of Applied Mathematics Beijing University of Technology100 PingleyuanChaoyang DistrictBeijing 100124P.R.China

In this paper,we consider the risk-adjusted two-stage stochastic facility location problem with penalties(RSFLPP).Using the monotonicity and positive homogeneity of the risk measure function,we present an LP-roundin... 详细信息

关键词： Facility location approximation algorithm LP-rounding Risk-adjusted

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：