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

Efficient polynomial-time approximation scheme for the genus of dense graphs

JOURNAL OF THE ACM 2024年第6期71卷 1-33页

作者： Jing, Yifan Mohar, Bojan Univ Oxford Math Inst Oxford England Simon Fraser Univ Dept Math Burnaby BC Canada

The main results of this paper provide an Efficient Polynomial-Time approximation Scheme (EPTAS) for approximating the genus (and non-orientable genus) of dense graphs. By dense we mean that |E(G)|>=alpha|V(G)|(2 )for some fixed alpha > 0. While a constant-factor approximation is trivial for this class of graphs, approximations with factor arbitrarily close to 1 need a sophisticated algorithm and complicated mathematical justification. More precisely, we provide an algorithm that for a given (dense) graph G of order n and given epsilon > 0, returns an integer g such that G has an embedding in a surface of genus g, and this is epsilon-close to a minimum genus embedding in the sense that the minimum genus g(G) of G satisfies: g(G) <= g <= (1+epsilon)g(G). The running time of the algorithm is O(f(epsilon)n(2)), where f(& sdot;) is an explicit function. Next, we extend this algorithm to also output an embedding (rotation system) whose genus is g. This second algorithm is an Efficient Polynomial-time Randomized approximation Scheme (EPRAS) and runs in time O(f(1)(epsilon)n(2)). Our algorithms are based on the analysis of minimum genus embeddings of quasirandom graphs. We use a general notion of quasirandom graphs [25]. We start with a regular partition obtained via an algorithmic version of the Szemer & eacute;di Regularity Lemma (due to Frieze and Kannan [17] and to Fox, Lov & aacute;sz, and Zhao [14, 15]). We then partition the input graph into a bounded number of quasirandom subgraphs, which are preselected in such a way that they admit embeddings using as many triangles and quadrangles as faces as possible. Here we provide an epsilon-approximation nu(G) for the maximum number of edge-disjoint triangles in G. The value nu(G) can be computed by solving a linear program whose size is bounded by certain value f2(epsilon) depending only on epsilon. After solving the linear program, the genus can be approximated (see Corollary 1.7). The proof of this result is long and wil

关键词： Genus of a graph graph embedding regularity lemma approximation algorithm PTAS

来源：评论

学校读者我要写书评

暂无评论

An Improved approximation algorithm for the Capacitated TSP with Pickup and Delivery on a Tree

引用

NETWORKS 2014年第2期63卷 179-195页

作者： Xu, Zhou Lai, Xiaofan Lim, Andrew Wang, Fan Hong Kong Polytech Univ Fac Business Dept Logist & Maritime Studies Hong Kong Hong Kong Peoples R China City Univ Hong Kong Dept Management Sci Hong Kong Hong Kong Peoples R China Sun Yat Sen Univ Sun Yat Sen Business Sch Guangzhou 510275 Guangdong Peoples R China

In this research, we study the capacitated traveling salesman problem with pickup and delivery (CTSPPD) on a tree, which aims to determine the best route for a vehicle with a finite capacity to transport amounts of a product from pickup points to delivery points on a tree network, such that the vehicle's total travel distance is kept to a minimum. It has several applications in logistics and is known to be NP-hard. We develop a 2-approximation algorithm that is a significant improvement over the best constant approximation ratio of 5 derived from existing CTSPPD literature. Computational results show that the proposed algorithm also achieves good average performance over randomly generated instances. (c) 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 63(2), 179-195 2014

关键词： approximation algorithm pickup and delivery traveling salesman problem tree

来源：评论

学校读者我要写书评

暂无评论

A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2014年第3期27卷 609-620页

作者： Li, Yu Du, Donglei Xiu, Naihua Xu, Dachuan Beijing Jiaotong Univ Sch Sci Dept Math Beijing 100044 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada Beijing Univ Technol Dept Appl Math Beijing 100124 Peoples R China

In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.

关键词： approximation algorithm Facility location problem Linear programming Submodular function

来源：评论

学校读者我要写书评

暂无评论

A 2-approximation algorithm for the vertex cover P₄ problem in cubic graphs

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2014年第10期91卷 2103-2108页

作者： Li, Yuchao Tu, Jianhua Beijing Univ Chem Technol Sch Sci Beijing 100029 Peoples R China

A subset F of vertices of a graph G is called a vertex cover P-k set if every path of order k in G contains at least one vertex from F. Denote by psi(k)(G) the minimum cardinality of a vertex cover P-k set in G. The vertex cover P-k (VCPk) problem is to find a minimum vertex cover P-k set. It is easy to see that the VCP2 problem corresponds to the well-known vertex cover problem. In this paper, we restrict our attention to the VCP4 problem in cubic graphs. The paper proves that the VCP4 problem is NP-hard for cubic graphs. Further, we give sharp lower and upper bounds on psi(4)(G) for cubic graphs and propose a 2-approximation algorithm for the VCP4 problem in cubic graphs.

