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

exact algorithms for the Equitable Traveling Salesman Problem

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2017年第2期261卷 475-485页

作者： Kinable, Joris Smeulders, Bart Delcour, Eline Spieksma, Frits C. R. Carnegie Mellon Univ Robot Inst 5000 Forbes Ave Pittsburgh PA 15213 USA Carnegie Mellon Univ Tepper Sch Business 5000 Forbes Ave Pittsburgh PA 15213 USA Katholieke Univ Leuven Dept Comp Sci CODeS Gebroeders De Smetstr 1 B-9000 Ghent Belgium Katholieke Univ Leuven IMinds ITEC Gebroeders De Smetstr 1 B-9000 Ghent Belgium Univ Liege HEC Management Sch QuantOM Rue Louvrex 14 B-4000 Liege Belgium Barry Callebaut Aalstersestr 122 B-9280 Lebbeke Belgium Katholieke Univ Leuven Fac Business & Econ ORSTAT Naamsestr 69 B-3000 Leuven Belgium

Given a weighted graph G = (V, E), the Equitable Traveling Salesman Problem (ETSP) asks for two perfect matchings in G such that (1) the two matchings together form a Hamiltonian cycle in G and (2) the absolute difference in costs between the two matchings is minimized. The problem is shown to be NP Hard, even when the graph G is complete. We present two integer programming models to solve the ETSP problem and compare the strength of these formulations. One model is solved through branch-and cut, whereas the other model is solved through a branch-and-price framework. A simple local search heuristic is also implemented. We conduct computational experiments on different types of instances, often derived from the TSPLib. It turns out that the behavior of the different approaches varies with the type of instances. For small and medium sized instances, branch-and-bound and branch-and-price produce comparable results. However, for larger instances branch-and-bound outperforms branch-and price. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Traveling Salesman Problem Branch-and-bound Branch-and-price exact algorithms

来源：评论

学校读者我要写书评

暂无评论

On exact algorithms for single-machine scheduling problems with a variable maintenance

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2017年 107卷 276-279页

作者： Wang, Qi Liu, Aihua Xiao, Junfang East China Univ Technol Sch Sci Nanchang 330013 Jiangxi Peoples R China

The aim of this paper is to point out that all mathematical programming models proposed by Ying et al. (2016) are incorrect. We present four revised mathematical programming models and four improved mathematical programming models by adding and revising some constraints and decision variables. Moreover, we show that the first three scheduling problems considered in their paper are equivalent to the problems with the objective of minimizing the sum of completion times or minimizing the maximum lateness, which can be solved by algorithms proposed by Luo et al. (2015) in O(n(2)) time. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Scheduling Variable maintenance exact algorithms

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for single-machine scheduling problems with a variable maintenance

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2016年第0期98卷 427-433页

作者： Ying, Kuo-Ching Lu, Chung-Cheng Chen, Jhao-Cheng Natl Taipei Univ Technol Dept Ind Engn & Management Taipei Taiwan Natl Chiao Tung Univ Dept Transportat & Logist Management Hsinchu Taiwan

This paper deals with four single-machine scheduling problems (SMSPs) with a variable machine maintenance. The objectives of the four SMSPs are to minimize mean lateness, maximum tardiness, total flow time and mean tardiness, respectively. These four SMSPs are important in the literature and in practice. This study proposes an exact algorithm with the computational complexity O(n(2)) for each of the four SMSPs. In addition to the given jobs, the machine maintenance activity between two consecutive jobs is optimally scheduled. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： Scheduling Variable maintenance exact algorithms

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Intervalizing Coloured Graphs

引用

THEORY OF COMPUTING SYSTEMS 2016年第2期58卷 273-286页

作者： Bodlaender, Hans L. van Rooij, Johan M. M. Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Eindhoven Univ Technol Dept Math & Comp Sci POB 513 NL-5600 MB Eindhoven Netherlands Consultants Qualitat Methods POB 414 NL-5600 AK Eindhoven Netherlands

In the INTERVALIZING COLOURED GRAPHS problem, one must decide for a given graph G = (V, E) with a proper vertex colouring of G whether G is the subgraph of a properly coloured interval graph. For the case that the number of colors is fixed, we give an exact algorithm that uses 2(O(n/log n)) time. We also give an O*(2(n)) algorithm for the case that the number of colors is not fixed.

