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

Min-Max Scheduling of Batch or Drop-Line Jobs Under Agreeable Release and Processing times

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2022年第2期39卷 2150023-2150023页

作者： Gao, Yuan Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China Zhengzhou Univ Sch Informat Engn Zhengzhou 450001 Henan Peoples R China

We study the Pareto optimization scheduling on an unbounded parallel-batch machine with jobs having agreeable release dates and processing times for minimizing makespan and maximum cost simultaneously. The jobs considered in this paper are of two types: batch jobs and drop-line jobs. For batch jobs, the completion time of a job is given by the completion time of the batch containing this job. For drop-line jobs, the completion time of a job is given by the starting time of the batch containing this job plus the processing time of this job. For both of batch jobs and drop-line jobs, we present polynomial-time algorithms for finding all Pareto optimal points.

关键词： Parallel-batch scheduling release dates pareto optimization polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

(Strong) conflict-free connectivity: algorithm and complexity

引用

THEORETICAL COMPUTER SCIENCE 2020年 804卷 72-80页

作者： Ji, Meng Li, Xueliang Zhu, Xiaoyu Nankai Univ Ctr Combinator Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China

Let G be an(a) edge(vertex)-colored graph. A path P of G is called a conflict-free path if there is a color that is used on exactly one of the edges(vertices) of P. The graph G is called conflict-free (vertex-)connected if any two distinct vertices of G are connected by a conflict-free path, whereas the graph G is called strongly conflict-free connected if any two distinct vertices u, v of G are connected by a conflict-free path of length of a shortest path between u and v in G. For a connected graph G, the (strong)conflict-free connection number of G, denoted by (scfc(G)) cf c(G), is defined as the smallest number of colors that are required to make G (strongly) conflict-free connected. In this paper, we first investigate the question: Given a connected graph G and a coloring c : E(or V) ->{1, 2, ..., k} (k >= 1) of G, determine whether or not G is, respectively, conflict-free connected, conflict-free vertexconnected, strongly conflict-free connected under the coloring c. We solve this question by providing polynomial-time algorithms. We then show that the problem of deciding whether scfc(G) <= k (k >= 2) for a given graph G is NP-complete. Moreover, we prove that it is NP-complete to decide whether there is a k-edge-coloring (k >= 2) of G such that all pairs (u, v) is an element of P (P subset of V x V) are strongly conflict-free connected. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Conflict-free connection polynomial-time algorithm Strong conflict-free connection Complexity

来源：评论

学校读者我要写书评

暂无评论

Polymatching algorithm in observational studies with multiple treatment groups

引用

COMPUTATIONAL STATISTICS & DATA ANALYSIS 2022年 167卷 107364-107364页

作者： Nattino, Giovanni Song, Chi Lu, Bo Ist Ric Farmacol Mario Negri IRCCS Via GB Camozzi 3 I-24020 Ranica BG Italy Ohio State Univ Div Biostat Coll Publ Hlth 1841 Neil Ave Columbus OH 43210 USA

Matched designs are commonly used in non-randomized studies to evaluate causal effects for dichotomous treatment. Optimal matching algorithms have been devised to form matched pairs or sets between treatment and control groups in various designs, including 1-k matching and full matching. With multiple treatment arms, however, the optimal matching problem cannot be solved in polynomial-time. This is a major challenge for implementing matched designs with multiple arms, which are important for evaluating causal effects with different dose levels or constructing evidence factors with multiple control groups. A polymatching framework for generating matched sets among multiple groups is proposed. An iterative multi-way algorithm for implementation is developed, which takes advantage of the existing optimal two-group matching algorithm repeatedly. An upper bound for the total distance attained by our algorithm is provided to show that the distance result is close to the optimal solution. Simulation studies are conducted to compare the proposed algorithm with the nearest neighbor algorithm under different scenarios. The algorithm is also used to construct a difference-in-difference matched design among four groups, to examine the impact of Medicaid expansion on the health status of Ohioans. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Polymatching Multiple treatment groups polynomial-time algorithm Causal inference Difference-in-difference

来源：评论

学校读者我要写书评

暂无评论

An algorithm for reconstructing level-2 phylogenetic networks from trinets

引用

INFORMATION PROCESSING LETTERS 2022年 178卷

作者： van Iersel, Leo Kole, Sjors Moulton, Vincent Nipius, Leonie Delft Univ Technol Delft Inst Appl Math Mekelweg 4 NL-2628CD Delft Netherlands Univ East Anglia Sch Comp Sci Norwich NR4 7TJ Norfolk England

Evolutionary histories for species that cross with one another or exchange genetic material can be represented by leaf-labelled, directed graphs called phylogenetic networks. A major challenge in the burgeoning area of phylogenetic networks is to develop algorithms for building such networks by amalgamating small networks into a single large network. The level of a phylogenetic network is a measure of its deviation from being a tree;the higher the level of a network, the less treelike it becomes. Various algorithms have been developed for building level-1 networks from small networks. However, level-1 networks may not be able to capture the complexity of some data sets. In this paper, we present a polynomial-time algorithm for constructing a rooted binary level-2 phylogenetic network from a collection of 3-leaf networks or trinets. Moreover, we prove that the algorithm will correctly reconstruct such a network if it is given all of the trinets in the network as input. The algorithm runs in time O (t middot n + n4) with t the number of input trinets and n the number of leaves. We also show that there is a fundamental obstruction to constructing level-3 networks from trinets, and so new approaches will need to be developed for constructing level-3 and higher level-networks.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Directed graph Phylogenetic network polynomial-time algorithm Subnetworks Graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Single Track Transportation in a Two-Machine Production System

引用

IFAC-PapersOnLine 2022年第10期55卷 2893-2897页

