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

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

来源：评论

学校读者我要写书评

暂无评论

polynomial time algorithms to Minimize Total Travel time in a Two-Depot Automated Storage/Retrieval System

引用

TRANSPORTATION SCIENCE 2017年第1期51卷 19-33页

作者： Gharehgozli, Amir Hossein Yu, Yugang Zhang, Xiandong de Koster, Rene Erasmus Univ Rotterdam Sch Management NL-3062 PA Rotterdam Netherlands Univ Sci & Technol China Sch Management Hefei 230026 Peoples R China Fudan Univ Sch Management Dept Management Sci Shanghai 200433 Peoples R China Texas A&M Univ Dept Maritime Adm Galveston TX 77554 USA

We sequence storage and retrieval jobs to minimize total travel time of a storage/retrieval (S/R) machine in a two-depot automated storage/retrieval system. These systems include storage systems with aisle-captive S/R machines and storage blocks with bridge cranes. The S/R machine must move retrieval unit loads from their current locations in the system to one of the two depots. In addition, it must move storage unit loads from given depots to given locations in the system. We model the problem as an asymmetric traveling salesman problem, which is in general NP-hard. We develop an algorithm to solve the problem in polynomial time, using the property that the system has two depots and the S/R machine always returns to one of the depots to pick up or deliver a load. Furthermore, we develop additional polynomial time algorithms for the following four special cases: (1) retrieval loads have to be delivered to given depots;(2) the system has one input depot and one output depot;(3) the system has a single depot;and (4) there are arbitrary S/R machine starting and ending locations. The computational results show the effectiveness of the proposed algorithms. Compared to first-come-first-served and nearest neighbor algorithms, commonly used in practice, the total travel time reduces on average by more than 30% and 15%, respectively.

关键词： automated storage and retrieval system two depots total travel time traveling salesman problem polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Routing and Scheduling Problems with Two Agents on a Line-Shaped Network 1

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

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

ISBN: (数字)9783030926816

ISBN: (纸本)9783030926816;9783030926809

We consider routing and scheduling problems with two agents on a line-shaped network in this paper. There are two agents and each agent has some jobs which are located in the network. Let L = (V, E) be a line-shaped network, where V = {v(0)} boolean OR V-A boolean OR V-B is the set of n + 1 vertices and E is a set of edges. A job v is located at some vertex v, which is also denoted as v. The travel time d(u, v) is associated with each edge {u, v} is an element of E. The vehicle starts from an initial vertex v(0) is an element of V and visits all jobs for their processing. The objective is to find a route of the vehicle that minimizes the completion time of agent A under the constraint condition that the completion time of agent B is no more than the threshold value Q. We express this problem as line - 1 vertical bar C-max(B) <= Q vertical bar C-max(A). For the problem without release time, an O(n) time algorithm is provided. For the problem with release time, we show that this problem is NP-hard even though there is only one job in agent B and the jobs in agent A have no release time. Finally we give a (3, 3)-approximation algorithm for the before general problem.

关键词： Network scheduling Agent scheduling polynomial time algorithm Approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the computational complexity of the secure state-reconstruction problem

引用

AUTOMATICA 2022年 136卷 110083-110083页

作者： Mao, Yanwen Mitra, Aritra Sundaram, Shreyas Tabuada, Paulo Univ Calif Los Angeles Dept Elect & Comp Engn Los Angeles CA 90095 USA Univ Penn Dept Elect & Syst Engn Philadelphia PA 19104 USA Purdue Univ Sch Elect & Comp Engn W Lafayette IN 47907 USA

In this paper, we discuss the computational complexity of reconstructing the state of a linear system from sensor measurements that have been corrupted by an adversary. The first result establishes that the problem is, in general, NP-hard. We then introduce the notion of eigenvalue observability and show that the state can be reconstructed in polynomial time when each eigenvalue is observable by at least 2s + 1 sensors and at most s sensors are corrupted by an adversary. However, there is a gap between eigenvalue observability and the possibility of reconstructing the state despite attacks - this gap has been characterized in the literature by the notion of sparse observability. To better understand this, we show that when the A matrix of the linear system has unitary geometric multiplicity, the gap disappears, i.e., eigenvalue observability coincides with sparse observability, and there exists a polynomial time algorithm to reconstruct the state provided the state can be reconstructed. (C) 2021 Elsevier Ltd. All rights reserved.