关键词： Graph algorithms exact algorithms Interval graphs Subexponential time Intervalizing coloured graphs Pathwidth

来源：评论

学校读者我要写书评

暂无评论

Bin packing and cutting stock problems: Mathematical models and exact algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2016年第1期255卷 1-20页

作者： Delorme, Maxence Iori, Manuel Martello, Silvano Alma Mater Studiorum Univ Bologna DEI Guglielmo Marconi Viale Risorgimento 2 I-40136 Bologna Italy Univ Modena & Reggio Emilia DISMI Via Giovanni Amendola 2 I-42122 Reggio Emilia Italy

We review the most important mathematical models and algorithms developed for the exact solution of the one-dimensional bin packing and cutting stock problems, and experimentally evaluate, on state-of-the art computer... 详细信息

关键词： Bin packing Cutting stock exact algorithms Computational evaluation

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for Kayles

引用

THEORETICAL COMPUTER SCIENCE 2015年第C期562卷 165-176页

作者： Bodlaender, Hans L. Kratsch, Dieter Timmer, Sjoerd T. Univ Utrecht NL-3508 TB Utrecht Netherlands Univ Lorraine Metz LITA F-57045 Metz 01 France

In the game of KAYLES, two players select alternatingly a vertex from a given graph G, but may never choose a vertex that is adjacent or equal to an already chosen vertex. The last player that can select a vertex wins the game. In this paper, we give an exact algorithm to determine which player has a winning strategy in this game. To analyze the running time of the algorithm, we introduce the notion of a K-set: a nonempty set of vertices W subset of V is a K-set in a graph G = (V, E), if G[W] is connected and there exists an independent set X such that W = V - N[X]. The running time of the algorithm is bounded by a polynomial factor times the number of K-sets in G. We prove that the number of K-sets in a graph with n vertices is bounded by O(1.6052(n)). A computer-generated case analysis improves this bound to O(1.6031(n)) K-sets, and thus we have an upper bound of O(1.6031(n)) on the running time of the algorithm for KAYLES. We also show that the number of K-sets in a tree is bounded by n center dot 3(n/3) and thus KAYLEs can be solved on trees in O(1.4423(n)) time. We show that apart from a polynomial factor, the number of K-sets in a tree is sharp. As corollaries, we obtain that determining which player has a winning strategy in the games G(avoid)(POSDNF2) and G(seek)(POSDNF3) can also be determined in O(1.6031(n)) time. In G(avoid)(POSDNF2), we have a positive formula F on n Boolean variables in Disjunctive Normal Form with two variables per clause. Initially, all variables are false, and players alternately set a variable from false to true;the first player that makes F true loses the game. The game G(seek)(POSDNF3) is similar, but now there are three variables per clause, and the first player that makes F true wins the game. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Graph algorithms exact algorithms Combinatorial games Analysis of algorithms Moderately exponential time algorithms Kayles Independent sets

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for dominating induced matching based on graph partition

引用

DISCRETE APPLIED MATHEMATICS 2015年 190卷 147-162页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 611731 Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Sakyo Ku Kyoto 6068501 Japan

A dominating induced matching, also called an efficient edge domination, of a graph G = (V, E) with n = vertical bar V vertical bar vertices and m = vertical bar E vertical bar edges is a subset F subset of E of edges in the graph such that no two edges in F share a common endpoint and each edge in E \ F is incident with exactly one edge in F. It is NP-hard to decide whether a graph admits a dominating induced matching or not. In this paper, we design a 1.1467(n)n(0(1)) -time exact algorithm for this problem, improving all previous results. This problem can be redefined as a partition problem that is to partition the vertex set of a graph into two parts I and F, where I induces an independent set (a 0-regular graph) and F induces a perfect matching (a 1-regular graph), After giving several structural properties of the problem, we show that the problem always contains some "good vertices," branching on which by including them to either I or F we can effectively reduce the graph. This leads to a fast exact algorithm to this problem. (C) 2015 Elsevier B.V. All rights reserved.

关键词： exact algorithms Graph algorithms Graph partition Branch-and-reduce Dominating induced matching

来源：评论

学校读者我要写书评

暂无评论

Resolution-exact algorithms for Link Robots 11th

Resolution-Exact Algorithms for Link Robots

引用

11th Workshop on Algorithmic Foundations of Robotics (WAFR)

