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

EFFICIENT SOLUTION OF A STOCHASTIC SCHEDULING PROBLEM ON AN OUT-FOREST-REVISITED

SIAM JOURNAL ON OPTIMIZATION 2009年第2期20卷 903-914页

作者： Rothblum, Uriel G. Technion Israel Inst Technol IL-32000 Haifa Israel

We consider the problem of scheduling tasks subject to out-forest precedence constraints, where the tasks are identified with the edges. Initially only the tasks with no predecessors are available. At each step, an available task is selected and processed, resulting in either (a) termination, or (b) the replacement of the selected task in the available set by a random subset of its immediate successors. Also, an outcome-dependent reward is gained. The goal is to maximize the expected utility, which can be either linear or exponential. Denardo, Rothblum, and Van der Heyden [Math. Oper. Res., 29 (2004), pp. 162-181] (DRV) study a special version of the above problem. DRV use a leaf-to-stem induction to demonstrate the optimality of a priority rule and to compute it, the latter with work that is quadratic in the number of edges in the application that motivated their paper. Sethuraman and Tsitsiklis [Math. Oper. Res., 32 (2007), pp. 589-593] (ST) treat the general model and demonstrate optimality of a priority rule by employing an idea of Tsisiklis [Ann. Appl. Probab., 4 (1994), pp. 194-199] to successively eliminate nodes, from highest to lowest priority. ST report a work bound that is exponential in the size of the data. In the current paper, we adapt the leaf-to-stem methodology of DRV to show how to compute optimal priority rules for the general model, with work that is polynomial in the size of the data.

关键词： stochastic scheduling trees precedence constraints polynomial-time algorithm combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

An edge scanning method for the continuous deviation-flow refueling station location problem on a general network

引用

NETWORKS 2022年第3期79卷 264-291页

作者： Abbaas, Omar Ventura, Jose A. Penn State Univ Harold & Inge Marcus Dept Ind & Mfg Engn University Pk PA 16802 USA

This study addresses the continuous deviation-flow refueling station location problem on a general network. Instead of having a finite number of candidate locations, we consider any point in the network as a candidate location. In addition, vehicles are allowed to deviate from their prescribed (shortest) paths to refuel. At the beginning, we focus on the location of a single refueling facility, which is a relevant problem in the initial stages of development of a refueling infrastructure for alternative fuels in a transportation network. The objective is to maximize the traffic flow covered (in roundtrips per time unit). We propose an exact algorithm that determines the endpoints of all refueling segments on each edge of the network that cover the corresponding origin-destination flows. Then, the set with the best endpoints is shown to be optimal and can be used to determine the entire set of optimal locations. Network reduction rules and a network decomposition procedure are also discussed to reduce the size of the problem and improve the computational efficiency. Later, the entire set of endpoints is used in a set covering model to locate multiple refueling stations under the assumption that every vehicle only needs to refuel once on each way of the round trip. Moreover, we limit the allowed refueling deviation distance from the shortest path. Finally, a numerical example is provided to illustrate the proposed methodology.

关键词： continuous location problem edge scanning network decomposition polynomial-time algorithm refueling infrastructure transportation network

来源：评论

学校读者我要写书评

暂无评论

Constructing the Simplest Possible Phylogenetic Network from Triplets

引用

algorithmICA 2011年第2期60卷 207-235页

作者： van Iersel, Leo Kelk, Steven Univ Canterbury Dept Math & Stat Christchurch 1 New Zealand CWI NL-1090 GB Amsterdam Netherlands

A phylogenetic network is a directed acyclic graph that visualizes an evolutionary history containing so-called reticulations such as recombinations, hybridizations or lateral gene transfers. Here we consider the construction of a simplest possible phylogenetic network consistent with an input set T, where T contains at least one phylogenetic tree on three leaves (a triplet) for each combination of three taxa. To quantify the complexity of a network we consider both the total number of reticulations and the number of reticulations per biconnected component, called the level of the network. We give polynomial-time algorithms for constructing a level-1 respectively a level-2 network that contains a minimum number of reticulations and is consistent with T (if such a network exists). In addition, we show that if T is precisely equal to the set of triplets consistent with some network, then we can construct such a network with smallest possible level in time O(|T| (k+1)), if k is a fixed upper bound on the level of the network.

