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

Solving the parallel processor scheduling and bin packing problems with contiguity constraints: Mathematical models and computational studies

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2025年第3期323卷 701-723页

作者： Akcay, Fatih Burak Delorme, Maxence Tilburg Univ Dept Econometr & Operat Res Tilburg Netherlands

The parallel processor scheduling and bin packing problems with contiguity constraints are important in the field of combinatorial optimization because both problems can be used as components of effective exact decomposition approaches for several two-dimensional packing problems. In this study, we provide an extensive review of existing mathematical formulations for the two problems, together with some model enhancements and lower bounding techniques, and we empirically evaluate the computational behavior of each of these elements using a state-of-the-art solver on a large set of literature instances. We also assess whether recent developments such as meet-in-the middle patterns and the reflect formulation can be used to solve the two problems more effectively. Our experiments demonstrate that some features, such as the mathematical model used, have a major impact on whether an approach is able to solve an instance, whereas other features, such as the use of symmetry-breaking constraints, do not bring any empirical advantage despite being useful in theory. Overall, our goal is to help the research community design more effective yet simpler algorithms to solve the parallel processor scheduling and bin packing problems with contiguity constraints and closely related extensions so that, eventually, those can be integrated into a larger number of exact methods for two-dimensional packing problems.

关键词： Packing Contiguity constraints exact algorithms Computational evaluation

来源：评论

学校读者我要写书评

暂无评论

Parallelizing exact motif finding algorithms on multi-core

引用

JOURNAL OF SUPERCOMPUTING 2014年第2期69卷 814-826页

作者： Abbas, Mostafa M. Bahig, Hazem M. Abouelhoda, Mohamed Mohie-Eldin, M. M. Qatar Univ Coll Engn KINDI Lab Comp Res Doha Qatar Sinai Univ Dept Basic Sci Fac Engn Al Arish Egypt Hail Univ Coll Comp Sci & Engn Comp Sci & Software Engn Dept Hail Saudi Arabia Ain Shams Univ Div Comp Sci Dept Math Fac Sci Cairo 11566 Egypt Cairo Univ Syst & Biomed Engn Dept Fac Engn Giza Egypt Nile Univ Ctr Informat Sci Giza Egypt Al Azhar Univ Fac Sci Dept Math Cairo Egypt

The motif finding problem is one of the important and challenging problems in bioinformatics. A variety of sequential algorithms have been proposed to find exact motifs, but the running time is still not suitable due to high computational complexity of finding motifs. In this paper we parallelize three efficient sequential algorithms which are HEPPMSprune, PMS5 and PMS6. We implement the algorithms on a Dual Quad-Core machine using openMP to measure the performance of each algorithm. Our experiment on simulated data show that: (1) the parallel PMS6 is faster than the other algorithms in case of challenging instances, while the parallel HEPPMSprune is faster than the other algorithms in most of solvable instances;(2) the scalability of parallel HEPPMSprune is linear for all instances, while the scalability of parallel PMS5 and PMS6 is linear in case of challenging instances only;(3) the memory used by HEPPMSprune is less than that of the other algorithms.

关键词： exact algorithms Motif finding Multi-core Challenging and solvable instances

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of local ROI algorithms for exact ROI reconstruction in spiral cone-beam computed tomography

引用

IEEE TRANSACTIONS ON NUCLEAR SCIENCE 2001年第3期48卷 697-702页

作者： Sourbelle, K Lauritsch, G Tam, KC Noo, F Kalender, WA Inst Med Phys D-91054 Erlangen Germany Siemens Med Engn D-91050 Erlangen Germany Siemens Corp Res Princeton NJ 08540 USA Inst Elect Montefiore B-4000 Liege Belgium