关键词： Resilient state secure state-reconstruction Eigenvalue and sparse observability polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal standalone data center renewable power supply using an offline optimization approach

引用

SUSTAINABLE COMPUTING-INFORMATICS & SYSTEMS 2022年 34卷

作者： Landre, Damien Nicod, Jean-Marc Varnier, Christophe Univ Bourgogne Franche Comte UFC CNRS ENSMMFEMTO ST Inst Besancon France

Because of the increasing energy consumption of data centers and their CO2 emissions, the ANR DATAZERO2 project aims to design autonomous data centers running solely on local renewable energy coupled with storage devices to overcome the intermittency issue. In order to optimize the use of renewable energy and storage devices, a MILP solver is usually in charge of assigning the power to be supplied to the data center. However, in order to reduce the computation time and make the approach scalable, it would be more appropriate to use a polynomial time algorithm. This paper aims at showing and proving that it is possible to provide an optimal power profile via a deterministic algorithm using a binary search approach. Considering the main constraints of the initial problem, numerous experimental results show similar results to those given by the MILP. These promising results encourage us to continue in this direction for proposing an efficient management of the data center power supply that takes uncertainty into account.

关键词： Green data center Renewable energy Power management strategy Operational research polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Capacitated Partial Inverse Maximum Spanning Tree Under the Weighted l_∞-norm 15th

Capacitated Partial Inverse Maximum Spanning Tree Under the ...

引用

15th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Li, Xianyue Yang, Ruowang Zhang, Heping Zhang, Zhao Lanzhou Univ Sch Math & Stat Lanzhou 730000 Gansu Peoples R China Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China

ISBN: (纸本)9783030926816;9783030926809

Given an edge weighted graph, and an acyclic edge set, the goal of the partial inverse maximum spanning tree problem is to modify the weight function as small as possible such that there exists a maximum spanning tree with respect to the new weight function containing the given edge set. In this paper, we consider this problem with capacitated constraint under the weighted l(infinity)-norm. By studying the properties of the optimal value and a special kind of optimal solutions, combining the algorithm for the decision version of this problem with the Binary search method, we present a strongly polynomial-time algorithm for calculating the optimal value and an optimal solution.

关键词： Partial inverse problem Spanning tree polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

Bicriteria scheduling of equal length jobs on uniform parallel machines

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第3期39卷 637-661页

作者： Zhao, Qiulan Yuan, Jinjiang Nanjing Univ Dept Math Nanjing 210093 Jiangsu Peoples R China Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

We study the bicriteria scheduling of equal length jobs on uniform parallel machines. By introducing a new scheduling model, called single-machine scheduling with generated completion times (shortly, GCT-scheduling), we show that the scheduling of equal length jobs on uniform parallel machines can be polynomially transformed into the single-machine GCT-scheduling with a special setting of generated completion times. In the GCT-scheduling, a sequence of completion times is given in advance and the job scheduled at the i-th position will be assigned the i-th completion time. We present a comprehensive study on the complexities of the bicriteria single-machine GCT-scheduling problems with respect to various regular criteria. We then turn these complexity results into the forms of bicriteria scheduling of equal length jobs on uniform (or identical) parallel machines. Our research generalizes the existing results on bicriteria scheduling of equal length jobs in the literature. Particularly, one of our results solves the open problem posed by Sarin and Prakash (J Comb Optim 8:227-240, 2004), which asks for minimizing the total weighted completion time subject to the optimality of minimizing the total number of tardy jobs on identical parallel machines, and we show that this problem is solvable in polynomial time.

关键词： Bicriteria scheduling Uniform parallel machines Generated completion times polynomial time algorithm NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Complexity of the Maximum k-Path Vertex Cover Problem

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2020年第10期E103A卷 1193-1201页

作者： Miyano, Eiji Saitoh, Toshiki Uehara, Ryuhei Yagita, Tsuyoshi van der Zanden, Tom C. Kyushu Inst Technol Iizuka Fukuoka 8208502 Japan Japan Adv Inst Sci & Technol Nomi 9231292 Japan Maastricht Univ Minderbroedersberg 4-6 NL-6211 LK Maastricht Netherlands

