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

approximation algorithms for 1-Wasserstein distance between persistence diagrams

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2025年 129卷

作者： Chen, Samantha Wang, Yusu Univ Calif San Diego La Jolla CA 92093 USA

Recent years have witnessed a tremendous growth using topological summaries, especially the persistence diagrams (encoding the so-called persistent homology) for analyzing complex shapes. Intuitively, persistent homology maps a potentially complex input object (be it a graph, an image, or a point set and so on) to a unified type of feature summary, called the persistence diagrams. One can then carry out downstream data analysis tasks using such persistence diagram representations. A key problem is to compute the distance between two persistence diagrams efficiently. In particular, a persistence diagram is essentially a multiset of points in the plane, and one popular distance is the so-called 1-Wasserstein distance between persistence diagrams. In this paper, we present two algorithms to approximate the 1-Wasserstein distance for persistence diagrams in nearlinear time. These algorithms primarily follow the same ideas as two existing algorithms to approximate optimal transport between two finite point-sets in Euclidean spaces via randomly shifted quadtrees. We show how these algorithms can be effectively adapted for the case of persistence diagrams. Our algorithms are much more efficient than previous exact and approximate algorithms, both in theory and in practice, and we demonstrate its efficiency via extensive experiments. They are conceptually simple and easy to implement, and the code is publicly available in github. (c) 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Spersistence diagrams approximation algorithms Wasserstein distance Optimal transport

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the airport and railway problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第1期49卷 1-33页

作者： Salavatipour, Mohammad R. Tian, Lijiangnan Univ Alberta Dept Comp Sci Edmonton AB Canada

In this paper, we present approximation algorithms for theAirport and Railwayproblem (AR) on several classes of graphs. The AR problem, introduced as reported byAdamaszek et al. (in: Ollinger, Vollmer (eds) 33rd symposium on theoretical aspectsof computer science (STACS 2016). Leibniz international proceedings in informatics(LIPIcs), Dagstuhl, 2016), is a combination of theCapacitated Facility Loca-tionproblem (CFL) and theNetwork Design Problem(NDP). An AR instanceconsists of a set of points (cities)Vin a metricd(., .), each of which is associatedwith a non-negative costfvand a numberk, which represent respectively the cost ofestablishing an airport (facility) in the corresponding point, and the universal airportcapacity. A feasible solution is a network of airports and railways providing servicesto all cities without violating any capacity, where railways are edges connecting pairsof points, with their costs equivalent to the distance between the respective *** objective is to find such a network with the least cost. In other words, find aforest, each component having at mostkpoints and one open facility, minimizing thetotal cost of edges and airport opening costs. As reported by Adamaszek et al. (in:Ollinger, Vollmer (eds) 33rd symposium on theoretical aspects of computer science(STACS 2016). Leibniz international proceedings in informatics (LIPIcs), Dagstuhl,2016) presented a PTAS for AR in the two-dimensional Euclidean metricR2witha uniform opening cost. In subsequent work (as reported by Adamaszek et al. (in:Niedermeier, Vall & eacute;e (eds) 35th symposium on theoretical aspects of computer science(STACS 2018). Leibniz international proceedings in informatics (LIPIcs), Dagstuhl,2018).) presented a bicriteria43(2+1 alpha)-approximation algorithm for AR with non-uniform opening costs but violating the airport capacity by a factor of 1 + alpha, i.e.(1+alpha)k capacity where 0 < alpha <= 1, a(2 + k/k-1 + epsilon)-approximation algorithm and a bicrite-ria Q

关键词： Facility location approximation algorithms Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for cycle and path partitions in complete graphs

引用

THEORETICAL COMPUTER SCIENCE 2025年 1029卷

作者： Zhao, Jingyang Xiao, Mingyu Univ Elect Sci & Technol China Sch Comp Sci & Engn 2006 Xiyuan Ave Chengdu 610054 Sichuan Peoples R China