This paper investigates the performance of exact reconstruction algorithms for spiral cone-beam computed tomography. We compare two different approaches of exact algorithms: the first one is the Radon algorithm with explicit calculation of radon data and subsequent direct inversion, the second approach is a reformulation of the Radon algorithm as a three-dimensional (3-D) filtered backprojection (FBP) method. Both algorithms are able to reconstruct a region of interest (ROI) of a long object by using the local ROI technique. The goal of this study is to identify which algorithm has the better performance with respect to image quality and practicability. The properties of the algorithms are analyzed. Image quality is evaluated regarding artifacts, spatial as well as contrast resolution, and noise properties. The 3-D point spread function (PSF) is examined for violations of isotropy and spatial invariance. In-plane and axial resolutions are derived from the in-plane modulation transfer function (MTF) and the slice sensitivity profile (SSP), respectively. The results show that for the two implementations investigated in this study, the image quality is similar, with a slight advantage of the FBP case. The algorithms yield images almost free of artifacts but with a poor spatial resolution. Regarding practicability, however, the FBP approach seems to be a more convenient and more flexible method because of the sequential processing of the projections and the easy control of image characteristics.

关键词： cone-beam CT contrast resolution exact algorithms image quality local object problem local ROI noise spatial resolution

来源：评论

学校读者我要写书评

暂无评论

Performance evaluation of local ROI algorithms for exact ROI reconstruction in spiral cone-beam computed tomography

Performance evaluation of local ROI algorithms for exact ROI...

引用

Medical Imaging Conference (MIC)

关键词： cone-beam CT contrast resolution exact algorithms image quality local object problem local ROI noise spatial resolution

来源：评论

学校读者我要写书评

暂无评论

Facility location problems: A parameterized view

引用

DISCRETE APPLIED MATHEMATICS 2011年第11期159卷 1118-1130页

作者： Fellows, Michael R. Fernau, Henning Univ Trier FB Abt Informat 4 D-54286 Trier Germany Charles Darwin Univ Darwin NT 0909 Australia

Facility location problems have been investigated in the Operations Research literature from a variety of algorithmic perspectives, including those of approximation algorithms, heuristics, and linear programming. We introduce the study of these problems from the point of view of parameterized algorithms and complexity. Some applications of algorithms for these problems in the processing of semistructured documents and in computational biology are also described. (C) 2011 Elsevier B.V. All rights reserved.

关键词： exact algorithms Parameterized algorithms NP-completeness Facility location problems Semistructured documents

来源：评论

学校读者我要写书评

暂无评论

Computing exact clustering posteriors with subset convolution

引用

COMMUNICATIONS IN STATISTICS-THEORY AND METHODS 2016年第10期45卷 3048-3058页

作者： Kohonen, Jukka Corander, Jukka Univ Helsinki Dept Math & Stat POB 68 FI-00014 Helsinki Finland

An exponential-time exact algorithm is provided for the task of clustering n items of data into k clusters. Instead of seeking one partition, posterior probabilities are computed for summary statistics: the number of clusters and pairwise co-occurrence. The method is based on subset convolution and yields the posterior distribution for the number of clusters in O(n3(n)) operations or O(n(3)2(n)) using fast subset convolution. Pairwise co-occurrence probabilities are then obtained in O(n(3)2(n)) operations. This is considerably faster than exhaustive enumeration of all partitions.

关键词： Clustering exact algorithms Subset convolution 62H30 62F15 11B13

来源：评论

学校读者我要写书评

暂无评论

THE UNIFORM MINIMUM-ONES 2SAT PROBLEM AND ITS APPLICATION TO HAPLOTYPE CLASSIFICATION

引用

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS 2010年第3期44卷 363-377页

作者： Boeckenhauer, Hans-Joachim Forisek, Michal Oravec, Jan Steffen, Bjoern Steinhoefel, Kathleen Steinova, Monika ETH Dept Comp Sci Zurich Switzerland Comenius Univ Dept Comp Sci Bratislava 81806 Slovakia Kings Coll London Dept Comp Sci London England

Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called haplotypes. In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based on the minimum-ones 2SAT problem with uniform clauses. The minimum-ones 2SAT problem asks for a satisfying assignment to a satisfiable formula in 2CNF which sets a minimum number of variables to true. This problem is well-known to be NP-hard, even in the case where all clauses are uniform, i.e., do not contain a positive and a negative literal. We analyze the approximability and present the first non-trivial exact algorithm for the uniform minimum-ones 2SAT problem with a running time of O(1.21061(n)) on a 2SAT formula with n variables. We also show that the problem is fixed-parameter tractable by showing that our algorithm can be adapted to verify in O*(2(k)) time whether an assignment with at most k true variables exists.

