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

Strip generation algorithms for constrained two-dimensional two-staged cutting problems

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2006年第2期172卷 515-527页

作者： Hifi, M M'Hallah, R Univ Paris 01 CNRS UMR 8095 CERMSEM F-75647 Paris 13 France Univ Picardie LaRIA F-80000 Amiens France Kuwait Univ Dept Stat & Operat Res Safat 13060 Kuwait

The constrained two-dimensional cutting (C_TDC) problem consists of determining a cutting pattern of a set of n small rectangular piece types on a rectangular stock plate of length L and width W, as to maximize the sum of the profits of the pieces to be cut. Each piece type i, i = 1, . . . , n, is characterized by a length l(i),a width w(i), a profit (or weight) c(i) and an upper demand value b(i). The upper demand value is the maximum number of pieces of type i which can be cut on rectangle (L, W). In this paper, we study the two-staged fixed orientation C_TDC, noted FC_2TDC. It is a classical variant of the C_TDC where each piece is produced, in the final cutting pattern, by at most two guillotine cuts, and each piece has a fixed orientation. We solve the FC_2TDC problem using several approximate algorithms, that are mainly based upon a strip generation procedure. We evaluate the performance of these algorithms on instances extracted from the literature. (c) 2004 Elsevier B.V. All rights reserved.

关键词： approximate algorithms cutting problems dynamic programming single constrained knapsack problems optimization

来源：评论

学校读者我要写书评

暂无评论

Improving the detectability of cracks during flow inspection by 3D tomography

引用

RUSSIAN JOURNAL OF NONDESTRUCTIVE TESTING 2013年第2期49卷 121-130页

作者： Skokov, A. A. Karikh, V. P. Altai Fed Sci Prod Ctr Biisk Russia

The advantages of X-ray computer tomography over industrial radiography are described as applied to the problem of detecting arbitrarily oriented cracks. The approximate Feldkamp projection algorithm and the approximate reverse-projection algorithm with double differentiation filtration (RPDDF) are considered and methods for improving their accuracy are proposed. The possibility of increasing the reconstruction rate by using the pipelined algorithm and the spiral trajectory of a source is shown.

关键词： nondestructive testing radiography computer tomography spiral trajectory approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

Smart smart bounds for weighted response time scheduling

引用

SIAM JOURNAL ON COMPUTING 1998年第1期28卷 237-253页

作者： Schwiegelshohn, U Ludwig, W Wolf, JL Turek, J Yu, PS Univ Dortmund Dortmund Germany Univ Wisconsin Dept Comp Sci Madison WI 53706 USA IBM Corp Thomas J Watson Res Ctr Yorktown Heights NY 10598 USA

Consider a system of independent tasks to be scheduled without preemption on a parallel computer. For each task the number of processors required, the execution time, and a weight are known. The problem is to find a schedule with minimum weighted average response time. We present an algorithm called SMART (which stands for scheduling to minimize average response time) for this problem that produces solutions that are within a factor of 8.53 of optimal. To our knowledge this is the first polynomial-time algorithm for the minimum weighted average response time problem that achieves a constant bound. In addition, for the unweighted case (that is, where all the weights are unity) we describe a variant of SMART that produces solutions that are within a factor of 8 of optimal, improving upon the best known bound of 32 for this special case.

关键词： scheduling parallel computing approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

PRODUCTION SCHEDULING PROBLEMS IN A TEXTILE-INDUSTRY

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1992年第2期58卷 173-190页

作者： SERAFINI, P SPERANZA, MG UNIV UDINE DEPT MATH & COMP SCII-33100 UDINEITALY

In this paper scheduling problems arising in a textile industry are analysed. The maximum tardiness is taken as an objective function. Bounds on the optimal solutions are derived in the general case;the worst-case behaviour of approximate algorithms is investigated in case of uniform looms and a polynomial algorithm is presented for the case of equal looms with identical deadlines. Finally an LP-based heuristic is presented for the general case.

关键词： SCHEDULING approximate algorithms WORST-CASE ANALYSIS TEXTILE INDUSTRY