关键词： Phylogenetics polynomial-time algorithm Phylogenetic networks Triplets Minimising reticulations

来源：评论

学校读者我要写书评

暂无评论

SOME RESULTS CONCERNING THE COMPLEXITY OF RESTRICTED COLORINGS OF GRAPHS

引用

DISCRETE APPLIED MATHEMATICS 1992年第1期36卷 35-46页

作者： KUBALE, M Institute of Informatics Technical University of Gdańsk PL-80952 Gdańsk Poland

We consider the complexity of restricted colorings of a graph in which each vertex (or edge) receives one color from a list of permissible colors associated with that vertex (edge). Since the problem is strongly NP-complete, we assume various restrictions imposed on the number and form of permissible colors and the structure of a graph. In this way we obtain some evidence for comparing the complexity of the restricted vertex coloring problem versus that of edge coloring and arrive at a number of results about special cases that are either positive (polynomial solvability) or negative (NP-completeness proofs).

关键词： CHROMATIC INDEX CHROMATIC NUMBER NP-COMPLETENESS polynomial-time algorithm RESTRICTED COLORING

来源：评论

学校读者我要写书评

暂无评论

Coloring vertices of claw-free graphs in three colors

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2014年第2期28卷 462-479页

作者： Lozin, Vadim Purcell, Christopher Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England

We study the computational complexity of the vertex 3-colorability problem in the class of claw-free graphs. Both the problem and the class received much attention in the literature, separately of each other. However, very little is known about the 3-colorability problem restricted to the class of claw-free graphs beyond the fact the problem is NP-complete under this restriction. In this paper we first strengthen this negative fact by revealing various further restrictions under which the problem remains NP-complete. Then we derive a number of positive results that deal with polynomially solvable cases of the problem in the class of claw-free graphs.

关键词： Vertex 3-colorability Claw-free graphs NP-completeness polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Super-stability in the student-project allocation problem with ties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2022年第5期43卷 1203-1239页

作者： Olaosebikan, Sofiat Manlove, David Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland

TheStudent-Project Allocation problem with lecturer preferences over Students(spa-s) involves assigning students to projects based on student preferences over projects, lecturer preferences over students, and the maximum number of students that each project and lecturer can accommodate. This classical model assumes that each project is offered by one lecturer and that preference lists are strictly ordered. Here, we study a generalisation ofspa-swhere ties are allowed in the preference lists of students and lecturers, which we refer to as theStudent-Project Allocation problem with lecturer preferences over Students with Ties(spa-st). We investigate stable matchings under the most robust definition of stability in this context, namelysuper-stability. We describe the first polynomial-time algorithm to find a super-stable matching or to report that no such matching exists, given an instance ofspa-st. Our algorithm runs inO(L) time, whereLis the total length of all the preference lists. Finally, we present results obtained from an empirical evaluation of the linear-time algorithm based on randomly-generatedspa-stinstances. Our main finding is that, whilst super-stable matchings can be elusive when ties are present in the students' and lecturers' preference lists, the probability of such a matching existing is significantly higher if ties are restricted to the lecturers' preference lists.

关键词： Student-project allocation Stable matching Super-stability polynomial-time algorithm Empirical evaluation

来源：评论

学校读者我要写书评

暂无评论

INDEPENDENT SETS OF MAXIMUM WEIGHT IN APPLE-FREE GRAPHS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2010年第1期24卷 239-254页

作者： Brandstaedt, Andreas Lozin, Vadim V. Mosca, Raffaele Univ Rostock Inst Informat D-18051 Rostock Germany Univ Warwick DIMAP Coventry CV4 7AL W Midlands England Univ Warwick Math Inst Coventry CV4 7AL W Midlands England Univ G DAnnunzio Dipartimento Sci I-65121 Pescara Italy

We present the first polynomial-time algorithm to solve the maximum weight independent set problem for apple-free graphs, which is a common generalization of several important classes where the problem can be solved efficiently, such as claw-free graphs, chordal graphs, and cographs. Our solution is based on a combination of two algorithmic techniques (modular decomposition and decomposition by clique separators) and a deep combinatorial analysis of the structure of apple-free graphs. Our algorithm is robust in the sense that it does not require the input graph G to be apple-free;the algorithm either finds an independent set of maximum weight in G or reports that G is not apple-free.