Given an edge-weighted (metric/general) complete graph with n vertices, where n mod k = 0, maximum weight (metric/general) k-cycle/path partition problem is to find a set of nk vertex disjoint k-cycles/paths such that the total weight is maximized. In this paper, we consider approximation algorithms. For metric k-cycle partition, we improve the previous approximation ratio from 35 to 710 for k = 5, and from 78 (1- 1 /k ) (2) for k >5 to ( 7 /8 - 1/8k )(1 -1/k) for constant odd k> 5and to 78 (1- 1/k + k(k-1) )for even k> 5. For metric k-path partition, we improve approximation ratio from 7 8 (1 - 1k )to 27k(2)-48k+16 /32k(2)-36k-24 for k is an element of {6, 8,10}. For the case of k = 4, we improve the approximation ratio from 43 to 56 for metric 4-cycle partition, from 2/3 to 3/4 for general 4-cycle partition, and from 3 /4 to 14 /17 for metric 4-path partition.

关键词： approximation algorithms Cycle partition Path partition

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for solving the heterogeneous rooted tree/path cover problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第3期49卷 1-19页

作者： Pan, Pengxiang Lichen, Junran Yang, Ping Li, Jianping Yunnan Univ Sch Math & Stat East Outer Ring South Rd Kunming 650504 Peoples R China Beijing Univ Chem Technol Sch Math & Phys 15 North Third Ring East Rd Beijing 100029 Peoples R China

In this paper, we consider the heterogeneous rooted tree cover (HRTC) problem, which further generalizes the rooted tree cover problem. Specifically, given a complete graph G = (V, E;w, f;r) and k construction teams, having nonuniform construction speeds lambda(1), lambda(2), ... , lambda(k), where r is an element of V is a fixed common root, w : E -> R+ is an edge-weight function, satisfying the triangle inequality, and f: V -> R-0(+) (i.e., R+ boolean OR approximation) is a vertex-weight function with f (r) = 0, we are asked to find k trees for these k construction teams, each tree having the same root r, and collectively covering all vertices in V, the objective is to minimize the maximum completion time of k construction teams, where the completion time of each team is the total construction weight of its related tree divided by its construction speed. In addition, substituting k paths for k trees in the HRTC problem, we also consider the heterogeneous rooted path cover (HRPC) problem. Our main contributions are as follows. (1) Given any small constant delta > 0, we first design a 58.3286(1 + delta)-approximation algorithm to solve the HRTC problem, and this algorithm runs in time O(n(2)(n + log n/delta) +log(w (E) + f (V))). Meanwhile, we present a simple 116.6572(1 + delta)-approximation algorithm to solve the HRPC problem, whose time complexity is the same as the preceding algorithm. (2) We provide a max{2 rho, 2 + rho - 2/k}-approximation algorithm to resolve the HRTC problem, and that algorithm runs in time O(n(2)), where rho is the ratio of the largest team speed to the smallest one. At the same time, we can prove that the preceding max{2 rho, 2 + rho - 2/k}-approximation algorithm also resolves the HRPC problem.

关键词： Rooted tree/path cover Nonuniform speeds approximation algorithms Complexity of algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for flexible graph connectivity

引用

MATHEMATICAL PROGRAMMING 2024年第1-2期204卷 493-516页

作者： Boyd, Sylvia Cheriyan, Joseph Haddadan, Arash Ibrahimpur, Sharat Univ Ottawa Sch Elect Engn & Comp Sci Ottawa ON Canada Univ Waterloo Dept Combinator & Optimizat Waterloo ON Canada Amazon Inc Modeling & Optimizat Bellevue WA USA London Sch Econ & Polit Sci Dept Math London England

