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

Multiple Subset Sum with Inclusive Assignment Set Restrictions

NAVAL RESEARCH LOGISTICS 2011年第6期58卷 546-563页

作者： Kellerer, Hans Leung, Joseph Y. -T. Li, Chung-Lun Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Graz Univ Inst Stat & Operat Res A-8010 Graz Austria New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

In a traditional multiple subset sum problem (MSSP), there is a given set of items and a given set of bins (or knapsacks) with identical capacities. The objective is to select a subset of the items and pack them into the bins such that the total weight of the selected items is maximized. However, in many applications of the MSSP, the bins have assignment restrictions. In this article, we study the subset sum problem with inclusive assignment set restrictions, in which the assignment set of one item (i.e., the set of bins that the item may be assigned to) must be either a subset or a superset of the assignment set of another item. We develop an efficient 0.6492-approximation algorithm and test its effectiveness via computational experiments. We also develop a polynomial time approximation scheme for this problem. (C) 2011 Wiley Periodicals, Inc. Naval Research Logistics 58: 546-563, 2011

关键词： subset sum inclusive assignment sets worst case analysis polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics

引用

ACM TRANSACTIONS ON ALGORITHMS 2020年第2期16卷 24-24页

作者： Chan, T-H Hubert Jiang, Haotian Jiang, Shaofeng H-C Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Univ Washington Paul G Allen Sch Comp Sci & Engn Seattle WA 98195 USA Weizmann Inst Sci Fac Math & Comp Sci Rehovot Israel

We present a unified (randomized) polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) in doubling metrics. Given a metric space and a penalty function on a subset of points known as terminals, a solution is a subgraph on points in the metric space whose cost is the weight of its edges plus the penalty due to terminals not covered by the subgraph. Under our unified framework, the solution subgraph needs to be Eulerian for PCTSP, while it needs to be a tree for PCSTP. Before our work, even a QPTAS for the problems in doubling metrics is not known. Our unified PTAS is based on the previous dynamic programming frameworks proposed in Talwar (STOC 2004) and Bartal, Gottlieb, Krauthgamer (STOC 2012). However, since it is unknown which part of the optimal cost is due to edge lengths and which part is due to penalties of uncovered terminals, we need to develop new techniques to apply previous divide-and-conquer strategies and sparse instance decompositions.

关键词： Doubling dimension prize collecting traveling salesman problem Steiner tree problem polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

approximation schemes for scheduling on uniformly related and identical parallel machines

引用

ALGORITHMICA 2004年第1期39卷 43-57页

作者： Epstein, L Sgall, J Tel Aviv Univ IL-69978 Tel Aviv Israel Interdisciplinary Ctr Sch Comp Sci Herzliyya Israel Acad Sci Czech Republ Math Inst CZ-11567 Prague 1 Czech Republic Inst Comp Sci Prague Czech Republic

We give a polynomial approximation scheme for the problem of scheduling on uniformly related parallel machines for a large class of objective functions that depend only on the machine completion times, including minimizing the l(p) norm of the vector of completion times. This generalizes and simplifies many previous results in this area.

关键词： scheduling approximation algorithms parallel machines machine completion time polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

BIQUADRATIC OPTIMIZATION OVER UNIT SPHERES AND SEMIDEFINITE PROGRAMMING RELAXATIONS

引用

SIAM JOURNAL ON OPTIMIZATION 2009年第3期20卷 1286-1310页

作者： Ling, Chen Nie, Jiawang Qi, Liqun Ye, Yinyu Zhejiang Univ Finance & Econ Sch Math & Stat Hangzhou 310018 Peoples R China Univ Calif San Diego Dept Math La Jolla CA 92093 USA Hong Kong Polytech Univ Dept Appl Math Kowloon Hong Kong Peoples R China Stanford Univ Dept Management Sci & Engn Stanford CA 94305 USA

This paper studies the so-called biquadratic optimization over unit spheres min(x is an element of Rn),(y is an element of Rm) Sigma 1 <= i,k <= n, 1 <= j, l <= m(bijklxiyjxkyl), subject to parallel to x parallel to = 1, parallel to y parallel to = 1. We show that this problem is NP-hard, and there is no polynomial time algorithm returning a positive relative approximation bound. Then, we present various approximation methods based on semidefinite programming (SDP) relaxations. Our theoretical results are as follows: For general biquadratic forms, we develop a 1/2max{m, n}(2)-approximation algorithm under a slightly weaker approximation notion;for biquadratic forms that are square-free, we give a relative approximation bound 1/nm;when min{n, m} is a constant, we present two polynomial time approximation schemes (PTASs) which are based on sum of squares (SOS) relaxation hierarchy and grid sampling of the standard simplex. For practical computational purposes, we propose the first order SOS relaxation, a convex quadratic SDP relaxation, and a simple minimum eigenvalue method and show their error bounds. Some illustrative numerical examples are also included.

关键词： biquadratic optimization semidefinite programming approximate solution sum of squares polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

A PTAS for non-resumable open shop scheduling with an availability constraint

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第2期43卷 350-362页

作者： Yuan, Yuan Lan, Yan Ding, Ning Han, Xin Dalian Univ Technol Sch Software Technol Dalian 116620 Peoples R China Dalian Minzu Univ Sch Informat & Commun Engn Dalian 116600 Peoples R China

