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

3rd International Conference on Numerical Computations - Theory and Algorithms (NUMTA)

作者： Khandeev, Vladimir Sobolev Inst Math 4 Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogova St Novosibirsk 630090 Russia

ISBN: (纸本)9783030406165

The paper is addressed to one strongly NP-hard problem of searching for the largest subset in the finite set of points in Euclidean space. A restriction is imposed on the searched subset: quadratic variation of its points with respect to the unknown centroid of this subset must not exceed a given value. We present the first polynomial-time approximation scheme for this problem.

关键词： Euclidean space Largest subset Quadratic variation NP-hard problem polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time approximation scheme for an arbitrary number of parallel two-stage flow-shops

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2020年第1期281卷 16-24页

作者： Dong, Jianming Jin, Ruyan Luo, Taibo Tong, Weitian Zhejiang Sci Tech Univ Dept Math Hangzhou 310018 Zhejiang Peoples R China Xidian Univ Sch Econ & Management Xian 710126 Shaanxi Peoples R China Eastern Michigan Univ Dept Comp Sci Ypsilanti MI 48165 USA

We investigate the approximability of the m parallel two-stage flow-shop (mP2FS) problem, where a set of jobs is scheduled on the multiple identical two-stage flow-shops to minimize the makespan, i.e., the finishing time of the last job. Each job needs to be processed non-preemptively on one flow-shop without switching to the other flow-shops. This problem is a hybrid of the classic parallel machine scheduling and two-stage flow-shop scheduling problems. Its strong NP-hardness follows from the parallel machine scheduling problem when the number of machines is part of the input. Our main contribution is a polynomial-time approximation scheme (PTAS) for the mP2FS problem when the number of shops is part of the input, which improves the previous best approximation algorithm of a ratio (2 + epsilon). Owing to the strong NP-hardness, our PTAS achieves the best possible approximation ratio. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Scheduling Parallel two-stage flow-shops Makespan Mixed integer program polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2016年 51卷 25-39页

作者： Ito, Takehiro Nakano, Shin-ichi Okamoto, Yoshio Otachi, Yota Uehara, Ryuhei Uno, Takeaki Uno, Yushi Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Gunma Univ Dept Comp Sci Kiruyu 3768515 Japan Univ Electrocommun Dept Commun Engn & Informat Chofu Tokyo 1828585 Japan Japan Adv Inst Sci & Technol Sch Informat Sci Nomi Ishikawa 9231292 Japan Natl Inst Informat Principles Informat Res Div Chiyoda Ku Tokyo 1018430 Japan Osaka Prefecture Univ Grad Sch Sci Naka Ku Sakai Osaka 5998531 Japan

We give a polynomial-time approximation scheme for the unique unit-square coverage problem: given a set of points and a set of axis-parallel unit squares, both in the plane, we wish to find a subset of squares that maximizes the number of points contained in exactly one square in the subset. Erlebach and van Leeuwen [9] introduced this problem as the geometric version of the unique coverage problem, and the best approximation ratio by van Leeuwen [21] before our work was 2. Our scheme can be generalized to the budgeted unique unit-square coverage problem, in which each point has a profit, each square has a cost, and we wish to maximize the total profit of the uniquely covered points under the condition that the total cost is at most a given bound. (C) 2015 Elsevier B.V. All rights reserved.

关键词： polynomial-time approximation scheme Unique coverage problem Dynamic programming Shifting strategy

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time approximation scheme for parallel two-stage flowshops under makespan constraint

引用

THEORETICAL COMPUTER SCIENCE 2022年 922卷 438-446页

作者： Tong, Weitian Xu, Yao Zhang, Huili Georgia Southern Univ Dept Comp Sci Statesboro GA 30458 USA Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China

