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

Sex-Equal Stable Matchings: Complexity and exact algorithms

ALGORITHMICA 2014年第3期68卷 545-570页

作者： McDermid, Eric Irving, Robert W. 21CT Austin TX 78730 USA Univ Glasgow Sch Comp Sci Glasgow G12 8QQ Lanark Scotland

We explore the complexity and exact computation of a variant of the classical stable marriage problem in which we seek matchings that are not only stable, but are also "fair" in a formal sense. In particular, we study the sex-equal stable marriage problem (SESM), in which, roughly speaking, we wish to find a stable matching with the property that the men's happiness is as close as possible to the women's happiness. This problem is known to be strongly NP-hard (Kato in Jpn. J. Ind. Appl. Math. 10:1-19, 1993). We specifically consider SESM instances in which the preference lists of the men and/or women are bounded in length by a constant. On the negative side, we show that SESM is NP-hard, even if both the men's and women's preference lists are of length at most three, and is not even in the class XP when parameterized by the objective value of the solution. This strengthens the NP-hardness results of Kato (Jpn. J. Ind. Appl. Math. 10:1-19, 1993). On the positive side, we show that our hardness result is "tight" by giving a polynomial-time algorithm for the case in which the preference lists on one side (say the men) are of length at most two, and the lengths of the lists on the other side (the women) are unbounded. Furthermore, we give a low-order exponential-time algorithm for SESM in which the preference lists on one side are of length at most l (and the lengths of the lists on the other side are unbounded). In particular, for every pair of constants and there is an algorithm with running time bounded by . Hence, if I mu is chosen to be a sufficiently small constant, the running time is in O (a

关键词： exact algorithms XP Series-parallel graphs Induced planar subgraphs Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

引用

JOURNAL OF GLOBAL OPTIMIZATION 2022年第3期84卷 687-714页

作者： Li, Jianping Wang, Wencheng Lichen, Junran Liu, Suding Pan, Pengxiang Yunnan Univ Dept Math East Outer Ring South Rd Kunming 650504 Yunnan Peoples R China Chinese Acad Sci Acad Math & Syst Sci Inst Appl Math 55 Zhongguancun East Rd Beijing 100190 Peoples R China Beijing Univ Chem Technol Sch Math & Phys 15 North Third Ring East Rd Beijing 100029 Peoples R China

In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Given a set X = (r(1), r(2),...,r(n)} of n terminals in R-2, a demand function d : X -> N and a positive integer C, we are asked to determine the location of a line l and a Steiner tree T-l to interconnect these n terminals in X and at least one point located on this line l such that the total demand of terminals in each maximal subtree (of TO connected to the line l, where the terminals in such maximal subtree are all located at the same side of this line l, does not exceed the bound C. The objective is to minimize total weight Sigma(e is an element of Tl) w(e) of such a Steiner tree T-l among all line-capacitated Steiner trees mentioned-above, where weight w(e) = 0 if two endpoints of that edge e is an element of T-l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge e is an element of T-l . In addition, when this line l is as an input in R-2 and Sigma(r is an element of X) d(r) <= C holds, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem, for short). We obtain three main results. (1) Given a rho(st )-approximation algorithm to solve the Euclidean minimum Steiner tree problem and a rho(1Lf)-approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a (rho(st)rho(1Lf )+2)-approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal r is an element of X is less than c/2, we provide a (rho(1Lf) + 2)-approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal r is an element of X is at least c/2, using the Edmonds' algorithm to solve the minimum weight perfect matching as a subroutine, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem.

关键词： Combinatorial optimization Locations of lines Line-capacitated Steiner trees Approximation algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

A Refined Branching Algorithm for the Maximum Satisfiability Problem

引用

ALGORITHMICA 2022年第4期84卷 982-1006页

作者： Li, Wenjun Xu, Chao Yang, Yongjie Chen, Jianer Wang, Jianxin Changsha Univ Sci & Technol Hunan Prov Key Lab Intelligent Proc Big Data Tran Changsha Peoples R China Saarland Univ Fac Human & Business Sci Chair Econ Theory Saarbrucken Germany Texas A&M Univ Dept Comp Sci & Engn College Stn TX USA Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China

The MAXIMUM SATISFIABILITY problem (MAXSAT) is a fundamental NP-hard problem which has significant applications in many areas. Based on refined observations, we derive a branching algorithm of running time O*(1.2989(m)) for the MAXSAT problem, where m denotes the number of clauses in the given CNF formula. Our algorithm considerably improves the previous best result O*(1.3248(m)) published in 2004. For our purpose, we derive improved branching strategies for variables of degrees 3, 4, and 5. The worst case of our branching algorithm is at certain degree-4 variables. To serve the branching rules, we also propose a variety of reduction rules which can be exhaustively applied in polynomial time.

关键词： Maximum satisfiability Branching algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Research on Optimization of Postal Logistics Distribution Driven by Operations Research algorithms: A Case Study and Comparative Analysis 24

Research on Optimization of Postal Logistics Distribution Dr...

引用

6th International Conference on Management Science and Industrial Engineering, MSIE 2024

作者： Feng, Yicheng Gao, Benhe Li, Menghan Zhu, Guowei Shenzhen International Graduate School Tsinghua University China China Academy of Industrial Internet China

ISBN: (纸本)9798400717130

Based on the vehicle distribution optimization problem with time window in postal logistics, this paper intends to apply various operations research optimization algorithms such as exact algorithms, tabu search algorithm, genetic-simulated annealing algorithm, etc., to optimize a postal delivery network in Guangzhou, China. It employs suitable delivery cost models and programming implementation. The effectiveness of heuristic algorithms is validated using standard instances, followed by further solving of real-world problems using both exact and heuristic algorithms. By comparing the original delivery schemes with the newly proposed solutions, improvement suggestions are provided for the postal delivery network. The research shows that the improved Genetic-Metropolis algorithm can effectively obtain the optimal distribution scheme, and the vehicle travel distance can be greatly reduced compared with that before the improvement, so as to reduce the cost of the transportation process. This paper innovatively introduces the idea of large-scale neighborhood search and simulated annealing to improve the genetic algorithm, which is used to solve the optimization model of mail truck path, but also presents the optimization results more intuitively through the visualization technology of location data. © 2024 Owner/Author.

关键词： exact algorithms

来源：评论

学校读者我要写书评

暂无评论

K-adaptability in stochastic optimization

引用

MATHEMATICAL PROGRAMMING 2022年第1-2期196卷 567-595页

作者： Malaguti, Enrico Monaci, Michele Pruente, Jonas Univ Bologna DEI Guglielmo Marconi Viale Risorgimento 2 I-40136 Bologna Italy TU Dortmund Fak Math Vogelpothsweg 87 D-44227 Dortmund Germany

We consider stochastic problems in which both the objective function and the feasible set are affected by uncertainty. We address these problems using a K-adaptability approach, in which K solutions for a given problem are computed before the uncertainty dissolves and afterwards the best of them can be chosen for the realized scenario. We analyze the complexity of the resulting problem from a theoretical viewpoint, showing that, even in case the deterministic problem can be solved in polynomial time, deciding if a feasible solution exists is NP-hard for discrete probability distributions. Besides that, we prove that an approximation factor for the underlying problem can be carried over to our problem. Finally, we present exact approaches including a branch-and-price algorithm. An extensive computational analysis compares the performances of the proposed algorithms on a large set of randomly generated instances.

关键词： Stochastic programming K-adaptability exact algorithms Branch-and-price Computational experiments

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for scheduling equal-length jobs with processing set restrictions on uniform parallel batch machines

引用

MATHEMATICAL BIOSCIENCES AND ENGINEERING 2022年第11期19卷 10731-10740页

作者： Li, Shuguang Shandong Technol & Business Univ Sch Comp Sci & Technol Yantai 264005 Peoples R China

We consider the problem of scheduling jobs with equal lengths on uniform parallel batch machines with non-identical capacities where each job can only be processed on a specified subset of machines called its processing set. For the case of equal release times, we give efficient exact algorithms for various objective functions. For the case of unequal release times, we give efficient exact algorithms for minimizing makespan.

关键词： scheduling uniform parallel batch machines processing set restrictions equal job lengths exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient Production Scheduling by Exploiting Repetitive Product Configurations 21

Efficient Production Scheduling by Exploiting Repetitive Pro...

引用

IEEE 21st International Conference on Industrial Informatics (INDIN)

作者： Gruettemeier, Niels Balzereit, Kaja Soni, Nehal Bunte, Andreas Fraunhofer IOSB INA Lemgo Germany

ISBN: (纸本)9781665493130

We consider the problem of scheduling production jobs on a single machine with sequence dependent family setup times and individual job deadlines. Given a set of jobs, the goal is to minimize the total time to process all jobs while every job meets its deadline. We study algorithms that compute an exact solution to the problem. Motivated by one example use case, we exploit a natural structural observation that occurs in many production settings: the number of product configurations may be significantly smaller than the total number of jobs. We identify an algorithm that is efficient in this setting in terms of performance. We experimentally evaluate its running time and compare it with two other natural approaches of exact job scheduling.

关键词： scheduling NP-hard problem exact algorithms experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

Quantifying Instance Hardness of Protein Folding within the HP-model 20

Quantifying Instance Hardness of Protein Folding within the ...

引用

20th IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (IEEE CIBCB)

作者： van Eck, Okke van den Berg, Daan Vrije Univ Amsterdam Netherlands

ISBN: (纸本)9798350310177

NP-hard problems are infamous for having highly varying and extreme runtimes for different problem instances. This study quantifies the instance hardness of NP-hard protein folding problem instances within the HP-model. A custom dataset is generated, consisting of 1000 problem instances of lengths 10, 15, 20, and 25, totalling to 4000 instances. The computational costs for solving a problem instance using a depth-first branch and bound algorithm are measured. The resulting hardness distributions can all be characterized by a probit function regardless of the corresponding protein length. Knowing the instance hardness distribution makes it possible to extrapolate the range of expected runtimes for larger problem instances. As a result, it allows for a prediction before folding a protein.

关键词： quantifying instance hardness empirical hardness model instance hardness distribution NP-hard exact algorithms protein folding HP-model

来源：评论

学校读者我要写书评

暂无评论

Moderate exponential-time algorithms for scheduling problems

引用

4OR-A QUARTERLY JOURNAL OF OPERATIONS RESEARCH 2022年第4期20卷 533-566页

作者： T'kindt, Vincent Della Croce, Federico Liedloff, Mathieu Univ Tours Lab Informat Fondamentale & Appl LIFAT EA 6300 ERL CNRS 7002ROOT 64 Ave Jean Portalis F-37200 Tours France Politecn Torino DIGEP Corso Duca Abruzzi 24 I-10129 Turin Italy Univ Orleans Lab Informat Fondamentale Orleans LIFO EA 4022 Rue Leonard de VinciBP 6759 F-45067 Orleans 2 France CNR IEIIT Turin Italy

This survey investigates the field of moderate exponential-time algorithms for NP-hard scheduling problems, i.e., exact algorithms whose worst-case time complexity is moderately exponential with respect to brute force algorithms. Scheduling problems are very challenging problems for which interesting results have emerged in the literature since 2010. We will provide a comprehensive overview of the known results of these problems before detailing three general techniques to derive moderate exponential-time algorithms. These techniques are Sort&Search, Inclusion-Exclusion and Branching. In the last part of this survey, we will focus on side topics such as approximation in moderate exponential time, the design of lower bounds on worst-case time complexities or fixed-parameter tractability. We will also discuss the potential benefits of moderate exponential-time algorithms for efficiently solving in practice scheduling problems.

关键词： Scheduling theory exact algorithms Complexity

来源：评论

学校读者我要写书评

暂无评论

Solving Euclidean Max-Sum problems exactly with cutting planes

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 168卷

作者： Bui, Hoa T. Spiers, Sandy Loxton, Ryan Curtin Univ ARC Training Ctr Transforming Maintenance Data Sci Perth Australia Curtin Univ Curtin Ctr Optimisat & Decis Sci Perth Australia

This paper studies binary quadratic programs in which the objective is defined by the maximisation of a Euclidean distance matrix, subject to a general polyhedral constraint set. This class of nonconcave maximisation problems, which we refer to as the Euclidean Max -Sum problem, includes the capacitated, generalised and maxsum diversity problems as special cases. Due to the nonconcave objective, traditional cutting plane algorithms are not guaranteed to converge globally. In this paper, we introduce two exact cutting plane algorithms to address this limitation. The new algorithms remove the need for a concave reformulation, which is known to significantly slow down convergence. We establish exactness of the new algorithms by examining the concavity of the quadratic objective in a given direction, a concept we refer to as directional concavity . Numerical results show that the algorithms outperform other exact methods for benchmark diversity problems (capacitated, generalised and max -sum), and can easily solve problems of up to three thousand variables.

关键词： Euclidean distance matrix Cutting plane methods Constrained diversity sum exact algorithms Nonlinear binary optimisation

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：