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

SOME COMPLEXITY AND approximation RESULTS FOR COUPLED-TASKS SCHEDULING PROBLEM ACCORDING TO TOPOLOGY

RAIRO-OPERATIONS RESEARCH 2016年第4-5期50卷 781-795页

作者： Darties, Benoit Giroudeau, Rodolphe Konig, Jean-Claude Simonin, Gilles Univ Burgundy UMR CNRS 6306 LE2I 8 Rue Alain Savary F-21000 Dijon France Univ Montpellier UMR CNRS 5506 LIRMM 161 Rue Ada F-34392 Montpellier 5 France Univ Coll Cork Insight Ctr Data Analyt Cork Ireland

We consider the makespan minimization coupled-tasks problem in presence of compatibility constraints with a specified topology. In particular, we focus on stretched coupled-tasks, i.e. coupled-tasks having the same sub-tasks execution time and idle time duration. We study several problems in framework of classic complexity and approximation for which the compatibility graph is bipartite (star, chain, ...). In such a context, we design some efficient polynomial-time approximation algorithms for an intractable scheduling problem according to some parameters.

关键词： Coupled-task scheduling model complexity polynomial-time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for MAX n/2-DIRECTED-BISECTION and MAX n/2-DENSE-SUBGRAPH

引用

JOURNAL OF GLOBAL OPTIMIZATION 2003年第4期27卷 399-410页

作者： Xu, DC Han, JY Huang, ZH Zhang, LP Chinese Acad Sci Acad Math & Syst Sci Inst Appl Math Beijing 100080 Peoples R China Tsing Hua Univ Dept Math Sci Beijing 100084 Peoples R China

We consider the MAX n/2-DIRECTED-BISECTION problem, i.e., partitioning the vertices of a directed graph into two blocks of equal cardinality so as to maximize the total weight of the edges in the directed cut. A polynomial approximation algorithm using a semidefinite-relaxation with 0.6458 performance guarantee is presented for the problem. The previous best-known results for approximating this problem are 0.5 using a linear programming relaxation, 0.6440 using a semidefinite relaxation. We also consider the MAX n/2-DENSE-SUBGRAPH problem, i.e., determine a block of half the number of vertices from a weighted undirected graph such that the sum of the edge weights, within the subgraph induced by the block, is maximized. We present an 0.6236 approximation of the problem as opposed to 0.6221 of Halperin and Zwick.

关键词： MAX n/2-DIRECTED-BISECTION MAX n/2-DENSE-SUBGRAPH polynomial-time approximation algorithm semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

Fast approximation algorithms for job scheduling with processing set restrictions

引用

THEORETICAL COMPUTER SCIENCE 2010年第44-46期411卷 3947-3955页

作者： Huo, Yumei Leung, Joseph Y-T 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 scheduling n independent jobs on m parallel machines, where the machines differ in their functionality but not in their processing speeds. Each job has a restricted set of machines to which it can be assigned, called its processing set. Preemption is not allowed. Our goal is to minimize the makespan of the schedule. We study two variants of this problem: (1) the case of tree-hierarchical processing set and (2) the case of nested processing set. We first give a fast algorithm for the case of tree-hierarchical processing set with a worst-case bound of 4/3, which is better than the best known algorithm whose worst-case bound is 2. We then give a more complicated algorithm for the case of nested processing set with a worst-case bound of 5/3, which is better than the best known algorithm whose worst-case bound is 7/4. In both cases, we will give examples achieving the worst-case bounds. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Tree-hierarchical processing set Inclusive processing set Nested processing set Makespan minimization polynomial-time approximation algorithm NP-hard Nonpreemptive scheduling

来源：评论

学校读者我要写书评

暂无评论

A complexity and approximation framework for the maximization scaffolding problem

引用

THEORETICAL COMPUTER SCIENCE 2015年 595卷 92-106页

作者： Chateau, A. Giroudeau, R. Univ Montpellier LIRMM UMR CNRS 5506 F-34392 Montpellier 5 France LIRMM Inst Biol Computat F-34090 Montpellier France

We explore in this paper some complexity issues inspired by the contig scaffolding problem in bioinformatics. We focus on the following problem: given an undirected graph with no loop, and a perfect matching on this graph, find a set of cycles and paths covering every vertex of the graph, with edges alternatively in the matching and outside the matching, and satisfying a given constraint on the numbers of cycles and paths. We show that this problem is NP-complete, even in planar bipartite graphs. Moreover, we show that there is no subexponential-time algorithm for several related problems unless the Exponential-time Hypothesis fails. Lastly, we also design two polynomial-time approximation algorithms for complete graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Complexity polynomial-time approximation algorithm Scaffolding

来源：评论

学校读者我要写书评

暂无评论

Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints

引用

THEORETICAL COMPUTER SCIENCE 2021年 858卷 35-48页

作者： Nguyen, Trung Thanh Rothe, Joerg Phenikaa Univ ORLab Fac Comp Sci Hanoi 12116 Vietnam Heinrich Heine Univ Dusseldorf Inst Informat D-40225 Dusseldorf Germany