This paper introduces the maximization version of the kpath vertex cover problem, called theM aximum k-P ath V ertex C over problem (MaxP(k)VC for short): A path consisting of k vertices, i.e., a path of length k 1 is called a k-path. If a k-path P-k includes a vertex v in a vertex set S, then we say that v or S covers P-k. Given a graph G = (V;E) and an integer s, the goal of MaxP(k)VC is to find a vertex subset S subset of V of at most s vertices such that the number of k-paths covered by S is maximized. The problem MaxP(k)VC is generally NP-hard. In this paper we consider the tractability/intractability of MaxP(k)VC on subclasses of graphs. We prove that MaxP(3)VC remains NP-hard even for split graphs. Furthermore, if the input graph is restricted to graphs with constant bounded treewidth, then MaxP(3)VC can be solved in polynomial time.

关键词： Maximum k-path vertex cover NP-hardness polynomial time algorithm split graphs bounded treewidth

来源：评论

学校读者我要写书评

暂无评论

A polynomial time Exact algorithm for Overlay-Resistant Self-Aligned Double Patterning (SADP) Layout Decomposition

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2013年第8期32卷 1228-1239页

作者： Xiao, Zigang Du, Yuelin Zhang, Hongbo Wong, Martin D. F. Univ Illinois Dept Elect & Comp Engn Urbana IL 61801 USA Synopsys Inc Hillsboro OR 97124 USA

Double patterning lithography (DPL) technologies have become a must for today's sub-32 nm technology nodes. Currently, there are two leading DPL technologies: self-aligned double patterning (SADP) and litho-etch-litho-etch (LELE). Among them, SADP has the significant advantage over LELE in its ability to avoid overlay, making it the likely DPL candidate for the next technology node of 14 nm. In any DPL technology, layout decomposition is the key problem. While the layout decomposition problem for LELE has been well studied in the literature, only a few attempts have been made to address the SADP layout decomposition problem. In this paper, we present a polynomial time exact (optimal) algorithm to determine if a given layout has SADP decompositions that do not have any overlay at specified critical edges. The previous approaches tried to minimize the total overlay of a given layout, which may be a problematic objective. Furthermore, all previous exact algorithms were computationally expensive exponential time algorithms based on SAT or ILP. Other previous algorithms for the problem were heuristics without having any guarantee that an overlay-free solution can be found even if one exists.

关键词： Computer-aided design design for manufacturability electronic design automation layout decomposition polynomial time algorithm self-aligned double patterning

来源：评论

学校读者我要写书评

暂无评论

Dominating induced matchings in S1,2,4-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2020年 278卷 83-92页

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

Let G = (V, E) be a finite undirected graph without loops and multiple edges. A subset M subset of E of edges is a dominating induced matching (d.i.m.) in G if every edge in E is intersected by exactly one edge of M. In particular, this means that M is an induced matching, and every edge not in M shares exactly one vertex with an edge in M. Clearly, not every graph has a d.i.m. The Dominating Induced Matching (DIM) problem asks for the existence of a d.i.m. in G;this problem is also known as the Efficient Edge Domination problem;it is the Efficient Domination problem for line graphs. The DIM problem is NP-complete in general, and even for very restricted graph classes such as planar bipartite graphs with maximum degree 3. However, DIM is solvable in polynomial time for claw-free (i.e., S-1,S-1,S-1-free) graphs, for S-1,S-2,S-3-free graphs, for S-2,S-2,S-2-free graphs as well as for S-2,S-2,S-3-free graphs, in linear time for P-7-free graphs, and in polynomial time for P-8-free graphs (P-k is a special case of S-i,S-j,S-l). In a paper by Hertz, Lozin, Ries, Zamaraev and de Werra, it was conjectured that DIM is solvable in polynomial time for S-i,S-j,S-k-free graphs for every fixed i, j, k. In this paper, combining two distinct approaches, we solve it in polynomial time for S-1,S-2,S-4-free graphs which generalizes the S-1,S-2,S-3-free as well as the P7-free case. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Dominating induced matching Efficient edge domination S-1,S-2,S-4-free graphs polynomial time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：