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

On the approximability of the two-phase knapsack problem

JOURNAL OF COMBINATORIAL OPTIMIZATION 2019年第4期38卷 1155-1179页

作者： Nip, Kameng Wang, Zhenbo Sun Yat Sen Univ Sch Math Zhuhai Zhuhai Peoples R China Tsinghua Univ Dept Math Sci Beijing Peoples R China

We consider a natural generalization of the knapsack problem and the multiple knapsack problem, which has two phases of packing decisions. In this problem, we have a set of items, several small knapsacks called boxes, and a large knapsack called container. Each item has a size and profit, each box has a size and the container has a capacity. The first phase is to select some items to pack into the boxes, and the second phase is to select the boxes (each includes some packed items) to pack into the container. The total profit of the problem is determined by the items that are selected and packed into the container within some packed box, and the objective is to maximize the total profit. This problem is motivated by various practical applications, e.g., in logistics. It is a generalization of the multiple knapsack problem, and hence is strongly NP-hard. We mainly propose three approximation algorithms for it. Particularly, the first one is a 1 4 -approximation algorithm based on its linear programming relaxation;the second one is based on applying the algorithms for the multiple knapsack problem and the knapsack problem, and has an approximation ratio 1/3 - epsilon for any small enough epsilon > 0. We finally provide a polynomial time approximation scheme for this problem.

关键词： Two-phase knapsack Multiple knapsack approximation algorithms polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Closing the Gap for Makespan Scheduling via Sparsification Techniques

引用

MATHEMATICS OF OPERATIONS RESEARCH 2020年第4期45卷 1371-1392页

作者： Jansen, Klaus Klein, Kim-Manuel Verschae, Jose Univ Kiel Dept Comp Sci D-24118 Kiel Germany Univ OHiggins Inst Engn Sci Rancagua 2820000 Chile

Makespan scheduling on identical machines is one of the most basic and fundamental packing problems studied in the discrete optimization literature. It asks for an assignment of n jobs to a set of m identical machines that minimizes the makespan. The problem is strongly NP-hard, and thus we do not expect a (1 + epsilon)-approximation algorithm with a running time that depends polynomially on 1/epsilon. It has been recently shown that a subexponential running time on 1/epsilon would imply that the Exponential time Hypothesis (ETH) fails. A long sequence of algorithms have been developed that try to obtain low dependencies on 1/epsilon, the better of which achieves a quadratic running time on the exponent. In this paper we obtain an algorithm with an almost-linear dependency on 1/epsilon in the exponent, which is tight under ETH up to logarithmic factors. Our main technical contribution is a new structural result on the configuration-IP integer linear program. More precisely, we show the existence of a highly symmetric and sparse optimal solution, in which all but a constant number of machines are assigned a configuration with small support. This structure can then be exploited by integer programming techniques and enumeration. We believe that our structural result is of independent interest and should find applications to other settings. We exemplify this by applying our structural results to the minimum makespan problem on related machines and to a larger class of objective functions on parallel machines. For all these cases, we obtain an efficient PTAS with running time with an almost-linear dependency on 1/epsilon and polynomial in n.

关键词： scheduling approximation algorithms polynomial time approximation scheme makespan conditional lower bounds

来源：评论

学校读者我要写书评

暂无评论

Energy-Efficient Task Allocation of Heterogeneous Resources in Mobile Edge Computing

引用

IEEE ACCESS 2021年 9卷 119700-119711页

作者： Liu, Xi Liu, Jun Wu, Hong Qujing Normal Univ Sch Informat Engn Qujing 655000 Peoples R China Qujing Normal Univ Inst Appl Math Qujing 655000 Peoples R China

The edge cloud provides heterogeneous resources, such as cores, memory, and storage which are then allocated to mobile applications in mobile edge computing, which require multiple types of resources to execute. While current work on mobile edge computing focuses on tasks needing a single resource to run, we investigate the task allocation problem aiming to minimize total energy consumption while considering heterogeneous resource settings. Specifically, we consider the binary computation offloading mode, in which a task executes successfully as a whole. We formulate this as an integer programming problem, and transform that to the two subproblems of the resource allocation and the offloading decision. We propose a heuristic approach to solve the resource allocation subproblem and an approximation algorithm for the offloading decision subproblem. We show that our proposed approximation algorithm is a polynomial time approximation scheme, and hence it achieves a tradeoff between optimality loss and time complexity. Experimental results demonstrate that the performance of our proposed algorithm scales very well for multi-resource allocation in different conditions, and it achieves a good balance of performance and speed.

关键词： Task analysis Resource management Mobile handsets Edge computing Servers approximation algorithms Cloud computing Mobile edge computing computation offloading resource allocation energy efficient polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

