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

OPTIMAL COVERING TOURS WITH TURN COSTS

SIAM JOURNAL ON COMPUTING 2005年第3期35卷 531-566页

作者： Arkin, Esther M. Bender, Michael A. Demaine, Erik D. Fekete, Sandor P. Mitchell, Joseph S. B. Sethia, Saurabh SUNY Stony Brook Dept Appl Math & Stat Stony Brook NY 11794 USA SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Braunschweig Univ Technol Dept Math Optimizat D-38106 Braunschweig Germany SoftJin Infotech Pvt Ltd Bangalore Karnataka India

We give the first algorithmic study of a class of "covering tour" problems related to the geometric traveling salesman problem: Find a polygonal tour for a cutter so that it sweeps out a specified region ("pocket") in order to minimize a cost that depends mainly on the number of turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing ("postman") problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the m-guillotine method.

关键词： NC machining manufacturing traveling salesman problem milling lawn mowing covering approximation algorithms polynomial-time approximation scheme m-guillotine subdivisions NP-completeness turn costs

来源：评论

学校读者我要写书评

暂无评论

A PTAS for the metric case of the optimum weighted source-destination communication spanning tree problem

引用

THEORETICAL COMPUTER SCIENCE 2019年 771卷 9-22页

作者： Ravelo, Santiago Valdes Ferreira, Carlos Eduardo Fed Univ Rio Grande Ctr Comp Sci Rio Grande RS Brazil Univ Sao Paulo Inst Math & Stat Sao Paulo Brazil

This work considers the optimum weighted source-destination communication spanning tree problem (WSDOCT), which is an NP-hard special case of the optimum communication spanning tree problem (OCT). Given an undirected graph G = (V, E) with non-negative lengths omega(e) associated to the edges and non-negative routing weights sigma(u) and rho(u) respectively to sending and receiving communication of nodes u is an element of V, the objective is to find a spanning tree T of G, that minimizes: Sigma(u, nu is an element of V) (sigma(u)rho(v) + rho(u)sigma(v))d(T, u, v), where d(H, x, y) is the minimum distance between nodes x and y in a graph H subset of G. We present a polynomial time approximation scheme for the metric case of the WSDOCT. This result improves the until now best existing approximation algorithm for this problem. Also, we give a 2-approximation for the problem which improves the time complexity required by our PTAS to achieve this approximation ratio. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Optimum communication spanning tree problem approximation algorithms polynomial-time approximation scheme Metric problem

来源：评论

学校读者我要写书评

暂无评论

Two-machine flow shop with dynamic storage space

引用

OPTIMIZATION LETTERS 2021年第7期15卷 2433-2454页

作者： Berlinska, Joanna Kononov, Alexander Zinder, Yakov Adam Mickiewicz Univ Fac Math & Comp Sci Poznan Poland Sobolev Inst Math Novosibirsk Russia Novosibirsk State Univ Novosibirsk Russia Univ Technol Sydney Sch Math & Phys Sci Sydney NSW Australia

The publications on two-machine flow shop scheduling problems with job dependent storage requirements, where a job seizes a portion of the storage space for the entire duration of its processing, were motivated by various applications ranging from supply chains of mineral resources to multimedia systems. In contrast to the previous publications that assumed that the availability of the storage space remains unchanged, this paper is concerned with a more general case when the availability is a function of time. It strengthens the previously published result concerning the existence of an optimal permutation schedule, shows that the variable storage space availability leads to the NP-hardness in the strong sense even for unit processing times, and presents a polynomial-time approximation scheme together with several heuristic algorithms. The heuristics are evaluated by means of computational experiments.

关键词： Two-machine flow shop Makespan Dynamic storage Computational complexity polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

On the closest string and substring problems

引用

JOURNAL OF THE ACM 2002年第2期49卷 157-171页

作者： Li, M Ma, B Wang, LS Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA Univ Western Ontario Dept Comp Sci London ON N6A 5B7 Canada City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

The problem of finding a center string that is "close" to every given string arises in computational molecular biology and coding theory. This problem has two versions: the Closest String problem and the Closest Substring problem. Given a set of strings S = {s(1), s(2),..., s(n)}, each of length m, the Closest String problem is to find the smallest d and a string s of length m which is within Hamming distance d to each s(i) is an element of S. This problem comes from coding theory when we are looking for a code not too far away from a given set of codes. Closest Substring problem, with an additional input integer L, asks for the smallest d and a string s, of length L, which is within Hamming distance d away from a substring, of length L, of each s(i). This problem is much more elusive than the Closest String problem. The Closest Substring problem is formulated from applications in finding conserved regions, identifying genetic drug targets and generating genetic probes in molecular biology. Whether there are efficient approximation algorithms for both problems are major open questions in this area. We present two polynomial-time approximation algorithms with approximation ratio 1 + epsilon for any small epsilon to settle both questions.

关键词： algorithms theory closest string and substring computer applications polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

How fast can we reach a target vertex in stochastic temporal graphs?

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2020年 114卷 65-83页

作者： Akrida, Eleni C. Mertzios, George B. Nikoletseas, Sotiris Raptopoulos, Christoforos Spirakis, Paul G. Zamaraev, Viktor Univ Liverpool Dept Comp Sci Liverpool Merseyside England Univ Durham Dept Comp Sci Durham England Univ Patras Comp Engn & Informat Dept Patras Greece CTI Patras Greece