关键词： 05C85 05C70 combinatorial optimization cubic graph approximation algorithm sharp lower and upper bounds vertex cover P-4 problem

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for maximum weight k-coverings of graphs by packings

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2022年第1期14卷

作者： Gavril, Fanica Shalom, Mordechai Zaks, Shmuel Technion Comp Sci Dept Haifa Israel TelHai Acad Coll Upper Galilee Israel ORT Braude Acad Coll Engn Karmiel Israel

Let GA be a family of graphs and let J be a set of connected graphs, each with at most r vertices, r fixed. A J-packing of a graph GA is a vertex induced subgraph of GA with every connected component isomorphic to a member of J. A maximum weight k-covering of a graph GA by J-packings, is a maximum weight subgraph of GA exactly covered by k vertex disjoint J-packings. For a graph GA is an element of GA let J(GA) be a graph, every vertex v of which corresponds to a vertex subgraph a(v) of GA isomorphic to a member of J, two vertices u,v of J(GA) being adjacent if and only if a(u) and a(v) have common vertices or interconnecting edges. The closed neighborhoods containment graph CNCG(GA) of a graph GA(V,D) is an element of GA, is the graph with vertex set V and edges directed from vertices u to v if and only if they are adjacent in GA and the closed neighborhood of u is contained in the closed neighborhood of v. A graph G(V,E) is a GA - H reduced graph if it can be obtained from a graph GA(V,D) is an element of GA by deleting the edges of a transitive subgraph H of CNCG(GA). We describe 1.582-approximation algorithms for maximum weight k-coverings by J-packings of GA and GA - H reduced graphs when GA is vertex hereditary, has an algorithm for maximum weight independent set and J(GA) subset of GA. These algorithms can be applied to families of interval filament, subtree filament, weakly chordal, AT-free and circle graphs, to find 1.582 approximate maximum weight k-coverings by vertex disjoint induced matchings, dissociation sets, forests whose subtrees have at most r vertices, etc.

关键词： approximation algorithm maximum weight k-covering packing GA - H reduced graphs interval filament graphs

来源：评论

学校读者我要写书评

暂无评论

SUBLINEAR TIME approximation OF THE COST OF A METRIC k-NEAREST NEIGHBOR GRAPH

引用

SIAM JOURNAL ON COMPUTING 2024年第2期53卷 524-571页

作者： Czumaj, Artur Sohler, Christian Univ Warwick Dept Comp Sci Coventry CV4 7AL England Univ Warwick Ctr Discrete Math & its Applicat DIMAP Coventry CV4 7AL England Univ Cologne Dept Math & Comp Sci D-50923 Cologne Germany

Let (X, d) be an n -point metric space. We assume that (X, d) is given in the distance oracle model, that is, X = {1, ... , n} and for every pair of points x, y from X we can query their distance d(x, y) in constant time. A k -nearest neighbor (k -NN) graph for (X, d) is a directed graph G = (V, E) that has an edge to each of v's k nearest neighbors. We use cost(G) to denote the sum of edge weights of G. In this paper, we study the problem of approximating cost(G) in sublinear time when we are given oracle access to the metric space (X, d) that defines G. Our goal is to develop an algorithm that solves this problem faster than the time required to compute G. We first present an algorithm that in Owidetilde\\varepsilon(n2/k) time with probability at least 23 approximates cost(G) to within a factor of 1 + \varepsilon. Next, we present a more elaborate sublinear algorithm that in time Owidetilde \ \varepsilon(min{nk3/2,n2/k}) computes an estimate

关键词： sublinear algorithms approximation algorithm nearest neighbors

来源：评论

学校读者我要写书评

暂无评论

A constant factor approximation algorithm for boxicity of circular arc graphs

引用

DISCRETE APPLIED MATHEMATICS 2014年 178卷 1-18页

作者： Adiga, Abhijin Babu, Jasine Chandran, L. Sunil Virginia Tech Virginia Bioinformat Inst Network Dynam & Simulat Sci Lab Blacksburg VA 24061 USA Indian Inst Sci Dept Comp Sci & Automat Bangalore 560012 Karnataka India