关键词： exact algorithms fixed-parameter algorithms minimum-ones 2SAT haplotypes

来源：评论

学校读者我要写书评

暂无评论

Quasi-polynomial algorithms for list-coloring of nearly intersecting hypergraphs

引用

THEORETICAL COMPUTER SCIENCE 2022年 902卷 64-75页

作者： Elbassioni, Khaled Khalifa Univ Sci & Technol Abu Dhabi U Arab Emirates

A hypergraph 7-t on n vertices and m edges is said to be nearly-intersecting if every edge of 7-t intersects all but at most polylogarthmically many (in m and n) other edges. Given lists of colors G(v), for each vertex v is an element of V, 7-t is said to be G-(list) colorable, if each vertex can be assigned a color from its list such that no edge in 7-t is monochromatic. We show that list-colorability for any nearly intersecting hypergraph, and lists drawn from a set of constant size, can be checked in quasi-polynomial time in m and n. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Hypergraph coloring Hypergraph dualization exact algorithms Quasi-polynomial algorithm List coloring

来源：评论

学校读者我要写书评

暂无评论

Mathematical models and decomposition methods for the multiple knapsack problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第3期274卷 886-899页

作者： Dell'Amico, Mauro Delorme, Maxence Iori, Manuel Martello, Silvano Univ Modena & Reggio Emilia DISMI Via Giovanni Amendola 2 I-42122 Reggio Emilia Italy Univ Edinburgh Sch Math James Clerk Maxwell BldgKings BldgMayfield Rd Edinburgh EH9 3JZ Midlothian Scotland Alma Mater Studiorum Univ Bologna DEI Guglielmo Marconi Viaie Risorgimento 2 I-40136 Bologna Italy

We consider the multiple knapsack problem, that calls for the optimal assignment of a set of items, each having a profit and a weight, to a set of knapsacks, each having a maximum capacity. The problem has relevant managerial implications and is known to be very difficult to solve in practice for instances of realistic size. We review the main results from the literature, including a classical mathematical model and a number of improvement techniques. We then present two new pseudo-polynomial formulations, together with specifically tailored decomposition algorithms to tackle the practical difficulty of the problem. Extensive computational experiments show the effectiveness of the proposed approaches. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Multiple knapsack problem exact algorithms Pseudo-polynomial formulations Decomposition methods

来源：评论

学校读者我要写书评

暂无评论

Color spanning objects: algorithms and hardness results

引用

DISCRETE APPLIED MATHEMATICS 2020年 280卷 14-22页

作者： Banerjee, Sandip Misra, Neeldhara Nandy, Subhas C. Indian Stat Inst Kolkata India Indian Inst Technol Gandhinagar India

In this paper, we study the SHORTEST COLOR SPANNING t- INTERVALS problem, and related generalizations, namely SMALLEST COLOR SPANNING t- SQUARES and SMALLEST COLOR SPANNING t- CIRCLES. The generic setting is the following: we are given n points in the plane (or on a line), each colored with one of k colors. For each color i we also have a demand s(i). Given a budget t, we are required to find at most t objects (for example, intervals, squares, circles, etc.) that cover at least si points of color i. Typically, the goal is to minimize the maximum perimeter or area. We provide exact algorithms for these problems for the cases of intervals, circles and squares, generalizing several known results. In the case of intervals, we provide a comprehensive understanding of the complexity landscape of the problem after taking several natural parameters into account. Given that the problem turns out to be W[1]-hard parameterized by the standard parameters, we introduce a new parameter, namely sparsity, and prove new hardness and tractability results in this context. For squares and circles, we use existing algorithms of one smallest color spanning object in order to design algorithms for getting t identical objects of minimum size whose union spans all the colors. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Color spanning sets Computational geometry Parameterized complexity exact algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：