As a hybrid of the Parallel Two-stage Flowshop problem and the Multiple Knapsack problem, we investigate the scheduling of parallel two-stage flowshops under makespan constraint, which was motivated by applications in cloud computing and introduced by Chen et al. [3] recently. A set of two-stage jobs are selected and scheduled on parallel two-stage flowshops to achieve the maximum total profit while maintaining the given makespan constraint. We give a positive answer to an open question about its approximability proposed by Chen et al. [3]. More specifically, based on guessing strategies and rounding techniques for linear programs, we present a polynomial time approximation scheme (PTAS) for the case when the number of flowshops is a fixed constant. As the case with two flowshops is already strongly NP-hard, our PTAS achieves the best possible approximation ratio. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Parallel two-stage flowshops Makespan constraint polynomial-time approximation scheme Multiple knapsacks Rounding

来源：评论

学校读者我要写书评

暂无评论

A Fully polynomial-time approximation scheme for Speed Scaling with a Sleep State

引用

ALGORITHMICA 2019年第9期81卷 3725-3745页

作者： Antoniadis, Antonios Huang, Chien-Chung Ott, Sebastian Saarland Univ Saarbrucken Germany Max Planck Inst Informat Saarbrucken Germany Ecole Normale Super Paris France

We study classical deadline-based preemptive scheduling of jobs in a computing environment equipped with both dynamic speed scaling and sleep state capabilities: Each job is specified by a release time, a deadline and a processing volume, and has to be scheduled on a single, speed-scalable processor that is supplied with a sleep state. In the sleep state, the processor consumes no energy, but a constant wake-up cost is required to transition back to the active state. In contrast to speed scaling alone, the addition of a sleep state makes it sometimes beneficial to accelerate the processing of jobs in order to transition the processor to the sleep state for longer amounts of time and incur further energy savings. The goal is to output a feasible schedule that minimizes the energy consumption. Since the introduction of the problem by Irani et al. (ACM Trans Algorithms 3(4), 2007), its exact computational complexity has been repeatedly posed as an open question (see e.g. Albers and Antoniadis in ACM Trans Algorithms 10(2):9, 2014;Baptiste et al. in ACM Trans Algorithms 8(3):26, 2012;Irani and Pruhs in SIGACT News 36(2):63-76, 2005). The currently best known upper and lower bounds are a 4 / 3-approximation algorithm and NP-hardness due to Albers and Antoniadis (2014) and Kumar and Shannigrahi (CoRR, 2013. ), respectively. We close the aforementioned gap between the upper and lower bound on the computational complexity of speed scaling with sleep state by presenting a fully polynomial-time approximation scheme for the problem. The scheme is based on a transformation to a non-preemptive variant of the problem, and a discretization that exploits a carefully defined lexicographical ordering among schedules.

关键词： approximation algorithms Energy efficiency polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks

引用

NETWORKS 2003年第4期42卷 202-208页

作者： Cheng, XZ Huang, X Li, DY Wu, WL Du, DZ Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA George Washington Univ Dept Comp Sci Washington DC 20052 USA 3M Co St Paul MN 55144 USA City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China Univ Texas Dept Comp Sci Richardson TX 75083 USA

A connected dominating set in a graph is a subset of vertices such that every vertex is either in the subset or adjacent to a vertex in the subset and the subgraph induced by the subset is connected. A minimum-connected dominating set is such a vertex subset with minimum cardinality. An application in ad hoc wireless networks requires the study of the minimum-connected dominating set in unit-disk graphs. In this paper, we design a (1 + 1/s)-approximation for the minimum-connected dominating set in unit-disk graphs, running in time n(O)((s log s)(2)). (C) 2003 Wiley Periodicals, Inc.

关键词： connected dominating set unit disk graph polynomial-time approximation scheme partition

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time approximation scheme for the Euclidean Problem on a Cycle Cover of a Graph

引用

PROCEEDINGS OF THE STEKLOV INSTITUTE OF MATHEMATICS 2015年第1-Sup期289卷 S111-S125页

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

