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

The minimum spanning strong subdigraph problem is fixed parameter tractable

DISCRETE APPLIED MATHEMATICS 2008年第15期156卷 2924-2929页

作者： Bang-Jensen, Jorgen Yeo, Anders Univ So Denmark Dept Math & Comp Sci DK-5230 Odense Denmark Univ London Dept Comp Sci Egham TW20 0EX Surrey England

A digraph D is strong if it contains a directed path from x to y for every choice of vertices x, y in D. We consider the problem (MSSS) of finding the minimum number of arcs in a spanning strong subdigraph of a strong digraph. It is easy to see that every strong digraph D on n vertices contains a spanning strong subdigraph on at most 2n - 2 arcs. By reformulating the MSSS problem into the equivalent problem of finding the largest positive integer k <= n - 2 so that D contains a spanning strong subdigraph with at most 2n - 2 - k arcs, we obtain a problem which we prove is fixed parameter tractable. Namely, we prove that there exists an O(f(k)n(c)) algorithm for deciding whether a given strong digraph D on it vertices contains a spanning strong subdigraph with at most 2n - 2 - k arcs. We furthermore prove that if k >= 1 and D has no cut vertex then it has a kernel of order at most (2k - 1)(2). We finally discuss related problems and conjectures. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Minimum strong spanning subdigraph polynomial algorithm FTP algorithm

来源：评论

学校读者我要写书评

暂无评论

Scheduling on uniform parallel machines with periodic unavailability constraints

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2019年第1期57卷 216-227页

作者： Kaabi, Jihene Harrath, Youssef Univ Bahrain Coll Informat Technol Dept Informat Syst Zallaq Bahrain Univ Bahrain Coll Informat Technol Dept Comp Sci Zallaq Bahrain

Scheduling problems under unavailability constraints has become a popular research topic in the last few years. Despite it's important application in the real world, the uniform parallel machine scheduling problem was the least studied due to its complexity. In this paper, we investigated the uniform parallel machine scheduling problem under deterministic availability constraints. Each machine is subject to one unavailability period. Different versions of the problem regarding the type of jobs (identical and non-identical) and the performance measures (the total completion times and the makespan) were studied. For the case of identical jobs and for both performance measures, we developed linear programming models and optimal algorithms to provide a solution to the problem. For the case of non-identical jobs, we proved that the problem is NP-hard and propose a quadratic program. Because, this later cannot solve problems with very large number of jobs and machines, a heuristic was developed to find near optimal solutions to the problem especially with very large number of jobs and machines. The computational results showed that the heuristic's performance is very high regardless the dimensions of problem instances.

关键词： uniform parallel machines scheduling unavailability constraints linear programming polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

A new large-update interior point algorithm for P_*(κ) linear complementarity problems

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2008年第1期216卷 265-278页

作者： Cho, Gyeong-Mi Dongseo Univ Dept Multimedia Engn Pusan 617716 South Korea

In this paper we propose a new large-update primal-dual interior point algorithm for P-*(kappa) linear complementarity problems (LCPs). We generalize Bai et al.'s [A primal-dual interior-point method for linear optimization based on a new proximity function, Optim. Methods Software 17(2002) 985-1008] primal-dual interior point algorithm for linear optimization (LO) problem to P-* (kappa) LCPs. New search directions and proximity measures are proposed based on a kernel function which is not logarithmic barrier nor self-regular for P-* (kappa) LCPs. We showed that if a strictly feasible starting point is available, then the new large-update primal-dual interior point algorithm for solving P-*(kappa) LCPs has the polynomial complexity O((1 + 2 kappa)n(3/4) log(n/epsilon)) and gives a simple complexity analysis. This proximity function has not been used in the complexity analysis of interior point method (IPM) for P-* (kappa) LCPs before. (C) 2007 Elsevier B.V. All rights reserved.

关键词： large-update interior point method kernel function complexity polynomial algorithm linear complementarity problem

