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

A randomized approximation algorithm for metric triangle packing

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第1期41卷 12-27页

作者： Chen, Yong Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng 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 City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is maximized. Although the problem has been extensively studied in the literature, it is surprising that prior to this work, no nontrivial approximation algorithm had been designed and analyzed for its metric case, where the edge weights in the input graph satisfy the triangle inequality. In this paper, we design the first nontrivial polynomial-time approximation algorithm for the maximum-weight metric triangle packing problem. Our algorithm is randomized and achieves an expected approximation ratio of 0.66768 - epsilon for any constant epsilon > 0.

关键词： Triangle packing Metric approximation algorithm Randomized algorithm Maximum cycle cover

来源：评论

学校读者我要写书评

暂无评论

Deterministic approximation algorithm for submodular maximization subject to a matroid constraint

引用

INTERNATIONAL JOURNAL OF CARDIOLOGY 2021年 343卷 1-15页

作者： Sun, Xin Xu, Dachuan Guo, Longkun Li, Min Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Qilu Univ Technol Shandong Comp Sci Ctr Sch Comp Sci & Technol Shandong Key Lab Comp NetworksShandong Acad Sci Jinan 250353 Peoples R China Fuzhou Univ Sch Comp & Data Sci Fuzhou 350116 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

In this paper, we study the generalized submodular maximization problem with a nonnegative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter alpha is an element of [0, 1] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for alpha = 1. For general value of the curvature parameter alpha is an element of [0, 1], we present an approximation algorithm with a factor of 1+h(alpha)(y)+Delta.[3+alpha-(2+alpha)y-(1+alpha)h(alpha)(y)]/2+alpha+(1+alpha)(1-y), where y is an element of [0, 1] is a predefined parameter for tuning the ratio. In particular, when alpha = 1 we obtain a ratio 0.5008 when setting y = 0.9, coinciding with the renowned state-of-art approximate ratio; when alpha = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions. (C) 2021 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Submodular maximization Total curvature Matroid constraint Deterministic algorithm ADAPTIVE COMPLEXITY SET OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

AN approximation algorithm FOR FULLY PLANAR EDGE-DISJOINT PATHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第2期35卷 752-769页

作者： Huang, Chien-Chung Mari, Mathieu Mathieu, Claire Schewior, Kevin Vygen, Jens Univ PSL Ecole Normale Super CNRS F-75005 Paris France Univ PSL Comp Sci Dept Ecole Normale Super F-75005 Paris France Univ Paris CNRS IRIF F-75205 Paris France Univ Cologne Dept Math Informat D-50931 Cologne Germany Univ Bonn Hausdorff Ctr Math Res Inst Discrete Math D-53113 Bonn Germany

We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if the supply graph together with the demand edges forms a planar graph. By planar duality, this is equivalent to packing cuts in a planar graph such that each cut contains exactly one demand edge. We also show that the natural linear programming relaxations have constant integrality gap, yielding an approximate max-multiflow min-multicut theorem.

关键词： approximation algorithm edge-disjoint paths planar graphs

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for Sharing-Aware Virtual Machine Revenue Maximization

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2021年第1期14卷 1-15页

作者： Rampersaud, Safraz Grosu, Daniel Wayne State Univ Dept Comp Sci 5057 Woodward Ave Detroit MI 48202 USA

Cloud providers face the challenge of efficiently managing their infrastructure through minimizing resource consumption while allocating service requests such that their revenue is maximized. Solutions addressing this challenge should consider the sharing of memory pages among virtual machines (VMs) and the available capacity of each type of requested resources. We provide such solution by designing a greedy approximation algorithm for solving the sharing-aware virtual machine revenue maximization (SAVMRM) problem. The SAVMRM problem requires determining the set of VMs that can be instantiated on a given server such that the revenue derived from hosting the VMs is maximized. In addition, we model the SAVMRM problem as a multilinear binary program and optimally solve it, while accounting for page sharing and multiple resource constraints. We determine and analyze the approximability properties of our proposed greedy algorithm and evaluate it by performing extensive experiments using Google cluster workload traces. The experimental results show that under various scenarios, our proposed algorithm generates higher revenue than other VM allocation algorithms while achieving significant reduction of allocated memory.