LOCAL SEARCH YIELDS A PTAS FOR k-MEANS IN DOUBLING METRICS

引用

SIAM JOURNAL ON COMPUTING 2019年第2期48卷 452-480页

作者： Friggstad, Zachary Rezapour, Mohsen Salavatipour, Mohammad R. Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

The most well-known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly k-MEANS: given a set of data points and a parameter k, select k centers and partition the data points into k clusters around these centers so that the sum of squares of distances of the points to their cluster center is minimized. Typically these data points lie in Euclidean space R-d for some d >= 2. k-MEANS and the first algorithms for it were introduced in the 1950s. Over the last six decades, hundreds of papers have studied this problem and different algorithms have been proposed for it. The most commonly used algorithm in practice is known as Lloyd-Forgy, which is also referred to as "the" k-MEANS algorithm, and various extensions of it often work very well in practice. However, they may produce solutions whose cost is arbitrarily large compared to the optimum solution. Kanungo et al. [Comput. Geom., 28 (2004), pp. 89-112] analyzed a very simple local search heuristic to get a polynomial-time algorithm with approximation ratio 9 + epsilon for any fixed epsilon > 0 for k-MEANS in Euclidean space. Finding an algorithm with a better worst-case approximation guarantee has remained one of the biggest open questions in this area, in particular, whether one can get a true polynomial-time approximation scheme (PTAS) for fixed dimension Euclidean space. We settle this problem by showing that a simple local search algorithm provides a PTAS for k-MEANS for R-d for any fixed d. More precisely, for any error parameter epsilon > 0, the local search algorithm that considers swaps of up to rho = d(O(d)). epsilon(-O(d/epsilon)) centers at a time will produce a solution using exactly k centers whose cost is at most a (1 + epsilon)-factor greater than the optimum solution. Although the algorithm is not practical due to the large polynomial running time, it settles the approximability of this important problem. Our analysis extends very easily to the more general sett

关键词： k-MEANS polynomial time approximation scheme doubling metrics

来源：评论

学校读者我要写书评

暂无评论

PTAS for minimum weighted connected vertex cover problem with c-local condition in unit disk graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第4期22卷 663-673页

作者： Fan, Lidan Zhang, Zhao Wang, Wei Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Xi An Jiao Tong Univ Coll Sci Xian 710049 Peoples R China

Given a graph G=(V,E) with node weight w:V -> R (+), the minimum weighted connected vertex cover problem (MWCVC) is to seek a subset of vertices of the graph with minimum total weight, such that for any edge of the graph, at least one endpoint of the edge is contained in the subset, and the subgraph induced by this subset is connected. In this paper, we study the problem on unit disk graph. A polynomial-time approximation scheme (PTAS) for MWCVC is presented under the condition that the graph is c-local.

关键词： Minimum weighted connected vertex cover c-local polynomial time approximation scheme Unit disk graph

来源：评论

学校读者我要写书评

暂无评论

Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2020年第1-3期88卷 53-69页

作者： Khachay, Michael Neznakhina, Katherine Krasovsky Inst Math & Mech Ekaterinburg Russia Ural Fed Univ Ekaterinburg Russia Omsk State Tech Univ Omsk Russia

We consider the geometric version of the well-known Generalized Traveling Salesman Problem introduced in 2015 by Bhattacharya et al. that is called the Euclidean Generalized Traveling Salesman Problem in Grid Clusters (EGTSP-GC). They proved the intractability of the problem and proposed first polynomial time algorithms with fixed approximation factors. The extension of these results in the field of constructing the polynomial time approximation schemes (PTAS) and the description of non-trivial polynomial time solvable subclasses for the EGTSP-GC appear to be relevant in the light of the classic C. Papadimitriou result on the intractability of the Euclidean TSP and recent inapproximability results for the Traveling Salesman Problem with Neighborhoods (TSPN) in the case of discrete neighborhoods. In this paper, we propose Efficient polynomial time approximation schemes (EPTAS) for two special cases of the EGTSP-GC, when the number of clusters k=O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$k=O(\log n)$\end{document} and k=n-O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$k=n-O(\log n)$\end{document}. Also, we show that any time, when one of the grid dimensions (height or width) is fixed, the EGTSP-GC can be solved to optimality in polynomial time. As a consequence, we specify a novel non-trivial polynomially solvable subclass of the Euclidean TSP in the plane.

关键词： Generalized traveling salesman problem polynomial time approximation scheme polynomial time solvable subclass

来源：评论

学校读者我要写书评

暂无评论

Exact and approximation algorithms for finding an optimal bridge connecting two simple polygons

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2005年第6期15卷 609-630页