We present approximation algorithms for several network design problems in the model of flexible graph connectivity (Adjiashvili et al., in: IPCO, pp 13-26, 2020, Math Program 1-33, 2021). Let k >== 1, p >= 1 and q >= 0 be integers. In an instance of the ( p, q)-Flexible Graph Connectivity problem, denoted ( p, q)-FGC, we have an undirected connected graph G = (V, E), a partition of E into a set of safe edges l and a set of unsafe edges U, and nonnegative costs c : E -> R(>=)0 on the edges. A subset F subset of. E of edges is feasible for the ( p, q)-FGC problem if for any set F 'subset of. U with | F '| <= q, the subgraph (V, F\ F ') is p-edge connected. The algorithmic goal is to find a feasible solution F that minimizes c( F) = Sigma F-e is an element of(ce.) We present a simple 2-approximation algorithm for the (1, 1)-FGC problem via a reduction to the minimum-cost rooted 2-arborescence problem. This improves on the 2.527-approximation algorithm of Adjiashvili et al. Our 2-approximation algorithm for the (1, 1)-FGC problem extends to a (k + 1)-approximation algorithm for the (1, k)-FGC problem. We present a 4-approximation algorithm for the (k, 1)-FGC problem, and an O(q log | V|)-approximation algorithm for the ( p, q)-FGC problem. Finally, we improve on the result of Adjiashvili et al. for the unweighted (1, 1)-FGC problem by presenting a 16/11-approximation algorithm. The ( p, q)-FGC problem is related to the well-known Capacitated k-Connected Subgraph problem (denoted Cap-k-ECSS) that arises in the area of Capacitated Network Design. We give a min(k, 2u(max))-approximation algorithm for the Cap-k-ECSS problem, where u(max) denotes the maximum capacity of an edge.

关键词： approximation algorithms Combinatorial optimization Network design Edge-connectivity of graphs Reliability of networks

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem

引用

Journal of the Operations Research Society of China 2024年第3期12卷 729-755页

作者： Jian-Ping Li Su-Ding Liu Jun-Ran Lichen Peng-Xiang Pan Wen-Cheng Wang Department of Mathematics Yunnan UniversityKunming650504YunnanChina School of Mathematics and Physics Beijing University of Chemical TechnologyBeijing650504China

We address the 1-line minimum Steiner tree of line segments(1L-MStT-LS)***,given a set S of n disjoint line segments in R^(2),we are asked to find the location of a line l and a set E_(l) of necessary line segments(i.e.,edges)such that a graph consisting of all line segments in S ∪ E_(l) plus this line l,denoted by T_(l)=(S,l,E_(l)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(l) among all such Steiner ***,we are asked to find a set E_(0) of necessary edges such that a graph consisting of all line segments in S ∪ E_(0),denoted by T_(S)=(S,E_(0)),becomes a Steiner tree,the objective is to minimize total length of edges in E_(0) among all such Steiner trees,we refer to this new problem as the minimum Steiner tree of line segments(MStT-LS)*** addition,when two endpoints of each edge in Eo need to be located on two different line segments in S,respectively,we refer to that problem as the minimum spanning tree of line segments(MST-LS)*** obtain three main results:(1)Using technique of Voronoi diagram of line segments,we design an exact algorithm in time O(n log n)to solve the MST-LS problem;(2)we show that the algorithm designed in(1)is a 1.214-approximation algorithm to solve the MStT-LS problem;(3)using the combination of the algorithm designed in(1)as a subroutine for many times,a technique of finding linear facility location and a key lemma proved by techniques of computational geometry,we present a 1.214-approximation algorithm in time O(n^(3) log n)to solve the 1L-MStT-LS problem.

关键词： 1-Line minimum Steiner tree of line segments Minimum spanning tree of line segments Voronoi diagram of line segments Steiner ratio approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for solving the vertex-traversing-constrained mixed Chinese postman problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2024年第4期90卷 965-982页

作者： Pan, Pengxiang Lichen, Junran Li, Jianping Yunnan Univ Sch Math & Stat East Outer Ring South Rd Kunming 650504 Peoples R China Beijing Univ Chem Technol Sch Math & Phys North Third Ring East Rd Beijing 100029 Peoples R China

In this paper, we address the vertex-traversing-constrained mixed Chinese postman problem (the VtcMCP problem), which is a further generalization of the Chinese postman problem, and this new problem has many practical applications in real life. Specifically, given a connected mixed graph G=(V,E boolean OR A;w,b)\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\cup A;w,b)$$\end{document} with length function w()\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$w(\cdot )$$\end{document} on edges and arcs and traversal function b()\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$b(\cdot )$$\end{document} on vertices, we are asked to determine a tour traversing each link (i.e., either edge or arc) at least once and each vertex v at most b(v) times, the objective is to minimize the total length of such a tour, where n=|V|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n=|V|$$\end{document} is the number of vertices and m=|E boolean OR A|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$m=|E\cup A|$$\end{document} is the number of links of G, respectively

关键词： Combinatorial optimization Mixed graphs Vertex traversal times Chinese postman routing approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Two-Watchman Route in a Simple Polygon

引用

ALGORITHMICA 2024年第9期86卷 2845-2884页

作者： Nilsson, Bengt J. Packer, Eli Malmo Univ S-20506 Malmo Sweden Yoom Ramat Gan Israel

The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the two tours is minimized. Two standard measures are: the minmax measure, where we want the tours where the longest of them has smallest length, and the minsum measure, where we want the tours for which the sum of their lengths is the smallest. It is known that computing a minmax two-watchman route is NP-hard for simple rectilinear polygons and thus also for simple polygons. Also, any c-approximation algorithm for the minmax two-watchman route is automatically a 2c-approximation algorithm for the minsum two-watchman route. We exhibit two constant factor approximation algorithms for computing minmax two-watchman routes in simple polygons with approximation factors 5.969 and 11.939, having running times O ( n 8 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>8)$$\end{document} and O ( n 4 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>4)$$\end{document} respectively, where n is the number of vertices of the polygon. We also use the same techniques to obtain a 6.922-approximation for the fixed two-watchman route problem running in O ( n 2 ) \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>2)$$\end{document} time, i.e., when two starting points of the two tours are given as input.

