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

Single-Machine Due-Window Assignment and Scheduling with Learning Effect and Resource-Dependent Processing times

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2014年第5期31卷 1450036-1450036页

作者： Wang, Ji-Bo Wang, Ming-Zheng Shenyang Aerosp Univ Sch Sci Shenyang 110136 Peoples R China Xi An Jiao Tong Univ State Key Lab Mfg Syst Engn Xian 710053 Peoples R China Dalian Univ Technol Sch Management Sci & Engn Dalian 116024 Peoples R China

We consider a single-machine common due-window assignment scheduling problem, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The window location and size, along with the associated job schedule that minimizes a certain cost function, are to be determined. This function is made up of costs associated with the window location, window size, earliness, and tardiness. For two different processing time functions, we provide a polynomial time algorithm to find the optimal job sequence and resource allocation, respectively.

关键词： Scheduling learning effect single-machine resource allocation due-window polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Minimum s-t hypercut in (s,t)-planar hypergraphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2024年第5期48卷

作者： Hassanpour, Abolfazl Aman, Massoud Ebrahimi, Alireza Univ Birjand Fac Sci Dept Math Birjand Iran Yazd Univ Fac Math Sci Yazd Iran

Planar hypergraphs are widely used in several applications, including VLSI design, metro maps, information visualisation, and databases. The minimum s - t hyper- cut problem in a weighted hypergraph is to find a partition of the vertices into two nonempty sets, S and S, with s is an element of S and t is an element of S(sic) that minimizes the total weight of hyperedges that have at least two endpoints in two different sets. In the present study, we propose an approach that effectively solves the minimum s-t hypercut problem in (s , t)-planar hypergraphs. The method proposed demonstrates polynomial time complexity, providing a significant advancement in solving this problem. The modelling example shows that the proposed strategy is effective at obtaining balanced bipartitions in VLSI circuits.

关键词： Planar hypergraph Shortest path polynomial time algorithm VLSI circuits Planar hypergraph Minimum s - t hypercut Maximum s - t flow Shortest path polynomial time algorithm VLSI circuits

来源：评论

学校读者我要写书评

暂无评论

Parallel-Machine Scheduling with Step-Deteriorating Jobs to Minimize the Total (Weighted) Completion time

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第1期40卷

作者： Miao, Cuixia Kong, Fanyu Zou, Juan Ma, Ran Huo, Yujia Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China Qingdao Univ Technol Sch Management Engn Qingdao 266525 Peoples R China Univ Res Ctr Smart City Construct & Management Shandong Prov Qingdao 266525 Peoples R China

In this paper, we consider the parallel-machine scheduling with step-deteriorating jobs. The actual processing time of each job deteriorates as a step function if its starting time is beyond a given deteriorating date. We focus on the case of the common job deteriorating date. For the minimization problem of total completion time, we first show that the problem is NP-hard in the strong sense. Then we propose one property of any optimal schedule. Furthermore, we prove that two special cases of common normal processing time or common penalty are polynomially solvable. For the minimization problem of total weighted completion time, we analyze the NP-hardness and present a polynomial time optimal algorithm for the case of common normal processing time and common penalty.

关键词： Scheduling step-deteriorating strongly NP-hard polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Weak Three-Linking in Eulerian Dgraphs

引用

SIAM Journal on Discrete Mathematics 1991年第1期4卷 84-98页

作者： T. Ibaraki S. Poljak

Let G be an Eulerian digraph, and a,b,ca,b,ca,b,c an ordered triple of its vertices. A polynomial time algorithm of <span class="MathJax" id="MathJax-Element-2-Frame" tabindex="0" styl... 详细信息

Let G be an Eulerian digraph, and

a, b, c

$a,b,c$ an ordered triple of its vertices. A polynomial time algorithm of

05C20 05C38 05C45 90B10 Eulerian digraph disjoint paths planar graph polynomial time algorithm weak three-linking

来源：评论

学校读者我要写书评

暂无评论

Constrained flows in networks

引用

THEORETICAL COMPUTER SCIENCE 2024年 1010卷

作者： Bang-Jensen, J. Bessy, S. Picasarri-Arrieta, L. Univ Southern Denmark Dept Math & Comp Sci Odense Denmark Univ Montpellier LIRMM CNRS Montpellier France Univ Cote Azur CNRS I3S Inria Sophia Antipolis France

