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

Minimizing Total Completion time on Uniform Machines with Deadline Constraints

ACM TRANSACTIONS ON algorithms 2006年第1期2卷 95-115页

作者： Gonzalez, Teofilo F. Leung, Joseph Y. -T. Pinedo, Michael Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA NYU Stern Sch Business New York NY 10012 USA

Consider n independent jobs and m uniform machines in parallel. Each job has a processing requirement and a deadline. All jobs are available for processing at time t = 0. Job j must complete its processing before or at its deadline and preemptions are allowed. A set of jobs is said to be feasible if there exists a schedule that meets all the deadlines. We present a polynomial-time algorithm that given a feasible set of jobs, constructs a schedule that minimizes the total completion time Sigma C-j. In the classical alpha vertical bar beta vertical bar gamma scheduling notation, this problem is referred to as Qm vertical bar prmt, (d) over bar (j )vertical bar Sigma C-j. It is well known that a generalization of this problem with regard to its machine environment results in an NP-hard problem.

关键词： Mean flow time uniform machines deadline constraints polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

On optimal spectrum-efficient routing in TDMA and FDMA multihop wireless networks

引用

COMPUTER COMMUNICATIONS 2012年第5期35卷 628-636页

作者： Saad, Mohamed Univ Sharjah Dept Elect & Comp Engn Sharjah U Arab Emirates

This paper addresses the problem of finding the route with maximum end-to-end spectral efficiency, under the constraint of equal bandwidth sharing, in multihop wireless networks that use time division multiple access (TDMA) or frequency division multiple access (FDMA). The conceptual difficulty of this problem arises from the fact that the associated routing metric is neither isotonic nor monotone, and, thus, it cannot be solved directly using shortest path algorithms. The author has recently presented the first polynomial-time algorithm that solves the problem to exact optimality for TDMA networks. The contribution of this paper is twofold. For TDMA networks, we present a new algorithm that achieves a significant improvement in the computational complexity as compared to the algorithms previously known. For FDMA networks, we introduce the first polynomial-time algorithm that provides provably optimal routes. The proposed algorithms rely on the divide-and-conquer principle and a modified Bellman-Ford algorithm for widest path computation. Our computational results further illustrate the efficiency of the proposed approach. (C) 2011 Elsevier B.V. All rights reserved.

关键词： Multihop wireless networks Spectrum-efficient routing TDMA FDMA polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Critical (P6, banner)-free graphs

引用

DISCRETE APPLIED MATHEMATICS 2019年 258卷 143-151页

作者： Huang, Shenwei Li, Tao Shi, Yongtang Nankai Univ Coll Comp Sci Tianjin 300071 Peoples R China Nankai Univ Ctr Combinator Tianjin 300071 Peoples R China Nankai Univ LPMC Tianjin 300071 Peoples R China

Given two graphs H-1 and H-2, a graph is (H-1, H-2)-free if it contains no induced subgraph isomorphic to H-1 or H-2. Let P-t and C-t be the path and the cycle on t vertices, respectively. A banner is the graph obtained from a C-4 by adding a new vertex and making it adjacent to exactly one vertex of the C-4. In this paper, we show that there are finitely many k-critical (P-6, banner)-free graphs for k = 4 and k = 5. For k = 4, we characterize all such graphs. Our results generalize previous results on k-critical (P-6, C-4)-free graphs for k = 4 and k = 5. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Coloring Critical graphs Hereditary classes Strong perfect graph theorem polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

A 5-parameter complexity classification of the two-stage flow shop scheduling problem with job dependent storage requirements

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第2期42卷 276-309页

作者： Zinder, Yakov Kononov, Alexandr Fung, Joey Univ Technol Sydney NSW Australia Sobolev Inst Math Novosibirsk Russia BHP Operat Res Res & Dev Technol Perth WA Australia

The paper is concerned with the two-machine scheduling problem where each job is to be processed on the first-stage machine and after that on the second-stage machine. In order to be processed, each job requires storage space that it seizes at the start of its processing on the first-stage machine and releases only at the completion of processing on the second-stage machine. The storage space is limited and its consumption varies from job to job. The goal is to minimise the time needed for the completion of all jobs. All instances of the considered scheduling problem are classified by means of five parameters. This leads to the sixty four families of instances. For each family, the paper establishes its computational complexity and, in the case of polynomial-time solvability, presents a polynomial-time algorithm, constructing an optimal schedule.

关键词： Computational complexity Flow shop Buffer polynomial-time algorithms Resource constrained scheduling

来源：评论

学校读者我要写书评

暂无评论

A polynomial projection-type algorithm for linear programming

引用

OPERATIONS RESEARCH LETTERS 2014年第1期42卷 91-96页

作者： Vegh, Laszlo A. Zambelli, Giacomo Univ London London Sch Econ & Polit Sci Dept Management London WC2A 2AE England

We propose a simple O(vertical bar n(5)/log n vertical bar L) algorithm for linear programming feasibility, that can be considered as a polynomial-time implementation of the relaxation method. Our work draws from Chubanov's "Divide-and-Conquer" algorithm (Chubanov, 2012), with the recursion replaced by a simple and more efficient iterative method. A similar approach was used in a more recent paper of Chubanov (2013). (C) 2014 Elsevier B.V. All rights reserved.

关键词： Linear programming polynomial-time algorithms Relaxation method

来源：评论

学校读者我要写书评

暂无评论

A polynomial-time algorithm for a nonconvex chance-constrained program under the normal approximation

引用

OPTIMIZATION LETTERS 2023年第2期17卷 265-282页