来源：评论

学校读者我要写书评

暂无评论

Quantitatively fair scheduling

引用

THEORETICAL COMPUTER SCIENCE 2012年第1期413卷 160-175页

作者： Bianco, Alessandro Faella, Marco Mogavero, Fabio Murano, Aniello Univ Naples Federico II Naples Italy

We consider finite graphs whose edges are labeled with elements, called colors, taken from a fixed finite alphabet. We study the problem of determining whether there is an infinite path where either (i) all colors occur with a fixed asymptotic frequency, or (ii) there is a constant that bounds the difference between the occurrences of any two colors for all prefixes of the path. These properties can be viewed as quantitative refinements of the classical notion of fair path in a concurrent system, whose simplest form checks whether all colors occur infinitely often. Our notions provide stronger criteria, particularly suitable for scheduling applications based on a coarse-grained model of the jobs involved. In particular, they enforce a given set of priorities among the jobs involved in the system. We show that both problems we address are solvable in polynomial time, by reducing them to the feasibility of a linear program. We also consider two-player games played on finite colored graphs where the goal is one of the above frequency-related properties. For all the goals, we show that the problem of checking whether there exists a winning strategy is Co-NP-complete. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Fairness polynomial algorithm Game Scheduling Edge-colored graphs Linear programming

来源：评论

学校读者我要写书评

暂无评论

Equilibria in Nonantagonistic Positional Games on Graphs and Searching for Them

引用

AUTOMATION AND REMOTE CONTROL 2018年第2期79卷 360-365页

作者： Bashlaeva, I. A. Volgograd State Univ Volgograd Russia

We distinguish some cases of existence of a stationary equilibrium in nonantagonistic games on directed graphs with terminal payoffs along trajectories. The proof of the existence of stationary equilibria implies poly... 详细信息

关键词： positional games stationary Nash equilibria Cournot acyclicity polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing the maximum bump cost in linear extensions of a poset

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第3期26卷 509-519页

作者： Wu, Biao Liu, Longcheng Yao, Enyu Zhejiang Univ Dept Math Hangzhou 310027 Peoples R China Xiamen Univ Sch Math Sci Xiamen 361005 Peoples R China

A linear extension of a poset P=(X,a parts per thousand(0)) is a permutation x (1),x (2),aEuro broken vertical bar,x (|X|) of X such that i < j whenever x (i) a parts per thousand(0)x (j) . For a given poset P=(X,a parts per thousand(0)) and a cost function c(x,y) defined on XxX, we want to find a linear extension of P such that maximum cost is as small as possible. For the general case, it is NP-complete. In this paper we consider the linear extension problem with the assumption that c(x,y)=0 whenever x and y are incomparable. First, we prove the discussed problem is polynomially solvable for a special poset. And then, we present a polynomial algorithm to obtain an approximate solution.

关键词： Poset Linear extension polynomial algorithm Optimization

来源：评论

学校读者我要写书评

暂无评论

Flight rescheduling responding to large-area flight delays

引用

KYBERNETES 2012年第10期41卷 1483-1496页

作者： Gao, Mingang Chi, Hong Xu, Baoguang Ding, Ruo Chinese Acad Sci Res Ctr Overall Planning Safety & Secur Managemen Inst Policy & Management Beijing Peoples R China

Purpose - The purpose of this paper is to focus on disruption management responding to large-area flight delays (LFD). It is urgent for airways to reschedule the disrupted flights so as to relieve the negative influence and minimize losses. The authors try to reduce the risk of airline company's credit and economic losses by rescheduling flights with mathematic models and algorithm. Design/methodology/approach - Based on flight classifications of real-time statuses and priority indicators, all flights are prioritized. In this paper, two mathematic programming models of flight rescheduling are proposed. For the second model, an optimum polynomial algorithm is designed. Findings - In practice, when LFD happens, it is very important for the airline company to pay attention to real-time statuses of all the flights. At the same time, the disruption management should consider not only the economic loss but also other non-quantitative loss such as passengers' satisfaction, etc. Originality/value - In this paper, two mathematic programming models of flight rescheduling are built. An algorithm is designed and it is proved to be an optimum polynomial algorithm and a case study is given to illustrate the algorithm. The paper provides a theory support for airways to reduce the risk brought by LFD.