作者： Luo, Zhongdi Chiang, Yi-Jen Lien, Jyh-Ming Yap, Chee NYU Dept Comp Sci New York NY USA NYU Dept Comp Sci & Engn Brooklyn NY USA George Mason Univ Dept Comp Sci Fairfax VA 22030 USA

ISBN: (纸本)9783319165950;9783319165943

Motion planning is a major topic in robotics. Divergent paths have been taken by practical roboticists and theoretical motion planners. Our goal is to produce algorithms that are practical and have strong theoretical guarantees. Recently, we have proposed a subdivision approach based on soft predicates Wang, C., Chiang, Y.-J., Yap, C.: On soft predicates in subdivision motion planning. In: 29th ACM Symposium on Computational Geometry (SoCG'13), pp. 349-358 (2013). To appear CGTA, Special Issue for SoCG' 13 [20], but with a new notion of correctness called resolution-exactness. Unlike mos ques for planar link robots. The technical contributions of this paper are the design of soft predicates for link robots, a novel "T/R splitting method" for subdivision, and feature-based search strategies. The T/R idea is to give primacy to the translational (T) components, and perform splitting of rotational components (R) only at the leaves of a subdivision tree. We implemented our algorithm for a 2-link robot with 4 degrees of freedom (DOFs). Our implementation achieves real-time performance on a variety of nontrivial scenarios. For comparison, our method outperforms sampling-based methods significantly. We extend our 2-link planner to thick link robots with little impact on performance. Note that there are no known exact algorithms for thick link robots.

关键词： exact algorithms Subdivision algorithms Motion planning Soft predicates Resolution-exact algorithms Link robots

来源：评论

学校读者我要写书评

暂无评论

On the exact quantum query complexity of MOD and exact functions

引用

Frontiers of Computer Science 2025年第4期19卷 91-98页

作者： Penghui YAO Zekun YE State Key Laboratory for Novel Software Technology Nanjing UniversityNanjing 210023China Hefei National Laboratory Hefei 230088China

In this paper,we consider the exact quantum query complexity of two fundamental symmetric functions.1)MOD_(m)^(n),which calculates the Hamming weight of an-bit string modulo;2)exact_(k,l)^(n),which determines if the Hamming weight of an-bit string is exactly k or *** these two symmetric functions have received considerable attention,their exact quantum query complexities have not been fully ***,our results are as follows:1)We design an optimal quantum query algorithm to compute MOD_(m)^(n)exactly and thus provide a tight characterization of its exact quantum query complexity,which settles a previous *** on this algorithm,we demonstrate that a broad class of symmetric functions is not evasive in the quantum model,i.e.,there exist quantum algorithms to compute these functions exactly when the number of queries is less than their input size.2)By proposing a quantum algorithm that utilizes the minimum number of queries to compute exact_(k,l)^(n)exactly for some specific values of k and l,we give a tight characterization of its exact quantum query complexity in these scenarios.

关键词： quantum computing query complexity symmetric functions exact algorithms evasiveness

来源：评论

学校读者我要写书评

暂无评论

A model-based algorithm for the Probabilistic Orienteering Problem

引用

COMPUTERS & OPERATIONS RESEARCH 2025年 176卷

作者： Montemanni, Roberto Smith, Derek H. Univ Modena & Reggio Emilia Dept Sci & Methods Engn Via Amendola 2 I-42122 Reggio Emilia Italy Univ South Wales Comp & Math Pontypridd CF37 1DL Wales

The Orienteering Problem is a routing problem aiming at selecting a subset of a given set of customers to visited within a given time budget, so that a total revenue is maximized. Multiple variants of the problem have been studied. The Probabilistic Orienteering Problem is one of these variants, where customers will require visit according to a certain given probability. Stochasticity makes the model more practical, but concurrently more difficult to solve. Effective approaches to solve the problem potentially lead to higher quality planning in real-life logistics, thanks to the exploitation of the probabilistic informations that can normally be derived from historical data. In this paper we present an iterative model-based algorithm that solves a sequence of deterministic problems and is able to retrieve and certify optimal solutions if run for sufficient time. Experimental results show that the new approach is performing well when compared against both the exact (proven optimality) and heuristic (high quality solutions) algorithms available in the literature.

关键词： Probabilistic Orienteering Problem Heuristic algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：