We study a generalized version of the load balancing problem on unrelated machines with cost constraints: Given a set of m machines (of certain types) and a set of n jobs, each job j processed on machine i requires p(i,j) time units and incurs a cost c(i,) j, and the goal is to find a schedule of jobs to machines, which is defined as an ordered partition of n jobs into m disjoint subsets, in such a way that some objective function of the vector of the completion times of the machines is optimized, subject to the constraint that the total costs by the schedule must be within a given budget B. Motivated by recent results from the literature, our focus is on the case when the number of machine types is a fixed constant and we develop a bi-criteria approximation scheme for the studied problem. Our result generalizes several known results for certain special cases, such as the case with identical machines, or the case with a constant number of machines with cost constraints. Building on the elegant technique recently proposed by Jansen and Maack [1], we construct a more general approach that can be used to derive approximation schemes for a wider class of load balancing problems with linear constraints. (c) 2020 Elsevier B.V. All rights reserved.

关键词： Bi-criteria approximation algorithm polynomial-time approximation algorithm Load balancing Machine scheduling

来源：评论

学校读者我要写书评

暂无评论

A .699-approximation algorithm for Max-Bisection

引用

MATHEMATICAL PROGRAMMING 2001年第1期90卷 101-111页

作者： Ye, YY Univ Iowa Dept Management Sci Henry B Tippie Coll Business Iowa City IA 52242 USA

We present a .699-approximation algorithm fur Max-Bisection, i.e., partitioning the nodes of a weighted graph into two blocks of equal cardinality so as to maximize the weights of crossing edges. This is an improved result from the .651-approximation algorithm of Frieze and Jerrum and the semidefinite programming relaxation of Goemans and Williamson.

关键词： graph bisection polynomial-time approximation algorithm semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for quadratic programming

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 1998年第1期2卷 29-50页

作者： Fu, MY Luo, ZQ Ye, YY Univ Newcastle Dept Elect & Comp Engn Newcastle NSW 2308 Australia McMaster Univ Dept Elect & Comp Engn Hamilton ON L8S 4K1 Canada Univ Iowa Dept Management Sci Iowa City IA 52242 USA

We consider the problem of approximating the global minimum of a general quadratic program (QP) with n variables subject to m ellipsoidal constraints. For m = 1, we rigorously show that an c-minimizer, where error epsilon is an element of (0, 1), can be obtained in polynomial time, meaning that the number of arithmetic operations is a polynomial in n, m, and log(1/epsilon). For m greater than or equal to 2, we present a polynomial-time (1 - 1/m(2))-approximation algorithm as well as a semidefinite programming relaxation for this problem. In addition, we present approximation algorithms for solving QP under the box constraints and the assignment polytope constraints.

关键词： quadratic programming global minimizer polynomial-time approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for MAX DICUT with Given Sizes of Parts

引用

Acta Mathematicae Applicatae Sinica 2003年第2期19卷 289-296页

作者： DachuanXu GuanghuiLiu InstituteofAppliedMathematics AcademyofMathematicsandSystemSciencesChineseAcademyofSciencesBeijing100080China WHQKB ResearchandDevelopmentUnitedAirlinesElkGroveTownshipIL60007USA

Abstract Given a directed graph G and an edge weight function w : A(G) M R^+ the maximum directed cut problem (MAX DICUT) is that of finding a directed cut '(S) with maximum total weight. We consider a version of MAX DICUT -- MAX DICUT with given sizes of parts or MAX DICUT WITH GSP -- whose instance is that of MAX DICUT plus a positive integer k, and it is required to find a directed cut '(S) having maximum weight over all cuts '(S) with |S|=k. We present an approximation algorithm for this problem which is based on semidefinite programming (SDP) relaxation. The algorithm achieves the presently best performance guarantee for a range of k.

关键词： Keywords MAX DICUT polynomial-time approximation algorithm semidefinite programming

来源：评论

学校读者我要写书评

暂无评论

approximation algorithmS FOR SOME ROUTING PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 1978年第2期7卷 178-193页

作者： FREDERICKSON, GN HECHT, MS KIM, CE

Several polynomial time approximation algorithms for some NPNPNP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strat... 详细信息

Several polynomial time approximation algorithms for some

N P

$NP$ -complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined. A mixed-strategy heuristic with a bound of 9/5 is presented for the stacker-crane problem (a modified traveling salesman problem). A tour-splitting heuristic is given for k-person variants of the traveling salesman problem, the Chinese postman problem, and the stacker-crane pr

关键词： -complete problems polynomial-time approximation algorithm heuristic worst-case performance bound traveling salesman problem Chinese postman problem stacker-crane problem -person routing

来源：评论

学校读者我要写书评

暂无评论

A Distributed Deterministic approximation algorithm for Data Association

A Distributed Deterministic Approximation Algorithm for Data...

引用

7th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS)

作者： Oh, Songhwai Seoul Natl Univ ASRI Sch Elect Engn & Comp Sci Seoul South Korea

ISBN: (纸本)9781457705137

The data association problem appears in many applications and is considered as the most challenging problem in intelligent systems. In this paper, we consider the Bayesian formulation of data association problems and present a deterministic polynomial-time approximation algorithm with guaranteed error bounds using correlation decay from statistical physics. We then show that the proposed algorithm naturally partitions a complex problem into a set of local problems and develop a distributed version of the algorithm. The performance of the proposed algorithm is evaluated in simulation.

关键词： approximation algorithms approximation methods Correlation Density measurement Distributed databases Partitioning algorithms polynomials approximation theory computational complexity correlation decay data association distributed deterministic approximation algorithm polynomial-time approximation algorithm sensor fusion statistical analysis statistical physics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：