Temporal graphs abstractly model real-life inherently dynamic networks. Given a graph G, a temporal graph with Gas the underlying graph is a sequence of subgraphs (snapshots) G(t) of G, where t >= 1. In this paper we study stochastic temporal graphs, i.e. stochastic processes Gwhose random variables are the snapshots of a temporal graph on G. Anatural feature observed in various real-life scenarios is a memory effect in the appearance probabilities of particular edges;i.e. the probability an edge e is an element of E appears at time step tdepends on its appearance (or absence) at the previous ksteps. We study the hierarchy of models of memory-k, k >= 0, in an edge-centric network evolution setting: every edge of Ghas its own independent probability distribution for its appearance over time. We thoroughly investigate the complexity of two naturally related, but fundamentally different, temporal path problems, called MINIMUM ARRIVAL and BEST POLICY. (c) 2020 Elsevier Inc. All rights reserved.

关键词： Temporal network Stochastic temporal graph Temporal path #P-hard problem polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A PTAS for a class of binary non-linear programs with low-rank functions

引用

OPERATIONS RESEARCH LETTERS 2021年第5期49卷 633-638页

作者： Trung Thanh Nguyen Elbassioni, Khaled Phenikaa Univ Fac Comp Sci ORLab Hanoi 12116 Vietnam Khalifa Univ Sci & Technol Abu Dhabi U Arab Emirates

Binary non-linear programs belong to the class of combinatorial problems which are computationally hard even to approximate. This paper aims to explore some conditions on the problem structure, under which the resulting problem can be well approximated. Particularly, we consider a setting when both objective function and constraint are low-rank functions, which depend only on a few linear combinations of the input variables, and provide polynomial time approximation schemes. Our result generalizes and unifies some existing results in the literature. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Binary non-linear program Convex program Low-rank function polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Simple PTAS's for families of graphs excluding a minor

引用

DISCRETE APPLIED MATHEMATICS 2015年 189卷 41-48页

作者： Cabello, Sergio Gajser, David IMFM Dept Math Ljubljana Slovenia Univ Ljubljana FMF Dept Math Ljubljana 61000 Slovenia

We show that very simple algorithms based on local search are polynomial-time approximation schemes for MAXIMUM INDEPENDENT SET, MINIMUM VERTEX COVER and MINIMUM DOMINATING SET, when the input graphs have a fixed forb... 详细信息

关键词： polynomial-time approximation scheme Forbidden minor Separator Local optimization Maximum independent set Minimum vertex cover Minimum dominating set

来源：评论

学校读者我要写书评

暂无评论

New Algorithms for Steiner Tree Reoptimization

引用

ALGORITHMICA 2024年第8期86卷 2652-2675页

作者： Bilo, Davide Univ Laquila Dept Informat Engn Comp Sci & Math Via Vetoio 0 Coppito I-67100 Laquila AQ Italy

Reoptimization is a setting in which we are given a good approximate solution of an optimization problem instance and a local modification that slightly changes the instance. The main goal is that of finding a good approximate solution of the modified instance. We investigate one of the most studied scenarios in reoptimization known as Steiner tree reoptimization. Steiner tree reoptimization is a collection of strongly NP \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {NP}$$\end{document} -hard optimization problems that are defined on top of the classical Steiner tree problem and for which several constant-factor approximation algorithms have been designed in the last decades. In this paper we improve upon all these results by developing a novel technique that allows us to design polynomial-time approximation schemes. Remarkably, prior to this paper, no approximation algorithm better than recomputing a solution from scratch was known for the elusive scenario in which the cost of a single edge decreases. Our results are best possible since none of the problems addressed in this paper admits a fully polynomial-time approximation scheme, unless P = NP \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textsf {P}=\textsf {NP}$$\end{document}

关键词： Reoptimization Steiner tree approximation algorithms polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Partitioned EDF scheduling on a few types of unrelated multiprocessors

引用

REAL-time SYSTEMS 2013年第2期49卷 219-238页

作者： Wiese, Andreas Bonifaci, Vincenzo Baruah, Sanjoy Univ Roma La Sapienza Dipartimento Ingn Informat Automat & Gest Rome Italy CNR Ist Anal Sistemi & Informat Rome Italy Univ N Carolina Chapel Hill NC 27515 USA

A polynomial-time approximation scheme (PTAS) is derived for the partitioned EDF scheduling of implicit-deadline sporadic task systems upon unrelated multiprocessor platforms that are comprised of a constant number of distinct types of processors. This generalizes earlier results showing the existence of polynomial-time approximation schemes for the partitioned EDF scheduling of implicit-deadline sporadic task systems on (1) identical multiprocessor platforms, and (2) unrelated multiprocessor platforms containing a constant number of processors.

关键词： Multiprocessor scheduling Unrelated multiprocessors polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A PTAS for capacitated sum-of-ratios optimization

引用

OPERATIONS RESEARCH LETTERS 2009年第4期37卷 230-238页

作者： Rusmevichientong, Paat Shen, Zuo-Jun Max Shmoys, David B. Cornell Univ Sch Operat Res & Informat Engn Ithaca NY 14853 USA UC Berkeley Berkeley CA USA

Motivated by an application in assortment planning under the nested logit choice model, we develop a polynomial-time approximation scheme for the sum-of-ratios optimization problem with a capacity constraint and a fix... 详细信息

关键词： Sum-of-ratios polynomial-time approximation scheme Assortment planning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：