关键词： Art gallery problems Visibility Watchman routes approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for solving the trip-constrained vehicle routing cover problems

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第3期48卷 1-24页

作者： Li, Jianping Yang, Ping Lichen, Junran Pan, Pengxiang Yunnan Univ Univ Town Sch Math & Stat East Outer Ring South Rd Kunming 650504 Peoples R China Beijing Univ Chem Technol Sch Math & Phys North Third Ring East Rd Beijing 100029 Peoples R China

In this paper, we address the trip-constrained vehicle routing cover problem (theTcVRC problem). Specifically, given a metric complete graphG=(V,E;w)with a set D(subset of V)of depots, a setJ(=V\D)of customer locations, each customerhaving unsplittable demand 1, andkvehicles with capacityQ, it is asked to find a setC={C-i|=1,2,...,k}ofktours forkvehicles to service all customers, each tourfor a vehicle starts and ends at one depot inDand permits to be replenished at someother depots inDbefore continuously servicing at mostQcustomers, i.e., the numberof customers continuously serviced in per trip of each tour is at mostQ(except thetwo end-vertices of that trip), where each trip is a path or cycle, starting at a depot andending at other depot (maybe the same depot) inD, such that there are no other depotsin the interior of that path or cycle, the objective is to minimize the maximum weightof suchktours inC, i.e., minCmax{w(C-i)|i=1,2,...,k}, wherew(Ci)is thetotal weight of edges in that tourCi. Consideringkvehicles whether to have commondepot or suppliers, we consider three variations of the TcVRC problem, i.e., (1) the trip-constrained vehicle routing cover problem with multiple suppliers (the TcVRC-MSproblem) is asked to find a setC={Ci|i=1,2,...,k}ofktours mentioned-above,the objective is to minimize the maximum weight of suchktours inC;(2) the trip-constrained vehicle routing cover problem with common depot and multiple suppliers(the TcVRC-CDMS problem) is asked to find a setC={Ci|i=1,2,...,k}ofk tours mentioned-above, where each tour starts and ends at same depotvinD, eachvehicle having its suppliers at some depots inD(possibly includingv), the objectiveis to minimize the maximum weight of suchktours inC;(3) the trip-constrainedk-traveling salesman problem with non-suppliers (the TckTS-NS problem, simply theTckTSP-NS) is asked to find a setC={C-i=1,2,...,k}of k tours mentioned-above, where each tour starts and ends at same depotvinD, each vehicle havingnon-suppli

关键词： Combinatorial optimization Trip-constrained vehicle routing covers Min-max tour covers Trip-constrained k-traveling salesman tours approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for node and element connectivity augmentation problems

引用

THEORY OF COMPUTING SYSTEMS 2024年第5期68卷 1468-1485页

作者： Nutov, Zeev Open Univ Israel Raanana Israel

In connectivity augmentation problems we are given a graph G=(V,EG)\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_G)$$\end{document} and an edge set E on V, and seek a min-size edge set J 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}$$J \subseteq E$$\end{document} such that G boolean OR J\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G \cup J$$\end{document} has larger connectivity than G. In the 1-Connectivity Augmentation (1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}-CA) problem G is connected and G boolean OR J\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G \cup J$$\end{document} should be 2-connected. In the Leaf to Leaf1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1$$\end{document}-CA every edge in E connects two leaves in the block-tree of G. For this version we give a simple combinatorial 5/3-approximation algorithm, improving the 1.892 appr

关键词： Connectivity augmentation Crossing family approximation algorithms Element connectivity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：