来源：评论

学校读者我要写书评

暂无评论

Better approximation ratios for the single-vehicle scheduling problems on line-shaped networks

引用

NETWORKS 2002年第4期39卷 203-209页

作者： Karuno, Y Nagamochi, H Ibaraki, T Kyoto Inst Technol Fac Engn & Design Dept Mech & Syst Engn Sakyo Ku Kyoto 6068585 Japan Toyohashi Univ Technol Fac Engn Dept Informat & Comp Sci Toyohashi Aichi 4418580 Japan Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Sakyo Ku Kyoto 6068501 Japan

We consider two variants of the single-vehicle scheduling problem on line-shaped networks. Let L = (V, E) be a line, where V = {v(1), v(2),..., v(n)} is a set of n vertices and E = {{v(i), v(i+1)]\i = 1, 2,..., n - 1) is a set of edges. The travel times w(u, v) and w(v, u) are associated with each edge {u, v) is an element of E, and each job, which is also denoted as v and is located at vertex v is an element of V, has release time r(v) and handling time h(v). There is a single vehicle, which is initially situated at v(1) is an element of V, and visits all vertices to process the jobs before it returns back to v(1). The first problem asks to find an optimal routing schedule of the vehicle that minimizes the completion time. This is NP-hard [21], and there exists an approximate algorithm with the approximation ratio of 2 [12]. In this paper, we improve this ratio to 1.5. On the other hand, the second problem minimizes the maximum lateness, under the assumption that all release times r(v) are zero, but there are due times d(v) for v is an element of V and d(v(n+1)) for the vehicle. This problem is also NP-hard [13]. We improve the previous best-known approximation ratio of 2, which was obtained in [11], to 1.5. (C) 2002 Wiley Periodicals, Inc.

关键词： routing and scheduling approximate algorithms performance guarantee worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

A GREEDY HEURISTIC FOR A MINIMUM-WEIGHT FOREST PROBLEM

引用

OPERATIONS RESEARCH LETTERS 1993年第2期14卷 65-71页

作者： IMIELINSKA, C KALANTARI, B KHACHIYAN, L RUTGERS UNIV DEPT COMP SCINEW BRUNSWICKNJ 08903

Given an undirected edge-weighted graph and a natural number m, we consider the problem of finding a minimum-weight spanning forest such that each of its trees spans at least m vertices. For m greater-than-or-equal-to 4, the problem is shown to be NP-hard. We describe a simple 2-approximate greedy heuristic that runs within the time needed to compute a minimum spanning tree. If the edge weights satisfy the triangle inequality, any such a 2-approximate solution, in linear time, can be converted into a 4-approximate solution for the problem of covering the graph with minimum-weight vertex disjoint cycles of size at least m.

关键词： approximate algorithms COMBINATORIAL PROBLEMS

来源：评论

学校读者我要写书评

暂无评论

ON THE EXISTENCE OF WEAK GREEDY MATCHING HEURISTICS

引用

OPERATIONS RESEARCH LETTERS 1986年第4期5卷 201-205页

作者： GRIGORIADIS, MD KALANTARI, B LAI, CY Department of Computer Science Rutgers University New Brunswick NJ 08903 USA

We exhibit an exponential number of greedy heuristics for minimum weight perfect matching of complete graphs of n vertices with edge weights satisfying the triangle inequality. The ratio of the weight of an approximate solution obtained by these heuristics to that of an optimal solution is shown to be bounded above by finite valued functions which depend only on n .

关键词： approximate algorithms complexity heuristics weighted perfect mathing

来源：评论

学校读者我要写书评

暂无评论

Group-based collective keyword querying in road networks

引用

INFORMATION PROCESSING LETTERS 2017年第Feb.期118卷 83-90页

作者： Su, Sen Zhao, Sen Cheng, Xiang Bi, Rong Cao, Xin Wang, Jie Beijing Univ Posts & Telecommun Beijing Peoples R China Queens Univ Belfast Belfast Antrim North Ireland Univ Massachusetts Lowell Lowell MA USA

