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

approximation schemes for the Generalized Traveling Salesman Problem

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS 2017年第1-Sup期299卷 97-105页

作者： Khachai, M. Yu. Neznakhina, E. D. Russian Acad Sci Krasovskii Inst Math & Mech Ural Branch Ekaterinburg 620990 Russia Ural Fed Univ Ekaterinburg 620000 Russia Omsk State Tech Univ Omsk 644050 Russia

The Generalized Traveling Salesman Problem (GTSP) is defined by a weighted graph G = (V,E,w) and a partition of its vertex set into k disjoint clusters V = V (1) a... a V (k). It is required to find a minimum-weight cycle that contains exactly one vertex of each cluster. We consider a geometric setting of the problem (we call it the EGTSP-k-GC), in which the vertices of the graph are points in the plane, the weight function corresponds to the Euclidean distances between the points, and the partition into clusters is specified implicitly by means of a regular integer grid with step 1. In this setting, a cluster is a subset of vertices lying in the same cell of the grid;the arising ambiguity is resolved arbitrarily. Even in this special setting, the GTSP remains intractable, generalizing in a natural way the classical planar Euclidean TSP. Recently, a -approximation algorithm with complexity depending polynomially both on the number of vertices n and on the number of clusters k has been constructed for this problem. We propose three approximation schemes for this problem. For each fixed k, all the schemes are polynomial and the complexity of the first two is linear in the number of nodes. Furthermore, the first two schemes remain polynomial for k = O(log n), whereas the third scheme is polynomial for k = n - O(log n).

关键词： generalized traveling salesman problem NP-hard problem polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A PTAS for Min-k-SCCP in Euclidean Space of Arbitrary Fixed Dimension

引用

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS 2016年第1期295卷 S120-S130页

作者： Neznakhina, E. D. Russian Acad Sci Krasovskii Inst Math & Mech Ural Branch Ekaterinburg 620990 Russia Ural Fed Univ Ekaterinburg 620000 Russia

We study the minimum weight k-size cycle cover problem (Min-k-SCCP), which consists in partitioning a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a generalization of the known traveling salesman problem and a special case of the classical vehicle routing problem. It is known that Min-k-SCCP is strongly NP-hard in the general case and preserves its intractability even in the geometric statement. For Euclidean Min-k-SCCP in R-d with k - O(log n), we construct a polynomial-time approximation scheme (PTAS), which generalizes the approach proposed earlier for planar Min-2-SCCP. For each fixed c > 1 the scheme finds a (1 + 1/c)-approximate solution in time O(n(O(d))(log n)(O(root dc))d-1).

关键词： cycle cover of size k traveling salesman problem NP-hard problem polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

COVERING A SET OF POINTS IN MULTIDIMENSIONAL SPACE

引用

INFORMATION PROCESSING LETTERS 1991年第4期40卷 181-188页

作者： GONZALEZ, TF Department of Computer Science Utrecht University Utrecht Netherlands

Let P = {p1, p2,...,p(n)} be a set of points in d-space. We study the problem of covering with the minimum number of fixed-size orthogonal hypersquares (CS(d) for short) all points in P. We present a fast approximation algorithm that generates provably good solutions and an improved polynomial-time approximation scheme for this problem. A variation of the CS(d) problem is the CR(d) problem, covering by fixed-size orthogonal hyperrectangles, where the covering of the points is by hyperrectangles with dimensions D1, D2,...,D(d) instead of hypersquares of size D. Another variation is the CD(d) problem, where we cover the set of points with hyperdiscs of diameter D. Our algorithms can be easily adapted to these problems.

关键词： ANALYSIS OF ALGORITHMS D-SPACE COVERING BY HYPERSQUARES HYPERDISCS AND HYPERRECTANGLES EFFICIENT ALGORITHMS polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation schemes for r-weighted Minimization Knapsack problems

引用

ANNALS OF OPERATIONS RESEARCH 2019年第1-2期279卷 367-386页

作者： Elbassioni, Khaled Karapetyan, Areg Trung Thanh Nguyen Khalifa Univ Sci & Technol Masdar Inst Abu Dhabi U Arab Emirates Hai Phong Univ Haiphong Vietnam