The boxicity (resp. cubicity) of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (resp. cubes) in R-k. Equivalently, it is the minimum number of interval graphs (resp. unit interval graphs) on the vertex set V, such that the intersection of their edge sets is E. The problem of computing boxicity (resp. cubicity) is known to be inapproximable, even for restricted graph classes like bipartite, co-bipartite and split graphs, within an O(n(1-epsilon))-factor for any epsilon > 0 in polynomial time, unless NP = ZPP. For any well known graph class of unbounded boxicity, there is no known approximation algorithm that gives n(1-epsilon)-factor approximation algorithm for computing boxicity in polynomial time, for any epsilon > 0. In this paper, we consider the problem of approximating the boxicity (cubicity) of circular arc graphs intersection graphs of arcs of a circle. Circular arc graphs are known to have unbounded boxicity, which could be as large as Omega(n). We give a (2 + 1/k) -factor (resp. (2 + [log n]/k)-factor) polynomial time approximation algorithm for computing the boxicity (resp. cubicity) of any circular arc graph, where k >= 1 is the value of the optimum solution. For normal circular arc (NCA) graphs, with an NCA model given, this can be improved to an additive two approximation algorithm. The time complexity of the algorithms to approximately compute the boxicity (resp. cubicity) is O(mn + n(2)) in both these cases, and in O(mn + kn(2)) = O(n(3)) time we also get their corresponding box (resp. cube) representations, where n is the number of vertices of the graph and m is its number of edges. Our additive two approximation algorithm directly works for any proper circular arc graph, since their NCA models can be computed in polynomial time. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Boxicity Cubicity Circular arc graphs approximation algorithm Normal circular arc graphs

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for Constructing Degree-Dependent Node-Weighted Multicast Trees

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2014年第8期25卷 1976-1985页

作者： Lin, Hwa-Chun Yang, Hsiu-Ming Natl Tsing Hua Univ Dept Comp Sci Hsinchu 30043 Taiwan Natl Tsing Hua Univ Inst Commun Engn Hsinchu 30043 Taiwan

This paper studies the problem of constructing a minimum-cost multicast tree (or Steiner tree) in which each node is associated with a cost that is dependent on its degree in the multicast tree. The cost of a node may depend on its degree in the multicast tree due to a number of reasons. For example, a node may need to perform various processing for sending messages to each of its neighbors in the multicast tree. Thus, the overhead for processing the messages increases as the number of neighbors increases. This paper devises a novel technique to deal with the degree-dependent node costs and applies the technique to develop an approximation algorithm for the degree-dependent node-weighted Steiner tree problem. The bound on the cost of the tree constructed by the proposed approximation algorithm is derived to be (2 ln k/2 + 1) (W-T* + B), where k is the size of the set of multicast members, W-T* is the cost of a minimum-cost Steiner tree T*, and B is related to the degree-dependent node costs. Simulations are carried out to study the performance of the proposed algorithm. A distributed implementation of the proposed algorithm is presented. In addition, the proposed algorithm is generalized to solve the degree-dependent node-weighted constrained forest problem.

关键词： Multicast tree Steiner tree degree-dependent node costs approximation algorithm constrained forest

来源：评论

学校读者我要写书评

暂无评论

2-approximation for Prize-Collecting Steiner Forest

引用

JOURNAL OF THE ACM 2025年第2期72卷

作者： Ahmadi, Ali Gholami, Iman Hajiaghayi, Mohammadtaghi Jabbarzade, Peyman Mahdavi, Mohammad Univ Maryland Comp Sci College Pk MD 20740 USA

approximation algorithms for the prize-collecting Steiner forest (PCSF) problem have been a subject of research for more than three decades, starting with the seminal works of Agrawal et al. and Goemans and Williamson on Steiner forest and prize-collecting problems. In this article, we propose and analyze a natural deterministic algorithm for PCSF that achieves a 2-approximate solution in polynomial time. This represents a significant improvement compared to the previously best known algorithm with a 2.54-approximation factor developed by Hajiaghayi and Jain in 2006. Furthermore, K & ouml;nemann et al. have established an integrality gap of at least 9/4 for the natural LP relaxation for PCSF. However, we surpass this gap through the utilization of an iterative algorithm and a novel analysis technique. Since 2 is the best known approximation guarantee for the Steiner forest problem, which is a special case of PCSF, our result matches this factor and closes the gap between the Steiner forest problem and its generalized version, PCSF.

关键词： Steiner forest prize-collecting approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A new approximation algorithm for the Selective Single-Sink Buy-at-Bulk problem in network design

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2014年第4期27卷 663-678页

作者： Zhang, Peng Shandong Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

The Selective Single-Sink Buy-at-Bulk problem was proposed by Awerbuch and Azar (FOCS 1997). For a long time, the only known non-trivial approach to approximate this problem is the tree-embedding method initiated by Bartal (FOCS 1996). In this paper, we give a thoroughly different approximation approach for the problem with approximation ratio , where q is the number of source terminals in the problem instance. Our approach is based on a mixed strategy of LP-rounding and the greedy method. When the number q (which is always at most n) is relatively small (say, q=o(log(2) n)), our approximation ratio is better than the currently known best ratio O(logn), where n is the number of vertices in the input graph.

关键词： Buy-at-Bulk Network design approximation algorithm Linear programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：