关键词： approximation algorithm multilinear programming multidimensional knapsack sharing-aware virtual machine

来源：评论

学校读者我要写书评

暂无评论

Cutting path optimization for an automatic cutter in polynomial time using a 3/2 approximation algorithm

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2021年第11-12期113卷 3667-3679页

作者： Eapen, Neeta A. Heckendorn, Robert B. Natl Inst Technol Calicut Calicut Kerala India Univ Idaho Moscow ID 83843 USA

The optimal path to be followed by an automatic cutter to cut a set of shapes arranged on a material is termed as the cutting path determination problem. The shapes are often considered as polygons. Each polygon can be either cut entirely (complete cutting approach) or partially (partial cutting approach) before cutting the next polygon. This work solves the cutting path determination problem using the partial cutting approach. The proposed approximation algorithm uses the concepts of ma tching, s panning tree, and tri angulation, and is hence termed as MASTRI. The MASTRI algorithm has a time complexity of O(n logn) where n is the total number of vertices of all the polygons. The cutting path computed by the MASTRI algorithm is guaranteed to be within a factor of 3/2 of optimum travel distance of the cutter. No other algorithm has been developed for the partial cutting approach which runs in polynomial time. The MASTRI algorithm is evaluated on 285 input problems, of which 192 problems are randomly generated, and 93 problems are taken from literature. The experimental analysis shows that the MASTRI algorithm computes the cutting path in a very short amount of time. The comparison of MASTRI algorithm with existing works in the literature shows that the MASTRI algorithm gives a shorter cutting path in less time. The MASTRI algorithm can be used for computing cutting path in industries like sheet metal cutting.

关键词： Cutting path optimization Endpoint cutting problem approximation algorithm Minimum spanning tree Delaunay triangulation Perfect matching

来源：评论

学校读者我要写书评

暂无评论

Minimizing the Installation Cost of Ground Stations in Satellite Networks: Complexity, Dynamic Programming and approximation algorithm

引用

IEEE WIRELESS COMMUNICATIONS LETTERS 2021年第2期10卷 378-382页

作者： Efrem, Christos N. Panagopoulos, Athanasios D. Natl Tech Univ Athens Sch Elect & Comp Engn Athens 15780 Greece

In this letter, we study the optimum selection of ground stations (GSs) in RF/optical satellite networks (SatNets) in order to minimize the overall installation cost under an outage probability requirement, assuming independent weather conditions between sites. First, we show that the optimization problem can be formulated as a binary-linear-programming problem, and then we give a formal proof of its NP-hardness. Furthermore, we design a dynamic-programming algorithm of pseudo-polynomial complexity with global optimization guarantee as well as an efficient (polynomial-time) approximation algorithm with provable performance guarantee on the distance of the achieved objective value from the global optimum. Finally, the performance of the proposed algorithms is verified through numerical simulations.

关键词： Optimization Heuristic algorithms Probability Power system reliability approximation algorithms Optical attenuators Complexity theory RF optical satellite networks site diversity outage probability ground station selection computational complexity NP-hardness combinatorial optimization dynamic programming approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for k-Depot Split Delivery Vehicle Routing Problem

引用

INFORMS JOURNAL ON COMPUTING 2023年第5期35卷 1179-1194页

作者： Lai, Xiaofan Xu, Liang Xu, Zhou Du, Yang Shenzhen Univ Inst Big Data Intelligent Management & Decis Coll Management Shenzhen 518055 Peoples R China Southwestern Univ Finance & Econ Sch Business Adm Chengdu 611130 Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Hong Kong Peoples R China