作者： Bhosle, AM Gonzalez, TF Amazon Software Dev Ctr Bangalore 560001 Karnataka India Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

Given two simple polygons P and Q we define the weight of a bridge (p, q), with p is an element of rho(p) and q is an element of rho(Q), where rho() denotes the compact region enclosed by the boundary of the polygon, between the two polygons as gd(p, P) + d(p, q) + gd(q, Q), where d(p, q) is the Euclidean distance between the points p and q, and gd(x, X) is the geodesic distance between x and its geodesic furthest neighbor on X. Our problem differs from another version of the problem where the additional restriction of requiring the endpoints of the bridge to be mutually visible was imposed. We show that an optimal bridge always exists such that the endpoints of the bridge lie on the boundaries of the two polygons. Using this critical property, we present an algorithm to find an optimal bridge (of minimum weight) in O(n(2) log n) time. We present a polynomial time approximation scheme that for any epsilon > 0 generates a bridge with objective function within a factor of 1 + epsilon of the optimal value in O(kn log kn) time, where k = 2 * [1/log(1+epsilon)]. An improved polynomial time approximation scheme and algorithms for generalized versions of our problems are also discussed.

关键词： optimal bridge between polygons polynomial time approximation scheme exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling three-operation jobs in a two-machine flow shop to minimize makespan

引用

ANNALS OF OPERATIONS RESEARCH 2004年第1-4期129卷 171-185页

作者： Gupta, JND Koulamas, CP Kyparisis, GJ Potts, CN Strusevich, VA Univ Alabama Coll Adm Sci Dept Accounting & Informat Syst Huntsville AL 35899 USA Florida Int Univ Dept Decis Sci & Informat Syst Miami FL 33199 USA Univ Southampton Fac Math Studies Southampton SO17 1BJ Hants England Univ Greenwich Sch Comp & Math Sci London SE10 9LS England

This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented.

关键词： scheduling flow shop makespan approximation algorithm polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Hardness and approximation of octilinear Steiner trees

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2007年第3期17卷 231-260页

作者： Mueller-Hannemann, Matthias Schulze, Anna Tech Univ Darmstadt Dept Comp Sci D-64289 Darmstadt Germany Univ Cologne Zentrum Angew Informat Koln D-50931 Cologne Germany

Given a point set K of terminals in the plane, the octilinear Steiner tree problem is to find a shortest tree that interconnects all terminals and edges run either in horizontal, vertical. or +/- 45 degrees diagonal direction. This problem is fundamental for the novel octilinear routing paradigm in VLSI design, the so-called X-architecture. As the related rectilinear and the Euclidian Steiner tree problem are well-known to be NP-hard, the same was widely believed for the octilinear Steiner tree problem but left open for quite some time. In this paper, we prove the NP-completeness of the decision version of the octilinear Steiner tree problem. We also show how to reduce the octilinear Steiner tree problem to the Steiner tree problem in graphs of polynomial size with the following approximation guarantee. We construct a planar graph of size O(n(2)/epsilon(2)) which contains a (1 + epsilon)-approximation of a minimum octilinear Steiner tree for every epsilon > 0 and n = vertical bar K vertical bar. Hence, we can apply any alpha-approximation algorithm for the Steiner tree problem in graphs (for planar graphs, Borradaile et al. very recently presented a polynomial time approximation scheme) and achieve an (alpha + epsilon)-approximation bound for the octilinear Steiner tree problem. This approximation guarantee also holds for the more difficult case where the Steiner tree has to avoid blockages (obstacles bounded by octilinear polygons).

关键词： Steiner trees octilinear routing NP-completeness VLSI design blockages polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Minimizing total weighted completion time on identical parallel batch machines

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2006年第6期17卷 1441-1453页

作者： Li, Shuguang Li, Guojun Qi, Xingqin Shandong Univ Sch Math & Syst Sci Jinan 250100 Peoples R China Yantai Univ Dept Math & Informat Sci Yantai 264005 Peoples R China Chinese Acad Sci Inst Software Beijing 100080 Peoples R China Shandong Univ Weihai Dept Appl Math Weihai 264213 Peoples R China

We study the problem of scheduling n jobs with release dates on m identical parallel batch machines to minimize the total weighted completion time of the jobs. A batch machine with capacity B (B < n) is able to process a batch of up to B jobs simultaneously and the time needed is equal to the maximum processing time among the jobs in the batch. This model is motivated by applications in the manufacturing of integrated circuits. In this paper, we present a polynomial time approximation scheme (PTAS) for this problem.

关键词： approximation algorithms batch scheduling total weighted completion time polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：