This paper addresses a group-based collective keyword (GBCK) query problem in road networks. We model the road network as an undirected graph, where each node locating in a two-dimensional space represents a road intersection or a Points of Interest (POI), and each edge with weight represents a road segment. The GBCK query aims to find a region containing a set of POIs that covers all the query keywords and these POIs are close to the group of users and are close to each other. We show the problem of answering the GBCK query is NP-hard. To solve this problem, we develop a series of query processing algorithms. We first propose an efficient algorithm, which gives a 5-factor approximation to find a feasible region. The cost of this region is further used to limit the search space in the other algorithms. We then propose an exact algorithm, and an approximate algorithm with a 15/7-factor approximation. Extensive performance studies using real datasets confirm the efficiency and accuracy of the proposed algorithms. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Design of algorithms Collective keyword query Road networks approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

Differential approximation of NP-hard problems with equal size feasible solutions

引用

RAIRO-OPERATIONS RESEARCH 2002年第4期36卷 279-297页

作者： Monnot, J Univ Paris 09 LAMSADE F-75775 Paris 16 France

In this paper, we focus on some specific optimization problems from graph theory, those for which all feasible solutions have an equal size that depends on the instance size. Once having provided a formal definition of this class of problems, we try to extract some of its basic properties;most of these are deduced from the equivalence, under differential approximation, between two versions of a problem pi which only differ on a linear transformation of their objective functions. This is notably the case of maximization and minimization versions of pi, as well as general minimization and minimization with triangular inequality versions of pi. Then, we prove that some well known problems do belong to this class, such as special cases of both spanning tree and vehicles routing problems. In particular, we study the strict rural postman problem (called SRPP) and show that both the maximization and the minimization versions can be approximately solved, in polynomial time, within a differential ratio bounded above by 1/2. From these results, we derive new bounds for standard ratio when restricting edge weights to the interval [a, ta] (the SRPP[t] problem): we respectively provide a 2/(t+1)- and a (t+1)/2t-standard approximation for the minimization and the maximization versions.

关键词： approximate algorithms differential ratio performance ratio analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient index-independent approaches for the collective spatial keyword queries

引用

NEUROCOMPUTING 2021年 439卷 96-105页

作者： Yang, Zhibang Zeng, Yifu Du, Jiayi Li, Fangmin Salah, Ahmad Changsha Univ Coll Comp Engn & Appl Math Changsha 410022 Hunan Peoples R China Cent South Univ Forestry & Technol Coll Comp & Informat Engn Changsha 410004 Hunan Peoples R China Changsha Univ Hunan Prov Key Lab Ind Internet Technol & Secur Changsha 410022 Peoples R China Zagazig Univ Dept Comp Sci Shakia 44519 Zigazig Egypt

In abundant location-based service applications, it is necessary to process continuous spatial keyword queries over geo-textual data streaming. As an important spatial keyword query, the collective spatial keyword (CSK) query aims to find a set of objects such that it covers all the given keywords collectively, the objects within the set are nearest to the query point, and it has the minimum distance between different objects. The existing approaches for the CSK query are mostly index-based algorithms. Although these approaches gain superior performance, their applicability is significantly limited by the necessity to create an index to organize the dataset. Therefore, these index-based approaches cannot be utilized to process data streaming that prevalently exists in most location-based service applications. In addition, the existing algorithms have much room for improvement as the distances between different objects are overlooked when generating feasible candidate sets. Moreover, the results returned by the proposed algorithms could be further refined to offer better decision support for users. In this paper, a greedy algorithm and an approximate algorithm with a provable approximate bound are proposed for the CSK query. Our approaches are appropriate to the CSK queries where the datasets are not suitable to be organized by indexes and can get better query results with less objects and smaller function scores. To boost the query performance, new pruning strategies and heuristic rules are developed. The experimental results demonstrate scalability, efficiency, and effectiveness of the proposed algorithms. (c) 2021 Elsevier B.V. All rights reserved.

关键词： approximate algorithms Keyword query Spatial query Np-hard

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：