Stimulated by salient applications arising from power systems, this paper studies a class of non-linear Knapsack problems with non-separable quadratic constrains, formulated in either binary or integer form. These problems resemble the duals of the corresponding variants of 2-weighted Knapsack problem (a.k.a., complex-demand Knapsack problem) which has been studied in the extant literature under the paradigm of smart grids. Nevertheless, the employed techniques resulting in a polynomial-time approximation scheme (PTAS) for the 2-weighted Knapsack problem are not amenable to its minimization version. We instead propose a greedy geometry-based approach that arrives at a quasi PTAS (QPTAS) for the minimization variant with boolean variables. As for the integer formulation, a linear programming-based method is developed that obtains a PTAS. In view of the curse of dimensionality, fast greedy heuristic algorithms are presented, additionally to QPTAS. Their performance is corroborated extensively by empirical simulations under diverse settings and scenarios.

关键词： Weighted Minimization Knapsack Quasi polynomial-time approximation scheme polynomial-time approximation scheme Power generation planning Smart grid Economic dispatch control

来源：评论

学校读者我要写书评

暂无评论

PTAS FOR k-TOUR COVER PROBLEM ON THE PLANE FOR MODERATELY LARGE VALUES OF k

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2010年第6期21卷 893-904页

作者： Adamaszek, Anna Czumaj, Artur Lingas, Andrzej Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Its Applicat DIMAP Coventry CV4 7AL W Midlands England Lund Univ Dept Comp Sci S-22100 Lund Sweden

Let P be a set of n points in the Euclidean plane and let O be the origin point in the plane. In the k-tour cover problem (called frequently the capacitated vehicle routing problem), the goal is to minimize the total length of tours that cover all points in P, such that each tour starts and ends in O and covers at most k points from P. The k-tour cover problem is known to be NP-hard. It is also known to admit constant factor approximation algorithms for all values of k and even a polynomial-time approximation scheme (PTAS) for small values of k, k = circle divide (log n/ log log n). In this paper, we significantly enlarge the set of values of k for which a PTAS is provable. We present a new PTAS for all values of k <= 2(log delta n), where delta = delta(epsilon). The main technical result proved in the paper is a novel reduction of the k-tour cover problem with a set of n points to a small set of instances of the problem, each with circle divide((k/epsilon)(circle divide(1))) points.

关键词： approximation algorithms capacitated vehicle routing k-tour cover polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

引用

THEORETICAL COMPUTER SCIENCE 2011年第3期412卷 198-208页

作者： Zou, Feng Wang, Yuexuan Xu, Xiao-Hua Li, Xianyue Du, Hongwei Wan, Pengjun Wu, Weili Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +epsilon)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +epsilon)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +epsilon)-approximation algorithm for an MWCDS. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Minimum-weighted dominating set Minimum-weighted connected dominating set Minimum-weighted chromatic disk cover Node-weighted Steiner tree polynomial-time approximation scheme approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximum Edge Colouring Problem On Graphs That Exclude a Fixed Minor 49th

Maximum Edge Colouring Problem On Graphs That Exclude a Fixe...

引用

49th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Dvorak, Zdenek Lahiri, Abhiruk Charles Univ Prague Prague 11800 Czech Republic Heinrich Heine Univ D-40225 Dusseldorf Germany

ISBN: (纸本)9783031433795;9783031433801

The maximum edge colouring problem considers the maximum colour assignment to edges of a graph under the condition that every vertex has at most a fixed number of distinct coloured edges incident on it. If that fixed number is q we call the colouring a maximum edge q-colouring. The problem models a non-overlapping frequency channel assignment question on wireless networks. The problem has also been studied from a purely combinatorial perspective in the graph theory literature. We study the question when the input graph is sparse. We show the problem remains NP-hard on 1-apex graphs. We also show that there exists PTAS for the problem on minor-free graphs. The PTAS is based on a recently developed Baker game technique for proper minor-closed classes, thus avoiding the need to use any involved structural results. This further pushes the Baker game technique beyond the problems expressible in the first-order logic.

关键词： polynomial-time approximation scheme Edge colouring Minor-free graphs

