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

TWO-AGENT VEHICLE SCHEDULING PROBLEM ON A LINE-SHAPED NETWORK

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2023年第7期19卷 4874-4892页

作者： Yan, Hao Liu, Peihai Lu, Xiwen East China Univ Sci & Technol Dept Math Shanghai 200237 Peoples R China

This paper studies single vehicle scheduling problems with two agents on a line-shaped network. Each of two agents has some customers that are situated at some vertices on the network. A vehicle has to start from upsilon(0) to serve all customers. The objective is to schedule the customers to minimize C-max(A) + theta C-max(B), where C-max(X) is the latest completion time of the customers for agent X and X is an element of{A,B}. We first propose a polynomial time algorithm for the problem without release time. Next, the problem with release time is proved to be NP-hard despite of a network with only two vertices. Then, we present a 3+root 5/2 -approximation algorithm. Finally, numerical experiments are carried out to verify the approximation algorithm is effective.

关键词： Agent scheduling network scheduling complexity polynomial time algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Sequencing jobs that require common resources on a single machine: A solvable case of the TSP

引用

MATHEMATICAL PROGRAMMING 1998年第1-2期82卷 235-254页

作者： van der Veen, JAA Woeginger, GJ Zhang, SZ Nijenrode Univ Netherlands Business Sch Ctr Supply Chain Management NL-3621 BG Breukelen Netherlands Graz Tech Univ Inst Math B A-8010 Graz Austria Erasmus Univ Inst Econometr NL-3000 DR Rotterdam Netherlands

In this paper a one-machine scheduling model is analyzed where n different jobs are classified into K groups depending on which additional resource they require. The change-over time from one job to another consists of the removal time or of the set-up time of the two jobs. It is sequence-dependent in the sense that the change-over time is determined by whether or not the two jobs belong to the same group. The objective is to minimize the make pan. This problem can be modeled as an asymmetric Traveling Salesman Problem (TSP) wit? a specially structured distance matrix. For this problem we give a polynomial time solution algorithm that runs in O(nlogn) time. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.

关键词： single machine scheduling Traveling Salesman Problem polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Reconstruction of interval graphs

引用

THEORETICAL COMPUTER SCIENCE 2010年第43期411卷 3859-3866页

作者： Kiyomi, Masashi Saitoh, Toshiki Uehara, Ryuhei JAIST Sch Informat Sci Nomi Ishikawa 9231292 Japan JST ERATO MINATO Discrete Struct Manipulat Syst Proje Sapporo Hokkaido 0600814 Japan

The graph reconstruction conjecture is a long-standing open problem in graph theory. There are many algorithmic studies related to it, such as DECK CHECKING, LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING. We study these algorithmic problems by limiting the graph class to interval graphs. Since we can solve GRAPH ISOMORPHISM for interval graphs in polynomial time, DECK CHECKING for interval graphs is easily done in polynomial time. Since the number of interval graphs that can be obtained from an interval graph by adding a vertex and edges incident to it can be exponentially large, developing polynomial time algorithms for LEGITIMATE DECK, PREIMAGE CONSTRUCTION, and PREIMAGE COUNTING on interval graphs is not trivial. We present that these three problems are solvable in polynomial time on interval graphs. (C) 2010 Elsevier B.V. All rights reserved.

关键词： The graph reconstruction conjecture Interval graphs polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm

引用

MATHEMATICAL PROGRAMMING 1996年第3期72卷 291-305页

作者： Muramatsu, M Tsuchiya, T INST STAT MATH MINATO KUTOKYO 106JAPAN