关键词： maximum independent set clique separators modular decomposition polynomial-time algorithm claw-free graphs apple-free graphs

来源：评论

学校读者我要写书评

暂无评论

On Hamiltonicity of {claw, net }-free graphs

引用

DISCRETE MATHEMATICS 2006年第21期306卷 2755-2761页

作者： Kelmans, Alexander Univ Puerto Rico San Juan PR 00936 USA Rutgers State Univ New Brunswick NJ 08903 USA

An st-path is a path with the end-vertices s and t. An s-path is a path with an end-vertex s. The results of this paper include necessary and sufficient conditions for a (claw, net)-free graph G with s, t is an element of V(G) and e is an element of E(G) to have (1) a Hamiltonian s-path, (2) a Hamiltonian st-path, (3) a Hamiltonian s- and st-paths containing e when G has connectivity one, and (4) a Hamiltonian cycle containing e when G is 2-connected. These results imply that a connected {claw, net}-free graph has a Hamiltonian path and a 2-connected {claw, net}-free graph has a Hamiltonian cycle [D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden subgraphs and the Hamiltonian theme, in: The Theory and Application of Graphs (Kalamazoo, Mich., 1980), Wiley, New York, 198 1, pp. 297-316]. Our proofs of (1)-(4) are shorter than the proofs of their corollaries in [D. Duffus, R.J. Gould, M.S. Jacobson, Forbidden subgraphs and the Hamiltonian theme, in: The Theory and Application of Graphs (Kalamazoo, Mich., 1980), Wiley, New York, 1981, pp. 297-316], and provide polynomial-time algorithms for solving the corresponding Hamiltonicity problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： claw net graph (claw, net)-free graph Hamiltonian path Hamiltonian cycle polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Path norms on a matrix

引用

SOFT COMPUTING 2023年第11期27卷 6939-6959页

作者： Varsha Aishwarya, S. Kuncham, Syam Prasad Kedukodi, Babushri Srinivas Manipal Acad Higher Educ MAHE Manipal Inst Technol Dept Math Manipal 576104 Karnataka India

We define row path norm and column path norm of a matrix and relate path norms with other standard matrix norms. A row (resp. column) path norm gives a path that maximizes relative row (resp. column) distances starting from the first row (resp. column). The comparison takes place from the last row (resp. column) to the first row (resp. column), tracing the path. We categorize different versions of path norms and provide algorithms to compute them. We show that brute-force methods to compute path norms have exponential running time. We give dynamic programming algorithms, which, in contrast, take quadratic running time for computing the path norms. We define path norms on Church numerals and Church pairs. Finally, we present applications of path norms in computing condition number, and ordering the solutions of magic squares and Latin squares

关键词： Matrix norm Matrix seminorm Normed ring polynomial-time algorithm Church numerals

来源：评论

学校读者我要写书评

暂无评论

Constrained domatic bipartition on trees

引用

DISCRETE OPTIMIZATION 2016年第PartB期22卷 372-388页

作者： Andreatta, Giovanni De Francesco, Carla De Giovanni, Luigi Serafini, Paolo Univ Padua Dipartimento Matemat Via Trieste 63 I-35121 Padua Italy Univ Udine Dipartimento Sci Matemat Informat & Fis Viale Sci 206 I-33100 Udine Italy

Given an undirected graph, the Constrained Domatic Bipartition Problem (CDBP) consists in determining a bipartition, if it exists, of the nodes into two dominating sets, with the additional constraint that one of the two subsets has a given cardinality. The problem is NP-hard in general and in this paper we focus on trees. First, we provide explicit solutions in simple cases, i.e., stars and paths. Then, we provide a polyhedral representation for all domatic bipartitions of a tree. Although the matrix associated with the polyhedron is not totally unimodular, we prove that all its vertices have integral components. Adding the cardinality constraint, the resulting polyhedron will generally lose this property. We then propose a constructive, dynamic programming algorithm for CDBP on trees, that is able to simultaneously find a solution for all possible cardinalities. The proposed algorithm is polynomial with complexity O(n(3)), where n is the number of nodes. Finally, we discuss the extension of CDBP to the weighted case, show that it is NP-hard and provide a pdeudo-polynomial algorithm for the problem. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Dominating set Cardinality constraint Tree polynomial-time algorithm Integral polytope

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：