The support of a flow x in a network is the subdigraph induced by the arcs uv for which x(uv) > 0. We discuss a number of results on flows in networks where we put certain restrictions on structure of the support of the flow. Many of these problems are NP-hard because they generalize linkage problems for digraphs. For example deciding whether a network N = (D. s, t, c) has a maximum flow x such that the maximum out-degree of the support D-x of x is at most 2 is NP-complete as it contains the 2-linkage problem as a very special case. Another problem which is NP-complete for the same reason is that of computing the maximum flow we can send from s to t along p paths (called a maximum p-path-flow) in N. Baier et al. (2005) gave a polynomial time algorithm which finds a-path-flow x whose value is at least 2/3 of the value of a optimum p-path-flow when p is an element of{2, 3}, and at least 1/2 when p >= 4. When p = 2, they show that this is best possible unless P=NP. We show for each p >= 2 that the value of a maximum p-path-flow cannot be approximated by any ratio larger than 9/11, unless P=NP. We also consider a variant of the problem where the p paths must be disjoint. For this problem, we give an algorithm which gets within a factor 1/H(p) of the optimum solution, where H(p) is the p'th harmonic number (H(p) similar to ln(p)). We show that in the case where the network is acyclic, we can find such a maximum p-path-flow in polynomial time for every p. We determine the complexity of a number of related problems concerning the structure of flows. For the special case of acyclic digraphs, some of the results we obtain are in some sense best possible.

关键词： Flows (Arc-)disjoint paths with prescribed end vertices Acyclic digraph polynomial time algorithm NP-complete problem Approximation algorithm Parameterised complexity

来源：评论

学校读者我要写书评

暂无评论

Near optimal colourability on hereditary graph families

引用

THEORETICAL COMPUTER SCIENCE 2024年 993卷

作者： Ju, Yiao Huang, Shenwei Nankai Univ Coll Comp Sci Tianjin 300350 Peoples R China Nankai Univ Tianjin Key Lab Network & Data Secur Technol Tianjin 300071 Peoples R China

In this paper, we initiate a systematic study on a new notion called near optimal colourability which is closely related to perfect graphs and the Lovasz theta function. A graph family G is near optimal colourable if there is a constant number c such that every graph G is an element of G satisfies chi(G) <= max{c, omega(G)}, where chi (G) and omega(G) are the chromatic number and clique number of G, respectively. The near optimal colourable graph families together with the Lovasz theta function are useful for the study of the colouring problems for hereditary graph families. We investigate the near optimal colourability for (H, H-2)-free graphs. Our main result is an almost complete characterisation for the near optimal colourability for (H, H-2)-free graphs with two exceptional cases, one of which is the celebrated Gyarfas conjecture. As an application of our results, we show that the colouring problem for (2K(2), P-4 v K-n)-free graphs is polynomial time solvable, which solves an open problem in Dabrowski and Paulusma (2018) [6].

关键词： Graph colouring Lovasz theta function polynomial time algorithm Forbidden induced subgraphs

来源：评论

学校读者我要写书评

暂无评论

An algorithm for node-to-node disjoint paths problem in burnt pancake graphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2007年第1期E90D卷 306-313页

作者： Kaneko, Keiichi Sawada, Naoki Tokyo Univ Agr & Technol Grad Sch Engn Koganei Tokyo 1848588 Japan

In this paper, we propose an algorithm that solves the node-to-node disjoint paths problem in n-burnt pancake graphs in polynomial-order time of n. We also give a proof of its correctness as well as the estimates of time complexity O(n(3)) and the maximum path length 3n + 4. We conducted a computer experiment for n = 2 to 100 to measure the average performance of our algorithm. The results show that the average time complexity is O(n(3.0)) and the maximum path length is 3n + 4.

关键词： burnt pancake graphs node-to-node disjoint paths problem container problem internally disjoint paths polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Combining decomposition approaches for the Maximum Weight Stable Set problem

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期960卷

作者： Brandstaedt, Andreas Mosca, Raffaele Univ Rostock Inst Informat D-18051 Rostock Germany Univ G DAnnunzio Dipartimento Econ I-65121 Pescara Italy