In this paper we give a new convergence analysis of a projective scaling algorithm. We consider a long-step affine scaling algorithm applied to a homogeneous linear programming problem obtained from the original linear programming problem. This algorithm takes a fixed lambda less than or equal to 2/3 of the way towards the boundary of the nonnegative orthant at each iteration. The iteration sequence for the original problem is obtained by pulling back the homogeneous iterates onto the original feasible region with a conical projection, which generates the same search direction as the original projective scaling algorithm at each iterate. The recent convergence results for the long-step affine scaling algorithm by the authors are applied to this algorithm to obtain some convergence results on the projective scaling algorithm. Specifically, we will show (i) polynomiality of the algorithm with complexities of O(nL) and O(n(2)L) iterations for lambda < 2/3 and lambda = 2/3, respectively;(ii) global convergence of the algorithm when the optimal face is unbounded;(iii) convergence of the primal iterates to a relative interior point of the optimal face;(iv) convergence of the dual estimates to the analytic center of the dual optimal face;and (v) convergence of the reduction rate of the objective function value to 1 - lambda.

关键词： linear programming interior point methods long-step algorithm projective scaling algorithm polynomial time algorithm convergence analysis

来源：评论

学校读者我要写书评

暂无评论

Computing a minimum paired-dominating set in strongly orderable graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 253卷 37-50页

作者： Pradhan, D. Panda, B. S. Indian Inst Technol ISM Dept Appl Math Dhanbad Bihar India Indian Inst Technol Dept Math Comp Sci & Applicat Grp Delhi India

A set D subset of V of a graph G = (V, E) is called a dominating set of G if every vertex in V \ D has at least one neighbor in D. A dominating set D of G is a paired-dominating set of G if G[D], the subgraph of G induced by D, has a perfect matching. Given a graph C, MIN-PAIRED-DOM-SET is the problem to find a paired-dominating set of G of minimum cardinality. MIN-PAIREDDOM-SET is known to be NP-hard for general graphs and many other restricted classes of graphs. However, MIN PAIRED DOM SET is solvable in polynomial time in some graph classes including strongly chordal graphs and chordal bipartite graphs. In this paper, we strengthen this result by proposing a polynomial time algorithm to compute a minimum paired-dominating set in the class of strongly orderable graphs, which includes strongly chordal graphs and chordal bipartite graphs. The algorithm runs in linear time if a quasi-simple elimination ordering of the strongly orderable graph is provided. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Domination Paired-domination Strongly orderable graphs polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Global total k-domination: Approximation and hardness results

引用

THEORETICAL COMPUTER SCIENCE 2021年 850卷 1-19页

作者： Panda, B. S. Goyal, Pooja Indian Inst Technol Delhi Dept Math New Delhi 110016 India

A subset D subset of V of a graph G = (V, E) is called a global total k-dominating set of G if D is a total k-dominating set of both G and the complement (G) over bar of G. The MINIMUM GLOBAL TOTAL k-DOMINATION problem is to find a global total k-dominating set of minimum cardinality of the input graph G and DECIDE GLOBAL TOTAL k-DOMINATION problem is the decision version of MINIMUM GLOBAL TOTAL k-DOMINATION problem. The DECIDE GLOBAL TOTAL k-DOMINATION problem is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen the NP-completeness result of DECIDE GLOBAL TOTAL k-DOMINATION problem by showing that this problem remains NP-complete for perfect elimination bipartite graphs, star-convex bipartite graphs and doubly chordal graphs. On the positive side, we give a polynomial time algorithm for the MINIMUM GLOBAL TOTAL k-DOMINATION problem for chordal bipartite graphs, which is a subclass of bipartite graphs. We propose a 2(1 +ln vertical bar V vertical bar)-approximation algorithm for the MINIMUM GLOBAL TOTAL k-DOMINATION problem for any graph. We show that MINIMUM GLOBAL TOTAL k-DOMINATION problem cannot be approximated within (1 - epsilon)ln vertical bar V vertical bar for any epsilon > 0 unless P = NP for any integer k >= 1. We further show that for bipartite graphs, MINIMUM GLOBAL TOTAL k DOMINATION problem cannot be approximated within (1/6 - c)ln vertical bar V vertical bar for any epsilon > 0 unless P = NP for any k >= 1. Finally, we show that the MINIMUM GLOBAL TOTAL k-DOMINATION problem is APX-complete for bounded degree bipartite graphs for any fixed integer k >= 1. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Domination polynomial time algorithm NP-complete APX-complete Graph algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum constellation covers: hardness, approximability and polynomial cases

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第3期41卷 603-624页