关键词： Airlines Operations management Risk management Programming and algorithm theory Aviation safety Large-area flight delays Flight status Priority Flight rescheduling Mathematic programming model polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Sets of nonnegative matrices without positive products

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2012年第3期437卷 749-765页

作者： Protasov, V. Yu. Voynov, A. S. Moscow MV Lomonosov State Univ Dept Mech & Math Moscow 119992 Russia

For an arbitrary irreducible set of nonnegative d x d-matrices, we consider the following problem: does there exist a strictly positive product (with repetitions permitted) of those matrices? Under some general assumptions, we prove that if it does not exist, then there is a partition of the set of basis vectors of R-d, on which all given matrices act as permutations. Moreover, there always exists a unique maximal partition (with the maximal number of parts) possessing this property, and the number of parts is expressed by eigenvalues of matrices. This generalizes well-known results of Perron-Frobenius theory on primitivity of one matrix to families of matrices. We present a polynomial algorithm to decide the existence of a positive product for a given finite set of matrices and to build the maximal partition. Similar results are obtained for scrambling products. Applications to the study of Lyapunov exponents, inhomogeneous Markov chains. etc. are discussed. (C) 2012 Published by Elsevier Inc.

关键词： Nonnegative matrix Primitivity Multiplicative semigroup Partition Permutation Scrambling matrix polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimizing the total completion time in a unit-time open shop with release times

引用

OPERATIONS RESEARCH LETTERS 1997年第5期20卷 207-212页

作者： Tautenhahn, T Woeginger, GJ Technische Universit&auml t Graz Institut f&uuml r Mathematik B Steyrergasse 30 A-8010 Graz Austria

We consider the problem of minimizing the total completion time in a unit-time open shop with release times where the number of machines is constant. Brucker and Kramer (1994) proved that this problem is solvable in polynomial time. However, the time complexity of the algorithm presented there is a polynom of a very high degree and, thus, the algorithm is not practicable even for a small number of machines. We give an O(n(2)) algorithm for the considered problem which is based on dynamic programming. The result is applied to solve a previously open problem with a special resource constraint raised by De Werra et al. (1991). (C) 1997 Elsevier Science B.V.

关键词： open-shop scheduling polynomial algorithm dynamic programming

来源：评论

学校读者我要写书评

暂无评论

OPTIMAL LOOP STORAGE-ALLOCATION FOR ARGUMENT-FETCHING DATA-FLOW MACHINES

引用

INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING 1992年第6期21卷 421-448页

作者： NING, Q GAO, GR CTR RECH INFORMAT MONTREAL MONTREALPQCANADA MCGILL UNIV SCH COMP SCIMONTREAL H3A 2T5QUEBECCANADA

In this paper, we consider the optimal loop scheduling and minimum storage allocation problems based on the argument-fetching dataflow architecture model. Under the argument-fetching model, the result generated by a node is stored in a unique location which is addressable by its successors. The main contribution of this paper includes: for loops containing no loop-carried dependences, we prove that the problem of allocating minimum storage required to support rate-optimal loop scheduling can be solved in polynomial time. The polynomial time algorithm is based on the fact that the constraint matrix in the formulation is totally unimodular. Since the instruction processing unit of an argument-fetching dataflow architecture is very much like a conventional processor architecture without a program counter, the solution of the optimal loop storage allocation problem for the former will also be useful for the latter.

关键词： DATA-FLOW ARCHITECTURE LOOP SCHEDULING STORAGE ALLOCATION polynomial algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：