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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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 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

来源：评论

学校读者我要写书评

暂无评论

The Complexity of Finding Fair Many-to-One Matchings

引用

ACM TRANSACTIONS ON algorithms 2024年第2期20卷 1-37页

作者： Boehmer, Niclas Koana, Tomohiro Tech Univ Berlin Str 17 Juni 135 D-10623 Berlin Germany

We analyze the (parameterized) computational complexity of "fair" variants of bipartite many-to-one matching, where each vertex from the "left" side is matched to exactly one vertex and each vertex from the "right" side may be matched to multiple vertices. We want to find a "fair" matching, in which each vertex from the right side is matched to a "fair" set of vertices. Assuming that each vertex from the left side has one color modeling its "attribute", we study two fairness criteria. For instance, in one of them, we deem a vertex set fair if for any two colors, the difference between the numbers of their occurrences does not exceed a given threshold. Fairness is, for instance, relevant when finding many-to-one matchings between students and colleges, voters and constituencies, and applicants and firms. Here colors may model sociodemographic attributes, party memberships, and qualifications, respectively. We show that finding a fair many-to-one matching is NP-hard even for three colors and maximum degree five. Our main contribution is the design of fixed-parameter tractable algorithms with respect to the number of vertices on the right side. Our algorithms make use of a variety of techniques including color coding. At the core lie integer linear programs encoding Hall like conditions. We establish the correctness of our integer programs, based on Frank's separation theorem [Frank, Discrete Math. 1982]. We further obtain complete complexity dichotomies regarding the number of colors and the maximum degree of each side.

关键词： Graph theory polynomial-time algorithms NP-hardness FPT ILP color coding submodular and supermodular functions algorithmic fairness

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Default reasoning from conditional knowledge bases: Complexity and tractable cases

引用

ARTIFICIAL INTELLIGENCE 2000年第2期124卷 169-241页

作者： Eiter, T Lukasiewicz, T Vienna Univ Technol Inst & Ludwig Wittgenstein Labor Informat Syst A-1040 Vienna Austria

Conditional knowledge bases have been proposed as belief bases that include defeasible rules (also called defaults) of the form "phi --> psi", which informally read as "generally, if phi then psi". Such rules may have exceptions, which can be handled in different ways. A number of entailment semantics for conditional knowledge bases have been proposed in the literature. However, while the semantic properties and interrelationships of these formalisms are quite well understood, about their computational properties only partial results are known so far. In this paper, we fill these gaps and first draw a precise picture of the complexity of default reasoning from conditional knowledge bases: Given a conditional knowledge base KB and a default phi --> psi, does KB entail phi --> psi? We classify the complexity of this problem for a number of well-known approaches (including Goldszmidt et al.'s maximum entropy approach and Geffner's conditional entailment), where we consider the general propositional case as well as natural syntactic restrictions (in particular, to Horn and literal-Horn conditional knowledge bases). As we show, the more sophisticated semantics for conditional knowledge bases are plagued with intractability in all these fragments. We thus explore cases in which these semantics are tractable, and find that most of them enjoy this property on feedback-free Horn conditional knowledge bases, which constitute a new, meaningful class of conditional knowledge bases. Furthermore, we generalize previous tractability results from Horn to q-Horn conditional knowledge bases, which allow for a limited use of disjunction. Our results complement and extend previous results, and contribute in refining the tractability/intractability frontier of default reasoning from conditional knowledge bases. They provide useful insight for developing efficient implementations. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： reasoning under uncertainty conditional knowledge bases default reasoning nonmonotonic inference computational complexity polynomial-time algorithms Horn knowledge bases and variants

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：