作者： Ravelo, Santiago Valdes Univ Fed Rio Grande do Sul Inst Informat Porto Alegre RS Brazil

This paper considers two graph covering problems, theMinimum Constellation Cover (CC) and theMinimum k-Split Constellation Cover (k- SCC). The input of these problems consists on a graph G = ( V, E) and a set C of stars of G, and the output is a minimum cardinality set of stars C, such that any two different stars of C are edgedisjoint and the union of the stars of C covers all edges of G. For CC, the set C must be compound by edges of G or stars of C while, for k- SCC, an integer k is given and the elements of C must be k-stars obtained by splitting stars of C. This work proves that unless P = NP, CC does not admit polynomial time |C|(O(1))-approximation algorithms and k- SCC cannot be ((1 - epsilon) ln |E|)-approximated in polynomial time, for any epsilon > 0. Additionally, approximation ratios are given for the worst feasible solutions of the problems and, for k- SCC, polynomial time approximation algorithms are proposed, achieving a (ln | E| - ln ln |E| + Theta (1)) approximation ratio. Also, polynomial time algorithms are presented for special classes of graphs that include bounded degree trees and cacti.

关键词： Exact graph cover NP-hard Inapproximability Approximation algorithm polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

An algorithm for a super-stable roommates problem

引用

THEORETICAL COMPUTER SCIENCE 2011年第50期412卷 7059-7065页

作者： Fleiner, Tamas Irving, Robert W. Manlove, David F. Budapest Univ Technol & Econ Dept Comp Sci & Informat Theory H-1117 Budapest Hungary Univ Glasgow Sch Comp Sci Glasgow G12 8QQ Lanark Scotland

In this paper, we describe an efficient algorithm that decides if a stable matching exists for a generalized stable roommates problem, where, instead of linear preferences, agents have partial preference orders on potential partners. Furthermore, we may forbid certain partnerships, that is, we are looking for a matching such that none of the matched pairs is forbidden, and yet, no blocking pair (forbidden or not) exists. To solve the above problem, we generalize the first algorithm for the ordinary stable roommates problem. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Stable marriages Stable roommates problem polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

On the approximability and exact algorithms for vector domination and related problems in graphs

引用

DISCRETE APPLIED MATHEMATICS 2013年第6期161卷 750-767页

作者： Cicalese, Ferdinando Milanic, Martin Vaccaro, Ugo Univ Salerno Dipartimento Informat I-84084 Fisciano SA Italy Univ Primorska UP IAM SI-6000 Koper Slovenia Univ Primorska UP FAMNIT SI-6000 Koper Slovenia

We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that any vertex outside S has a prescribed number of neighbors in S. In total vector domination, the requirement is extended to all vertices of the graph. We prove that these problems (and several variants thereof) cannot be approximated to within a factor of c In n, where c is a suitable constant and n is the number of the vertices, unless P=NP. We also show that two natural greedy strategies have approximation factors In Delta + 0(1), where Delta is the maximum degree of the input graph. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend, improve, and unify several results previously known in the literature. (C) 2012 Elsevier B.V. All rights reserved.

关键词： Vector domination Total vector domination alpha-domination k-domination Multiple domination Inapproximability Approximation algorithm polynomial time algorithm Trees Threshold graphs P-4-free graphs

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for NMR quantum computers with small qubits

引用

NEW GENERATION COMPUTING 2003年第4期21卷 329-337页

作者： Kunihiro, N Yamashita, S Univ Electrocommun Chofu Tokyo 1828585 Japan Nara Inst Sci & Technol Nara 6310101 Japan

The security of the RSA cryptosystems is based on the difficulty of factoring a large composite integer. In 1994, Shor showed that factoring a large composite is executable in polynomial time if we use a quantum Turing machine. Since this algorithm is complicated, straightforward implementations seem impractical judging from current technologies. In this paper, we propose simple and efficient algorithms for factoring and discrete logarithm problem based on NMR quantum computers. Our algorithms are easier to implement if we consider NMR quantum computers with small qubits.

关键词： factoring problem discrete logarithm problem NMR quantum computers counting problem polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：