作者： Yakov Zinder Alexander Lazarev Elena Musatova University of Technology Sydney Australia V.A. Trapeznikov Institute of Control Science of Russian Academy of Sciences Moscow Russia

The paper is concerned with scheduling traffic on a single track between two stations which generate requests for transportation with different release times. These requests are served by a fleet of identical vehicles, each of which can serve (carry) several requests for transportation simultaneously. The single track, used by the vehicles, does not permit traffic in both directions simultaneously. The presented polynomial-time algorithms are based on dynamic programming.

关键词： Scheduling dynamic programming single track polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Rescheduling Traffic on a Partially Blocked Segment of Railway with a Siding

引用

AUTOMATION AND REMOTE CONTROL 2020年第6期81卷 955-966页

作者： Zinder, Y. Lazarev, A. A. Musatova, E. G. Univ Technol Sydney NSW Australia Russian Acad Sci Trapeznikov Inst Control Sci Moscow Russia Natl Res Univ Higher Sch Econ Moscow Russia

The paper presents a polynomial-time algorithm for rescheduling traffic when one track of a double-track railway becomes unavailable, the remaining track has a siding, and there are two categories of trains-priority trains such as passenger trains and ordinary trains such as the majority of freight trains. The presented algorithm minimises the negative effect, caused by the track blockage, first for the priority trains and then for the ordinary trains on the set of all schedules optimal for the priority trains.

关键词： single-track railway dynamic programming rescheduling polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

Characterizing Star-PCGs

引用

algorithmICA 2020年第10期82卷 3066-3090页

作者： Xiao, Mingyu Nagamochi, Hiroshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto Japan

A graph G is called a pairwise compatibility graph (PCG, for short) if it admits a tuple (T, w, d min, d max) of a tree T whose leaf set is equal to the vertex set of G, a non-negative edge weight w, and two non-negative reals d min = d max such that G has an edge between two vertices u, v. V if and only if the distance between the two leaves u and v in the weighted tree (T, w) is in the interval [d min, d max]. The tree T is also called a witness tree of the PCG G. How to recognize PCGs is a wide-open problem in the literature. This paper gives a complete characterization for a graph to be a star-PCG (a PCG that admits a star as its witness tree), which provides us the first polynomial-time algorithm for recognizing star-PCGs.

关键词： Pairwise compatibility graph polynomial-time algorithm Graph algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

An improved formulation and efficient heuristics for the discrete parallel-machine makespan ScheLoc problem

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 140卷 106238-106238页

作者： Wang, Shijin Wu, Ruochen Chu, Feng Yu, Jianbo Liu, Xin Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China Univ Paris Saclay Univ Evry Lab IBISC F-91025 Evry France Fuzhou Univ Sch Econ & Management Fuzhou 350116 Peoples R China Tongji Univ Sch Mech Engn Shanghai 200092 Peoples R China Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China

The scheduling-location (ScheLoc) problem is a new and interesting field, which is a combination of two complex problems: the machine-location problem and the scheduling problem. Owing to the NP-hardness of both the component problems, the ScheLoc problem is naturally NP-hard. This study investigates a deterministic and discrete parallel-machine ScheLoc problem for minimizing the makespan. A new mixed integer programming formulation based on network flow problems is proposed. Two formulation-based heuristics are developed for small-scale problems. Subsequently, a polynomial-time heuristic is designed for efficiently solving large-scale problems. Extensive computational experiments are conducted for 1450 benchmark problem instances with different scales. The computational results show that our model can solve more problem instances to optimality than that in Healer and Deghdak (2017) in the same time limit. In addition, the heuristics can yield near-optimal solutions for small-scale problems in a short time. The polynomial-time algorithm outperforms most of the state-of-the-art methods for the large-scale problems in terms of both the efficiency and solution quality.

关键词： Scheduling-location (ScheLoc) problem Discrete location Mixed integer programming formulation polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

SUBSET SELECTION IN SPARSE MATRICES

引用

SIAM JOURNAL ON OPTIMIZATION 2020年第2期30卷 1173-1190页

作者： Del Pia, Alberto Dey, Santanu S. Weismantel, Robert Univ Wisconsin Dept Ind & Syst Engn Madison WI 53706 USA Univ Wisconsin Wisconsin Inst Discovery Madison WI 53706 USA Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA Swiss Fed Inst Technol Dept Math CH-8092 Zurich Switzerland

In subset selection we search for the best linear predictor that involves a small subset of variables. From a computational complexity viewpoint, subset selection is NP-hard and few classes are known to be solvable in polynomial time. Using mainly tools from discrete geometry, we show that some sparsity conditions on the original data matrix allow us to solve the problem in polynomial time.

关键词： subset selection linear least squares polynomial-time algorithm sparsity

来源：评论

学校读者我要写书评

暂无评论

Connected Vertex Cover for (sP1 + P5)-Free Graphs

引用

algorithmICA 2020年第1期82卷 20-40页

作者： Johnson, Matthew Paesani, Giacomo Paulusma, Daniel Univ Durham Dept Comp Sci Durham England

The Connected Vertex Cover problem is to decide if a graph G has a vertex cover of size at most k that induces a connected subgraph of G. This is a well-studied problem, known to be NP-complete for restricted graph classes, and, in particular, for H-free graphs if H is not a linear forest. On the other hand, the problem is known to be polynomial-time solvable for sP(2)-free graphs for any integer s >= 1. We give a polynomial-time algorithm to solve the problem for (sP(1)+P-5)-free graphs for every integer s >= 0. Our algorithm can also be used for the WEIGHTED CONNECTED VERTEX COVER problem.

关键词： Vertex cover Connected vertex cover H-free graph polynomial-time algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：