A multidepot capacitated vehicle routing problem aims to serve customers' demands using a fleet of capacitated vehicles located in multiple depots, such that the total travel cost of the vehicles is minimized. We study a variant of this problem, the k-depot split delivery vehicle routing problem (or k-DSDVRP in short), for the situation where each customer's demand can be served by more than one vehicle, and the total number of depots, denoted by k >= 2, is a fixed constant. This is a challenging problem with broad applications in the logistics industry, for which no constant ratio approximation algorithm is known. We develop a new approximation algorithm for the k-DSDVRP, ensuring an approximation ratio of (6 4/k) and a polynomial running time for any fixed constant k >= 2. To achieve this, we propose a novel solution framework based on a new relaxation of the problem, a cycle splitting procedure, and a vehicle assignment procedure. To further enhance its efficiency for practical usage, we adapt the newly developed approximation algorithm to a heuristic, which runs in polynomial time even when k is arbitrarily large. Experimental results show that this heuristic outperforms a commercial optimization solver and a standard vehicle routing heuristic. Moreover, our newly proposed solution framework can be applied to developing new constant ratio approximation algorithms for several other variants of the k-DSDVRP with k >= 2 a fixed constant.

关键词： approximation algorithm multiple depot vehicle routing problem split delivery

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for lower-bounded k-median with constant factor

引用

Science China(Information Sciences) 2022年第4期65卷 93-101页

作者： Xiaoliang WU Feng SHI Yutian GUO Zhen ZHANG Junyu HUANG Jianxin WANG School of Computer Science and Engineering Central South University Hunan Provincial Key Lab on Bioinformatics Central South University School of Frontier Crossover Studies Hunan University of Technology and Business

The lower-bounded k-median problem plays a key role in many applications related to privacy protection, which requires that the amount of assigned client to each facility should not be less than the requirement. Unfortunately, the lower-bounded clustering problem remains elusive under the widely studied k-median objective. Within this paper, we convert this problem to the capacitated facility location problem and successfully give a(516+ε)-approximation for this problem.

关键词： approximation algorithm k-median lower-bounded k-median

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for the Offloading Problem in Edge Computing 15th

Approximation Algorithm for the Offloading Problem in Edge C...

引用

15th International Conference on Wireless algorithms, Systems, and Applications (WASA)

作者： Han, Xinxin Gao, Guichen Ning, Li Wang, Yang Zhang, Yong Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen Peoples R China Univ Chinese Acad Sci Beijing Peoples R China

ISBN: (纸本)9783030590161;9783030590154

In the edge-cloud environment, offloading technique decides the task to be executed either at the cloud or at the edge. Offloading can improve the quality of service and the efficiency of the system. In most previous works on the offloading problem, the communication costs between tasks on both cloud side or the edge side are often ignored. We consider a general offloading model where the communication costs between any two tasks is non-zero and asymmetric. Moreover, due to the resource limitation on the edge side, we assume that the number of tasks executed on the edge side is bounded by a fixed constant k. This generalized offloading problem is NP-hard in minimizing the total cost with cardinality constraint. Based on semidefinite program, we give an approximation algorithm with the performance guarantee of 2/pi.

关键词： Offloading Edge computing approximation algorithm Semidefinite program

来源：评论

学校读者我要写书评

暂无评论

A Tight approximation algorithm for the Cluster Vertex Deletion Problem 22nd

A Tight Approximation Algorithm for the Cluster Vertex Delet...

引用

22nd International Conference on Integer Programming and Combinatorial Optimization (IPCO)

作者： Aprile, Manuel Drescher, Matthew Fiorini, Samuel Huynh, Tony Univ Padua Dipartimento Matemat Padua Italy Univ Libre Bruxelles Dept Math Brussels Belgium Monash Univ Sch Math Melbourne Vic Australia

ISBN: (纸本)9783030738792;9783030738785

We give the first 2-approximation algorithm for the cluster vertex deletion problem. This is tight, since approximating the problem within any constant factor smaller than 2 is UGC-hard. Our algorithm combines the previous approaches, based on the local ratio technique and the management of true twins, with a novel construction of a "good" cost function on the vertices at distance at most 2 from any vertex of the input graph. As an additional contribution, we also study cluster vertex deletion from the polyhedral perspective, where we prove almost matching upper and lower bounds on how well linear programming relaxations can approximate the problem.

关键词： approximation algorithm Cluster vertex deletion Linear programming relaxation Sherali-Adams hierarchy

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：