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

Scheduling unit-length jobs with precedence constraints of small height

OPERATIONS RESEARCH LETTERS 2014年第2期42卷 166-172页

作者： Berger, Andre Grigoriev, Alexander Heggernes, Pinar van der Zwaan, Ruben Maastricht Univ Operat Res Grp NL-6200 MD Maastricht Netherlands Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Univ Bergen Dept Informat N-5020 Bergen Norway

We consider the problem of scheduling unit-length jobs on identical machines subject to precedence constraints. We show that natural scheduling rules fail when the precedence constraints form a collection of stars or a collection of complete bipartite graphs. We prove that the problem is in fact NP-hard on collections of stars when the input is given in a compact encoding, whereas it can be solved in polynomial time with standard adjacency list encoding. On a subclass of collections of stars and on collections of complete bipartite graphs we show that the problem can be solved in polynomial time even when the input is given in compact encoding, in both cases via non-trivial algorithms. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Scheduling Precedence constraints Computational complexity polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A New Combinatorial Algorithm for Separable Convex Resource Allocation with Nested Bound Constraints

引用

INFORMS JOURNAL ON COMPUTING 2021年第3期33卷 1197-1212页

作者： Wu, Zeyang Nip, Kameng He, Qie Univ Minnesota Dept Ind & Syst Engn Minneapolis MN 55455 USA Xiamen Univ Sch Math Sci Xiamen 361005 Peoples R China

The separable convex resource allocation problem with nested bound constraints aims to allocate B units of resources to n activities to minimize a separable convex cost function, with lower and upper bounds on the total amount of resources that can be consumed by nested subsets of activities. We develop a new combinatorial algorithm to solve this model exactly. Our algorithm is capable of solving instances with millions of activities in several minutes. The running time of our algorithm is at most 73% of the running time of the current best algorithm for benchmark instances with three classes of convex objectives. The efficiency of our algorithm derives from a combination of constraint relaxation and divide and conquer based on infeasibility information. In particular, nested bound constraints are relaxed first;if the solution obtained violates some bound constraints, we show that the problem can be divided into two subproblems of the same structure and smaller sizes according to the bound constraint with the largest violation. Summary of Contribution. The resource allocation problem is a collection of optimization models with a wide range of applications in production planning, logistics, portfolio management, telecommunications, statistical surveys, and machine learning. This paper studies the resource allocation model with prescribed lower and upper bounds on the total amount of resources consumed by nested subsets of activities. These nested bound constraints are motivated by storage limits, time-window requirements, and budget constraints in various applications. The model also appears as a subproblem in models for green logistics and machine learning, and it has to be solved repeatedly. The model belongs to the class of computationally challenging convex mixed-integer nonlinear programs. We develop a combinatorial algorithm to solve this model exactly. Our algorithm is faster than the algorithm that currently has the best theoretical complexity in the literatu

关键词： resource allocation constraint relaxation divide and conquer polynomial-time algorithms mixed-integer convex optimization

来源：评论

学校读者我要写书评

暂无评论

Reconfiguring k-Path Vertex Covers

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2022年第7期E105D卷 1258-1272页

作者： Hoang, Duc A. Suzuki, Akira Yagita, Tsuyoshi Kyoto Univ Grad Sch Informat Kyoto 6068501 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan Kyushu Inst Technol Iizuka Fukuoka 8208502 Japan