The Maximum Weight Stable Set Problem (MWS) is a well-known NP-hard problem. A popular way to study MWS is to detect graph classes for which MWS can be solved in polynomial time. In this context some decomposition approaches have been introduced in the literature, in particular decomposition by homogeneous sets and decomposition by clique separators, which had several applications in the literature. Brandstadt and Hoang (2007) [6] showed how to combine such two decomposition approaches and stated the following result: If the MWS problem can be solved in polynomial time for every subgraph of a graph G which has no homogeneous set and has no clique separators then so can the problem for G. This result, namely Corollary 9 of [6], was used in various papers. Unfortunately, it was stated in a successive paper by Brandstadt and Giakoumakis (2015) [5] that "Actually, [6] does not give a proof for this, and it seems that Corollary 9 of [6] promises too much;later attempts for proving it failed, and thus, it is unproven and its use has to be avoided." This manuscript introduces a proof of Corollary 9 of [6]. Furthermore a third decomposition approach, namely decomposition by anti-neighborhoods of vertices, is combined together with such two decomposition approaches. Then the various papers in which Corollary 9 of [6] was used would be fixed.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Maximum Weight Independent Set problem polynomial time algorithm Decomposition by homogeneous sets Decomposition by clique separators Decomposition by anti-neighborhood of vertices

来源：评论

学校读者我要写书评

暂无评论

Optimal resilient sensor placement problem for secure state estimation

引用

AUTOMATICA 2024年 160卷

作者： Shinohara, Takumi Namerikawa, Toru Keio Univ Grad Sch Sci & Technol 3-14-1 HiyoshiKohoku Ku Yokohama Kanagawa 2238522 Japan Keio Univ Dept Syst Design Engn 3-14-1 HiyoshiKohoku Ku Yokohama Kanagawa 2238522 Japan

In this paper, we consider a sensor placement problem for secure state estimation in an adversarial environment. Specifically, this paper deals with a system consisting of n agents where up to l sensor measurements are potentially compromised by malicious adversaries and tackles the problem of sensor placement such that the system state can be reconstructed even if the measurements are compromised. However, since it is costly to deploy sensors for all agents, we also aim to place sensors at the lowest possible cost. We call this problem the optimal resilient sensor placement problem (ORSPP) and show that this problem is coNP-hard. Therefore, it is, in general, impossible to compute the ORSPP in polynomial time unless P = coNP. On the positive side, however, we also provide that this problem can be solved in polynomial time if the network structure of the agents satisfies certain conditions. The concrete algorithm for the ORSPP is provided, and further, in the process of providing the coNP-hardness, we also derive a new form of a necessary and sufficient condition for secure state estimation. Finally, we show the results of numerical simulations using a random graph and a diffusion process.(c) 2023 Elsevier Ltd. All rights reserved.

关键词： Secure state estimation Optimal sensor placement Eigenvalue and sparse observability polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

FAST APPROXIMATION algorithmS FOR KNAPSACK AND SUM OF SUBSET PROBLEMS

引用

JOURNAL OF THE ACM 1975年第4期22卷 463-468页

作者： IBARRA, OH KIM, CE UNIV MINNESOTA DEPT COMP INFORMATION & CONTROL SCI114 MAIN ENGN BLDGMINNEAPOLISMN 55455

Given a positive integer M and n pairs of positive integers [formula omitted], maximize the [formula omitted] subject to the constramts [formula omitted] and δi = 0 or 1 This is the well-known 0/1 knapsack problem An... 详细信息

Given a positive integer M and n pairs of positive integers [formula omitted], maximize the [formula omitted] subject to the constramts [formula omitted] and δ_i = 0 or 1 This is the well-known 0/1 knapsack problem An algorithm is presented which finds for any 0 < ϵ < 1 an approximate solution P satisfying [formula omitted] is the desired optimal sum Moreover, for any fixed ϵ, the algorithm has time complexity O(n log n) and space complexity O(n) Modification of the algorithm for the unbounded knapsack problem where the δ_i's can be any nonnegative integer results in a O(n) computing time A hnear-time algorithm is also obtained for a special class of 0/1 knapsack problems having the property that p_i/c_i is the same for all 1 ≤ i ≤ n. © 1975, ACM. All rights reserved.

关键词： approximation algorithm knapsack problem P-complete problem polynomial time algorithm sum of subset problem

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：