作者： Mildebrath, David Rice Univ Dept Computat & Appl Math 3100 Main St MS-134 Houston TX 77005 USA

We study a chance-constrained optimization problem where the random variable appearing in the chance constraint follows a normal distribution whose mean and variance both depend linearly on the decision variables. Such structure may arise in many applications, including the normal approximation to the Poisson distribution. We present a polynomial-time algorithm to solve the resulting nonconvex optimization problem, and illustrate the efficacy of our method using a numerical experiment.

关键词： Chance-constrained programming Reverse convex programming Nonlinear optimization polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Bi-arc graphs and the complexity of list homomorphisms

引用

JOURNAL OF GRAPH THEORY 2003年第1期42卷 61-80页

作者： Feder, T Hell, P Huang, J Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Victoria Dept Math & Stat Victoria BC V8W 3P4 Canada

Given graphs G, H, and lists L(v) subset of or equal to V(H), v is an element of V(G), a list homomorphism of G to H with respect to the lists L is a mapping f: V(G) --> V(H) such that uv is an element of E(G) implies f(u)f(v) is an element of E(H), and f(v) is an element of (v) for all v is an element of V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) subset of or equal to V(H), v is an element of V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and (H) over bar is a circular arc graph, and is NP-complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi-arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi-arc graph, and is NP-complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. (C) 2002 Wiley Periodicals, Inc.

关键词： list colorings list homomorphisms internal graphs circular arc graphs bi-arc graphs edge asteroids sheet width polynomial-time algorithms NP-completeness complexity

来源：评论

学校读者我要写书评

暂无评论

Online Pricing Incentive to Sample Fresh Information

引用

IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING 2023年第1期10卷 514-526页

作者： Li, Hongbo Duan, Lingjie Singapore Univ Technol & Design Pillar Engn Syst & Design Singapore 487372 Singapore

Today mobile users such as drivers are invited by content providers (e.g., Tripadvisor) to sample fresh information of diverse paths to control the age of information (AoI). However, selfish drivers prefer to travel through the shortest path instead of the others with extra costs in time and gas. To motivate drivers to route and sample diverse paths, this paper is the first to propose online pricing for a provider to economically reward drivers for diverse routing and control the actual AoI dynamics over time and spatial path domains. This online pricing optimization problem should be solved without knowing drivers' costs and even arrivals, and is intractable due to the curse of dimensionality in both time and space. If there is only one non-shortest path, we leverage the Markov decision process (MDP) techniques to analyze the problem. Accordingly, we design a linear-time algorithm for returning optimal online pricing, where a higher pricing reward is needed for a larger AoI. If there are a number of non-shortest paths, we prove that pricing one path at a time is optimal, yet it is not optimal to choose the path with the largest current AoI. Then we propose a new backward-clustered computation method and develop an approximation algorithm to alternate different paths to price over time. Perhaps surprisingly, our analysis of approximation ratio suggests that our algorithm's performance approaches closer to optimum given more paths.

关键词： Pricing Vehicles Costs Approximation algorithms Heuristic algorithms Routing Roads Age of information approximation error online multi-path pricing polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Colouring graphs with no induced six-vertex path or diamond

引用

THEORETICAL COMPUTER SCIENCE 2023年 941卷 278-299页

作者： Goedgebeur, Jan Huang, Shenwei Ju, Yiao Merkel, Owen Katholieke Univ Leuven Dept Comp Sci Campus Kulak B-8500 Kortrijk Belgium Univ Ghent Dept Appl Math Comp Sci & Stat B-9000 Ghent Belgium Nankai Univ Coll Comp Sci Tianjin 300350 Peoples R China Wilfrid Laurier Univ Dept Math Waterloo ON Canada

The diamond is the graph obtained by removing an edge from the complete graph on 4 vertices. A graph is (P6, diamond)-free if it contains no induced subgraph isomorphic to a six-vertex path or a diamond. In this paper we show that the chromatic number of a (P6, diamond)-free graph G is no larger than the maximum of 6 and the clique number of G. We do this by reducing the problem to imperfect (P6, diamond)-free graphs via the Strong Perfect Graph Theorem, dividing the imperfect graphs into several cases, and giving a proper colouring for each case. We also show that there is exactly one 6-vertex -critical (P6, diamond, K6)-free graph. Together with the Lovasz theta function, this gives a polynomial time algorithm to compute the chromatic number of (P6, diamond)-free graphs.2022 Elsevier B.V. All rights reserved.

关键词： Graph colouring ?-boundedness Strong perfect graph theorem Lov?sz theta function polynomial-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Scheduling time-dependent jobs under mixed deterioration

引用

APPLIED MATHEMATICS AND COMPUTATION 2010年第2期216卷 438-447页

作者： Gawiejnowicz, Stanislaw Lin, Bertrand M. T. Adam Mickiewicz Univ Poznan Fac Math & Comp Sci PL-61614 Poznan Poland Natl Chiao Tung Univ Dept Informat & Finance Management Inst Informat Management Hsinchu 300 Taiwan

We consider a new model of time-dependent scheduling. A set of deteriorating jobs has to be processed on a single machine which is available starting from a non-zero time. The processing times of some jobs from this set are constant, while other ones are either proportional or linear functions of the job starting times. The applied criteria of schedule optimality include the maximum completion time, the total completion time, the total weighted completion time, the maximum lateness and the number of tardy jobs. We delineate a sharp boundary between computationally easy and difficult problems, showing polynomially solvable and NP-hard cases. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Scheduling Single machine Deteriorating jobs polynomial-time algorithms NP-hard problems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：