A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The k-P ath V ertex C over R econfiguration (k-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of kpath vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of k-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k = 2, known as the Vertex Cover Reconfiguration (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for k-PVCR. In particular, we prove a complexity dichotomy for k-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for k-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

关键词： combinatorial reconfiguration computational complexity k-path vertex cover PSPACE-completeness polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Acyclic matching in some subclasses of graphs

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期943卷 36-49页

作者： Panda, B. S. Chaudhary, Juhi Indian Inst Technol Delhi Dept Math New Delhi India Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

A subset M subset of E of edges of a graph G = (V, E) is called a matching if no two edges of M share a common vertex. Given a matching M in G , a vertex v is an element of V is called M-saturated if there exists an edge e is an element of M incident with v. A matching M of a graph G is called an acyclic matching if, G[V (M)] , the subgraph of G induced by the M-saturated vertices of G is an acyclic graph. Given a graph G , the ACYCLIC MATCHING problem asks to find an acyclic matching of maximum cardinality in G. The DECIDE-ACYCLIC MATCHING problem takes a graph G and an integer k and asks whether G has an acyclic matching of cardinality at least k. The DECIDE-ACYCLIC MATCHING problem is known to be NP-complete for general graphs as well as for bipartite graphs. In this paper, we strengthen this result by showing that the DECIDE-ACYCLIC MATCHING problem remains NP-complete for comb-convex bipartite graphs, star-convex bipartite graphs, and dually chordal graphs. On the positive side, we show that the ACYCLIC MATCHING problem is linear time solvable for split graphs, block graphs, and proper interval graphs. We show that the ACYCLIC MATCHING problem is hard to approximate within a factor of n(1-epsilon) for any epsilon > 0 unless P = NP. Also, we show that the ACYCLIC MATCHING problem is APX-complete for (2k +1)-regular graphs for every fixed integer k >= 3. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Matching Acyclic matching Graph algorithms NP-completeness polynomial-time algorithms APX-completeness

来源：评论

学校读者我要写书评

暂无评论

NEARLY ON LINE SCHEDULING OF PREEMPTIVE INDEPENDENT TASKS

引用

DISCRETE APPLIED MATHEMATICS 1995年第2-3期57卷 229-241页

作者： SANLAVILLE, E UNIV PARIS 06 LAB LITP4 PL JUSSIEUF-75252 PARIS 05FRANCE

We discuss the problem of scheduling preemptive independent tasks, subject to release dates and due dates, on identical processors, so as to minimize the maximum lateness. This problem was solved by a polynomial flow based algorithm, but the major drawback of this approach is its off-line character. We study a priority algorithm, the equivalent of a list scheduling method in the non-preemptive case, in which tasks are ordered according to their due dates. This algorithm is nearly on-line and of low complexity. It builds an optimal schedule when the release dates are equal. In the general case, it provides an absolute performance gurantee. These results hold when the number of available machines is allowed to vary with time in a zigzag way (the number of machines is either K, or K - 1).

关键词： PARALLEL MACHINES PREEMPTIVE SCHEDULING PROFILE SCHEDULING polynomial-time algorithms PERFORMANCE GUARANTEE

来源：评论

学校读者我要写书评

暂无评论

Exact algorithms for linear programming over algebraic extensions

引用

ALGORITHMICA 2001年第4期31卷 459-478页

作者： Beling, PA Univ Virginia Dept Syst Engn Charlottesville VA 22903 USA

We study the computational complexity of linear programs with coefficients that are real algebraic numbers under a Turing machine model of computation. After reviewing a method for exact representation of algebraic numbers under the Turing model, we show that the fundamental tasks of comparison and arithmetic can be performed in polynomial time. Our technique for establishing polynomial-time algorithms for comparison and arithmetic is distinct from the usual resultant-based approaches, and has the advantage that it provides a natural framework for analysis of the complexity of computational tasks, such as Gaussian elimination, that involve a sequence of arithmetic operations. Our main contribution is to show that a variant of the ellipsoid method can be used to solve linear programming in time polynomial in the encoding size of the problem coefficients and the degree of any algebraic extension that contains those coefficients.

关键词： linear programming algebraic numbers computational complexity symbolic computation ellipsoid method polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for finding regular simple paths in outerplanar graphs

引用

JOURNAL OF algorithms 2000年第2期35卷 235-259页

作者： Nedev, ZP Wood, PT Univ Cape Town Dept Comp Sci ZA-7700 Rondebosch South Africa Kings Coll London Dept Comp Sci London WC2R 2LS England

Let G be a labeled directed graph with are labels drawn from alphabet Sigma, R be a regular expression over Sigma, and x and y be a pair of nodes from G. The regular simple path (RSP) problem is to determine whether there is a simple path p in G from x to y, such that the concatenation of are labels along p satisfies R. Although RSP is known to be NP-hard in general, we show that it is solvable in polynomial time when G is outerplanar. The proof proceeds by presenting an algorithm which gives a polynomial-time reduction of RSP for outerplanar graphs to RSP for directed acyclic graphs, a problem which has been shown to be solvable in polynomial time. (C) 2000 Academic Press.

关键词： labeled directed graphs NP-completeness polynomial-time algorithms regular expressions simple paths outerplanar graphs

来源：评论

学校读者我要写书评

暂无评论

A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions

引用

DISCRETE OPTIMIZATION 2009年第3期6卷 292-298页

作者： Huo, Yumei Leung, Joseph Y. -T. Wang, Xin New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA CUNY Dept Comp Sci Staten Isl NY 10314 USA

We consider the problem of preemptively scheduling n independent jobs on m parallel machines so as to minimize the makespan. Each job J(j) has a release time r(j) and it can only be processed on a subset of machines M-j. The machines are linearly ordered. Each job J(j) has a machine index a(j) such that M-j = {M-aj, Maj+1, ... , M-m}. We first show that there is no 1-competitive online algorithm for this problem. We then give an offline algorithm with a running time of O(nk logP + mnk(2) + m(3)k), where k is the number of distinct release times and P is the total processing time of all jobs. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Preemptive scheduling Release time Inclusive processing set Makespan minimization polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Computing the metric dimension for chain graphs

引用

INFORMATION PROCESSING LETTERS 2015年第9期115卷 671-676页

作者： Fernau, Henning Heggernes, Pinar van't Hof, Pim Meister, Daniel Saei, Reza Univ Trier Fachbereich 4 Informat Wissensch D-54286 Trier Germany Univ Bergen Dept Informat N-5020 Bergen Norway

The metric dimension of a graph G is the smallest size of a set R of vertices that can distinguish each vertex pair of G by the shortest-path distance to some vertex in R. Computing the metric dimension is NP-hard, even when restricting inputs to bipartite graphs. We present a linear-time algorithm for computing the metric dimension for chain graphs, which are bipartite graphs whose vertices can be ordered by neighborhood inclusion. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Combinatorial problems Metric dimension Adjacency metric dimension Chain graphs polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

An efficient retrieval selection algorithm for video servers with random duplicated assignment storage technique

引用

INFORMATION PROCESSING LETTERS 2002年第6期83卷 315-321页

作者： Low, CP Nanyang Technol Univ Sch Elect & Elect Engn Singapore 639798 Singapore

Random Duplicated Assignment (RDA) is an approach in which video data is stored by assigning a number of copies of each data block to different, randomly chosen disks. It has been shown that this approach results in smaller response times and lower disk and RAM costs compared to the well-known disk stripping techniques. Based on this storage approach, one has to determine, for each given batch of data blocks, from which disk each of the data blocks is to be retrieved. This is to be done in such a way that the maximum load of the disks is minimized. The problem is called the Retrieval Selection Problem (RSP). In this paper, we propose a new efficient algorithm for RSP. This algorithm is based on the breadth-first search approach and is able to guarantee optimal solutions for RSP in O(n(2) + mn), where m and n correspond to the number of data blocks and the number of disks, respectively. We will show that our proposed algorithm has a lower time complexity than an existing algorithm, called the MFS algorithm. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： random duplicated assignment breadth-first search polynomial-time algorithms load balancing algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：