来源：评论

学校读者我要写书评

暂无评论

Approximating Connectivity Domination in Weighted Bounded-Genus Graphs 16

Approximating Connectivity Domination in Weighted Bounded-Ge...

引用

48th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Cohen-Addad, Vincent de Verdiere, Eric Colin Klein, Philip N. Mathieu, Claire Meierfrankenfeld, David Ecole Normale Super Dept Informat Paris France Ecole Normale Super Dept Informat CNRS Paris France Brown Univ Providence RI 02912 USA

ISBN: (纸本)9781450341325

We present a framework for addressing several problems on weighted planar graphs and graphs of bounded genus. With that framework, we derive polynomial-time approximation schemes for the following problems in planar graphs or graphs of bounded genus: edge-weighted tree cover and tour cover, vertex-weighted connected dominating set, max weight-leaf spanning tree, and connected vertex cover. In addition, we obtain a polynomial-time approximation scheme for feedback vertex set in planar graphs. These are the first polynomial-time approximation schemes for all those problems in weighted embedded graphs. (For unweighted versions of some of these problems, polynomial-time approximation schemes were previously using bidimensionality.)

关键词： approximation algorithm polynomial-time approximation scheme graph bounded genus planar graph connected dominating set feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

Two-Dimensional Knapsack for Circles 13th

Two-Dimensional Knapsack for Circles

引用

13th Latin American Theoretical Informatics Symposium (LATIN)

作者： Lintzmayer, Carla Negri Miyazawa, Flavio Keidi Xavier, Eduardo Candido Fed Univ ABC Ctr Math Comp & Cognit Santo Andre Brazil Univ Estadual Campinas Inst Comp Campinas SP Brazil

ISBN: (纸本)9783319774046;9783319774039

In this paper we consider the Two-dimensional Knapsack for Circles problem, in which we are given a set C of circles and want to pack a subset C' subset of C of them into a rectangular bin of dimensions w and h such that the sum of the area of circles in C' is maximum. By packing we mean that the circles do not overlap and they are fully contained inside the bin. We present a polynomial-time approximation scheme that, for any epsilon > 0, gives an approximation algorithm that packs a subset of the input circles into an augmented bin of dimensions w and (1 + O(epsilon)) h such that the area packed is at least (1 - O(epsilon)) times the area packed by an optimal solution into the regular bin of dimensions w and h. This result also extends to the multiple knapsack version of this problem.

关键词： Circle packing Two-dimensional Knapsack polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Pandora's Problem with Nonobligatory Inspection: Optimal Structure and a PTAS 2023

Pandora's Problem with Nonobligatory Inspection: Optimal Str...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Beyhaghi, Hedyeh Cai, Linda Carnegie Mellon Univ Pittsburgh PA 15213 USA Princeton Univ Princeton NJ USA

ISBN: (纸本)9781450399135

Weitzman (1979) introduced Pandora's box problem as a mathematical model of sequential search with inspection costs, in which a searcher is allowed to select a prize from one of n alternatives. Several decades later, Doval (2018) introduced a close version of the problem, where the searcher does not need to incur the inspection cost of an alternative, and can select it uninspected. Unlike the original problem, the optimal solution to the nonobligatory inspection variant is proved to need adaptivity by Doval (2018), and by recent work of Fu Li and Liu (2022), finding the optimal solution is NP-hard. Our first main result is a structural characterization of the optimal policy: We show there exists an optimal policy that follows only two different pre-determined orders of inspection, and transitions from one to the other at most once. Our second main result is a polynomial time approximation scheme (PTAS). Our proof involves a novel reduction to a framework developed by Fu Li and Xu (2018), utilizing our optimal two-phase structure. Furthermore, we show Pandora's problem with nonobligatory inspection belongs to class NP, which by using the hardness result of Fu Li and Liu (2022), settles the computational complexity class of the problem. Finally, we provide a tight 0.8 approximation and a novel proof for committing policies (informally, the set of nonadaptive policies) for general classes of distributions, which was previously shown only for discrete and finite distributions in Guha, Munagala and Sarka (2008).

关键词： Pandora's box optimal search polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：