Shop scheduling problem is one of the most classical problems in combinatorial optimization. In this paper, we study two-machine open shop scheduling problem, provided that one machine is subject to maintenance period which has to be performed in a fixed time interval. The target is to minimize the makespan. This paper considers non-resumable scenario, i.e., if a job which starts before the maintenance period cannot be completed before the maintenance period, then it must be restarted after the interval from scratch. We only discuss the case that the maintenance period is performed on the first machine, while the case of the maintenance period on the second machine is symmetric. We obtain a polynomial time approximation scheme, which is better than the best previous result 4/3.

关键词： Open shop scheduling Machine non-availability approximation algorithm polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Efficient independent set approximation in unit disk graphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 280卷 63-70页

作者： Das, Gautam K. da Fonseca, Guilherme D. Jallu, Ramesh K. Indian Inst Technol Guwahati Dept Math Gauhati India Univ Auvergne Clermont Ferrand France LIMOS Clermont Ferrand France

We consider the maximum (weight) independent set problem in unit disk graphs. The high complexity of the existing polynomial-time approximation schemes motivated the development of faster constant approximation algorithms. In this paper, we present a 2.16-approximation algorithm that runs in O(nlog(2)n) time and a 2-approximation algorithm that runs in O(n(2) log n) time for the unweighted version of the problem. In the weighted version, the running times increase by an O(log n) factor. Our algorithms are based on a classic strip decomposition, but we improve over previous algorithms by efficiently using geometric data structures. We also propose a PTAS for the unweighted version. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Maximum independent set Unit disk graph approximation algorithms polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Scheduling parallel machines with inclusive processing set restrictions

引用

NAVAL RESEARCH LOGISTICS 2008年第4期55卷 328-338页

作者： Ou, Jinwen Leung, Joseph Y. -T. Li, Chung-Lun Hong Kong Polytech Univ Dept Logist Kowloon Hong Kong Peoples R China Jinan Univ Dept Adm Management Guangzhou 510632 Peoples R China New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We consider the problem of assigning a set of jobs to different parallel machines of the same processing speed, where each job is compatible to only a subset of those machines. The machines can be linearly ordered such that a higher-indexed machine can process all those jobs that a lower-indexed machine can process. The objective is to minimize the makespan of the schedule. This problem is motivated by industrial applications such as cargo handling by cranes with nonidentical weight capacities, computer processor scheduling with memory constraints, and grades of service provision by parallel servers. We develop an efficient algorithm for this problem with a worst-case performance ratio of 4/3 + epsilon, where epsilon is a positive constant which may be set arbitrarily close to zero. We also present a polynomial time approximation scheme for this problem, which answers an open question in the literature. (C) 2008 Wiley Periodicals, Inc.

关键词： scheduling parallel machines worst-case analysis polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Improved approximation schemes for Early Work Scheduling on Identical Parallel Machines with a Common Due Date

引用

Journal of the Operations Research Society of China 2024年第2期12卷 341-350页

作者： Wei-Dong Li School of Mathematics and Statistics Yunnan UniversityKunming650504YunnanChina

We study the early work scheduling problem on identical parallel machines in order to maximize the total early work,i.e.,the parts of non-preemptive jobs that are executed before a common due *** preprocessing and constructing an auxiliary instance which has several good properties,for any desired accuracy,we propose an efficient polynomial time approximation scheme with running time O(f(1/ε)n),where n is the number of jobs and f(1/ε)is exponential in 1/ε,and a fully polynomial time approximation scheme with running time O(1/ε^(2m+1)+n)when the number of machines is fixed.

关键词： Scheduling Early work polynomial time approximation scheme Effcient polynomial time approximation scheme Fully polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for the combination problem of parallel machine scheduling and path

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第3期38卷 689-697页

作者： Guan, Li Li, Jianping Li, Weidong Lichen, Junran Yunnan Univ Sch Math & Stat Kunming 650504 Yunnan Peoples R China

In this paper, we study a combination problem of parallel machine scheduling and the s-t path problem, which is to find a s-t path P-st of the given directed graph, and to schedule the jobs corresponding to the arcs of the path P-st on m parallel machines, such that the makespan is minimized. It has been proved that this problem is NP-hard and admits 2-approximation algorithm. We present a polynomial-time algorithm with approximation ratio 1.5. By modifying the dynamic programming method for the restricted shortest path problem, we also give a polynomial time approximation scheme.

关键词： Parallel machine scheduling Shortest path approximation algorithm polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

PACKING SQUARES WITH PROFITS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2012年第1期26卷 263-279页

作者： Jansen, Klaus Solis-Oba, Roberto Univ Kiel Inst Informat Kiel Germany Univ Western Ontario Dept Comp Sci London ON Canada

We study the following square packing problem: Given a set Q of squares with positive profits, the goal is to pack a subset of Q into a rectangular bin R so that the total profit of the squares packed in R is maximized. Squares must be packed so that their sides are parallel to those of R. We present a polynomial time approximation scheme for the problem, which for any value epsilon > 0 finds and packs a subset Q' subset of Q of profit at least (1 - epsilon)OPT, where OPT is the profit of an optimum solution.

关键词： polynomial time approximation scheme square packing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：