We study the minimum-weight k-size cycle cover problem (Min-k-SCCP) of finding a partition of a complete weighted digraph into k vertex-disjoint cycles of minimum total weight. This problem is a natural generalization of the known traveling salesman problem (TSP) and has a number of applications in operations research and data analysis. We show that the problem is strongly NP-hard in the general case and preserves intractability even in the geometric statement. For the metric subclass of the problem, a 2-approximation algorithm is proposed. For the Euclidean Min-2-SCCP, a polynomial-time approximation scheme based on Arora's approach is built.

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

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time approximation scheme for an arbitrary number of parallel identical multi-stage flow-shops

引用

ANNALS OF OPERATIONS RESEARCH 2024年第1期335卷 185-204页

作者： Gong, Mingyang Lin, Guohui Miyano, Eiji Su, Bing Tong, Weitian Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Kyushu Inst Technol Dept Artificial Intelligence Iizuka Japan Xian Technol Univ Sch Econ & Management Xian Peoples R China Georgia Southern Univ Dept Comp Sci Statesboro GA 30458 USA

We investigate the seemingly untouched yet the most general parallel identical k-stage flow-shops scheduling, in which we are given an arbitrary number of indistinguishable k-stage flow-shops and a set of jobs each to be processed on one of the flow-shops, and the goal is to schedule these jobs to the flow-shops so as to minimize the makespan. Here the number k of stages is a fixed constant, but the number of flow-shops is part of the input. This scheduling problem is strongly NP-hard. To the best of our knowledge all previously presented approximation algorithms are for the special case where k=2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k = 2$$\end{document}, including a 17/6-approximation in 2017, a (2+epsilon)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(2 + \epsilon )$$\end{document}-approximation in 2018, and the most recent polynomial-time approximation scheme in 2020;they all take advantage of the number of stages being two. We deal with an arbitrary constant k >= 3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 3$$\end{document}, where the k-stage flow-shop scheduling is already strongly NP-hard. To define a configuration that summarizes the key information about the job assignments in a feasible schedule, we present novel concepts of big job type, big job assignment pair type, and flow-shop type. We show that the total number of distinct configurations is a polynomial in the input number of flow-shops. We t

关键词： Scheduling Parallel identical multi-stage flow-shops Makespan Configuration polynomial-time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Guillotine subdivisions approximate polygonal subdivisions:: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems

引用

SIAM JOURNAL ON COMPUTING 1999年第4期28卷 1298-1309页

作者： Mitchell, JSB SUNY Stony Brook Dept Appl Math & Stat Stony Brook NY 11794 USA

We show that any polygonal subdivision in the plane can be converted into an "m-guillotine" subdivision whose length is at most (1 + c/m) times that of the original subdivision, for a small constant c. "m-Guillotine" subdivisions have a simple recursive structure that allows one to search for the shortest of such subdivisions in polynomial time, using dynamic programming. In particular, a consequence of our main theorem is a simple polynomial-time approximation scheme for geometric instances of several network optimization problems, including the Steiner minimum spanning tree, the traveling salesperson problem (TSP), and the k-MST problem.

关键词： approximation algorithms polynomial-time approximation scheme traveling salesperson problem k-MST Steiner minimal trees guillotine subdivisions computational geometry

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs

引用

RANDOM STRUCTURES & ALGORITHMS 2024年第1期65卷 220-257页

作者： Ding, Jian Du, Hang Gong, Shuyang Peking Univ Sch Math Sci Beijing Peoples R China MIT Dept Math Cambridge MA USA

For two independent Erdos-Renyi graphs G(n,p)$$ \mathbf{G}\left(n,p\right) $$, we study the maximal overlap (i.e., the number of common edges) of these two graphs over all possible vertex correspondence. We present a polynomial-time algorithm which finds a vertex correspondence whose overlap approximates the maximal overlap up to a multiplicative factor that is arbitrarily close to 1. As a by-product, we prove that the maximal overlap is asymptotically n2 alpha-1$$ \frac{n}{2\alpha -1} $$ for p=n-alpha$$ p={n}<^>{-\alpha } $$ with some constant alpha is an element of(1/2,1)$$ \alpha \in \left(1/2,1\right) $$.

关键词： greedy algorithm polynomial-time approximation scheme random graph matching

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：