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

Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time

引用

INFORMATION SCIENCES 2013年 251卷 150-163页

作者： Chen, Yong Zhang, An Tan, Zhiyi Hangzhou Dianzi Univ Inst Operat Res & Cybernet Hangzhou 310018 Zhejiang Peoples R China Zhejiang Univ Dept Math State Key Lab CAD & CG Hangzhou 310027 Zhejiang Peoples R China

This paper considers the single machine scheduling problem with an operator non-availability period. The operator non-availability period is an open time interval in which a job may neither start nor complete. The objective is to minimize the total completion time. We prove that the problem is NP-hard, even if the length of the operator non-availability period is smaller than the processing time of any job. We also present an algorithm with a tight worst-case ratio of 20/17. (c) 2013 Elsevier Inc. All rights reserved.

关键词： Scheduling Machine maintenance approximation algorithm Worst-case analysis

来源：评论

学校读者我要写书评

暂无评论

approximation algorithmS FOR QMA-COMPLETE PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 2012年第4期41卷 1028-1050页

作者： Gharibian, Sevag Kempe, Julia Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada Univ Waterloo Inst Quantum Comp Waterloo ON N2L 3G1 Canada Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel Univ Paris 07 CNRS Paris France Univ Paris 07 LIAFA Paris France

approximation algorithms for classical constraint satisfaction problems are one of the main research areas in theoretical computer science. Here we define a natural approximation version of the QMA-complete local Hamiltonian problem (where QMA stands for Quantum Merlin Arthur) and initiate its study. We present two main results. The first shows that a nontrivial approximation ratio can be obtained in the class NP using product states. The second result (which builds on the first one) gives a polynomial time (classical) algorithm providing a similar approximation ratio for dense instances of the problem. The latter result is based on an adaptation of the "exhaustive sampling method" by Arora, Karger, and Karpinski [J. Comput. System Sci., 58 (1999), p. 193] to the quantum setting and might be of independent interest.

关键词： QMA-complete approximation algorithm local Hamiltonian constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

An improved approximation ratio for the jump number problem on interval orders

引用

THEORETICAL COMPUTER SCIENCE 2013年 513卷 77-84页

作者： Krysztowiak, Przemyslaw Nicholas Copernicus Univ Fac Math & Comp Sci PL-87100 Torun Poland

The jump number problem is to find a linear extension of a given poset that minimizes the number of incomparable adjacent elements. The problem is NP-hard even in the class of interval orders and so three different 3/2-approximation algorithms for this case have been proposed respectively by Felsner, Syslo, and Mitas. We build upon the approach of Mitas, where the problem is reduced to packing vertex-disjoint edges and odd cycles in a certain graph. We prove that the requirement of independence between edges and cycles may be abandoned. In effect, the jump number problem is reduced to the set cover problem, and the 4/3-approximation algorithm of Duh and Purer for the 3-set cover problem is used to show that the approximation ratio of the jump number problem on interval orders is tighter than 89/60. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Poset Jump number approximation algorithm Combinatorial optimization Interval order Linear extension Graph packing Set cover

来源：评论

学校读者我要写书评

暂无评论

Improved approximation for spanning star forest in dense graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2013年第2期25卷 255-264页

作者： He, Jing Liang, Hongyu Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China

A spanning subgraph of a graph G is called a spanning star forest of G if it is a collection of node-disjoint trees of depth at most 1. The size of a spanning star forest is the number of leaves in all its components. The goal of the spanning star forest problem is to find the maximum-size spanning star forest of a given graph. In this paper, we study the spanning star forest problem on c-dense graphs, where for any fixed ca(0,1), a graph of n vertices is called c-dense if it contains at least cn (2)/2 edges. We design a -approximation algorithm for spanning star forest in c-dense graphs for any I mu > 0, where is the best known approximation ratio of the spanning star forest problem in general graphs. Thus, our approximation ratio outperforms the best known bound for this problem when dealing with c-dense graphs. We also prove that, for any constant ca(0,1), approximating spanning star forest in c-dense graphs is APX-hard. We then demonstrate that for weighted versions (both node- and edge-weighted) of this problem, we cannot get any approximation algorithm with strictly better performance guarantee on c-dense graphs than on general graphs. Finally, we give strong inapproximability results for a closely related problem, namely the minimum dominating set problem, restricted on c-dense graphs.

关键词： Spanning star forest Dense graph approximation algorithm Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

AN algorithmIC FRAMEWORK FOR SOLVING GEOMETRIC COVERING PROBLEMS - WITH APPLICATIONS

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2014年第5期25卷 623-639页

作者： Ghasemi, Taha Ghasemalizadeh, Hossein Razzazi, Mohammadreza Amirkabir Univ Technol Software Syst R&D Lab Comp Engn & IT Dept Tehran Iran Inst Res Fundamental Sci IPM Tehran Iran

In geometric covering problems, the aim is to cover a set of given points using a minimum number of shapes with prescribed properties. These problems extend in many ways such as covering in the presence of obstacles and partial covering. Since in most cases these problems are NP-hard, researchers have developed a large number of approximation algorithms to solve them. In this paper, with a more general view on these approadies, we propose an algorithmic framework that gives an approximation algorithm for the covering problem at hand, provided that its prerequisites are satisfied. As the result, we present a general class of geometric covering problems for which one can obtain polynomial-time approximation schemes (PTASs). This class of problems involves covering point sets with bounded shapes in a space with fixed dimension. For a problem to be in this class, it must be possible to find a polynomial number of maximal shapes and it must be possible to cover all the points in a small box with a small number of shapes. Using this frame:work, is e present two new PTASs for the problems covering with disks in the presence of polygonal obstacles and covering with sectors (pie-shaped wedges). The first problem has never been addressed before and for the second problem, only a logarithmic approximation algorithm was known in general and a 9-approximation algorithm for Wide angles.

关键词： Geometric covering covering with disks covering with obstacles covering with sectors set cover problem algorithmic framework approximation algorithm computational gcometry

来源：评论

学校读者我要写书评

暂无评论

The hardness and approximation of the star p-hub center problem

引用

OPERATIONS RESEARCH LETTERS 2013年第2期41卷 138-141页

作者： Liang, Hongyu Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China

We consider the star p-hub center problem recently introduced by Yaman and Elloumi [H. Yaman and S. Elloumi. Star p-hub center problem and star p-hub median problem with bounded path lengths, Comput. Oper. Res., 39 (11) (2012) 2725-2732]. We first show that the problem does not admit a (1.25 - is an element of)-approximation algorithm for any is an element of > 0 unless P = NP. In particular this gives the first strong NP-hardness result for the problem in a metric space. We also present, complementing the inapproximability result, a purely combinatorial 3.5-approximation algorithm for the star p-hub center problem. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Star p-hub center problem NP-hardness approximation algorithm Hardness of approximation

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Semi-random Partitioning Problems 12

Approximation Algorithms for Semi-random Partitioning Proble...

引用

44th ACM Annual Symposium on Theory of Computing (STOC)

作者： Makarychev, Konstantin Makarychev, Yury Vijayaraghavan, Aravindan IBM Res Ossining NY 10562 USA Toyota Technol Inst Chicago Chicago IL USA Princeton Univ Princeton NJ 08544 USA

ISBN: (纸本)9781450312455

In this paper, we propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of real-world instances. The model is more flexible than the semi-random model of Feige and Kilian and planted random model of Bui, Chaudhuri, Leighton and Sipser. We develop a general framework for solving semi-random instances and apply it to several problems of interest. We present constant factor bi-criteria approximation algorithms for semi-random instances of the Balanced Cut, Multicut, Min Uncut, Sparsest Cut and Small Set Expansion problems. We also show how to almost recover the optimal solution if the instance satisfies an additional expanding condition. Our algorithms work in a wider range of parameters than most algorithms for previously studied random and semi-random models. Additionally, we study a new planted algebraic expander model and develop constant factor bi-criteria approximation algorithms for graph partitioning problems in this model.

关键词： approximation algorithm semi-random model random planted model average-case analysis graph partitioning

来源：评论

学校读者我要写书评

暂无评论

Swarm Intelligence algorithm for Optimality Discovery in Distributed Constraint Optimization

Swarm Intelligence Algorithm for Optimality Discovery in Dis...

引用

IEEE International Conference on Systems, Man, and Cybernetics

作者： Kazuhei Hasegawa Masato Noto Dept. of Electrical Electronics and Information Engineering Kanagawa University

ISBN: (纸本)9781479938414

The distributed constraint optimization problem (DCOP) is known as a basic problem of multiagent systems. This problem seeks optimal solutions using cooperative behavior between agents. However, because DCOP is NP-hard, the computational load becomes massive as the number of agents increase. What are needed are high-speed algorithms that can solve problems without increasing the computational load. In recent years, methods that intentionally limit the number of cooperative agents, such as k-optimality and p-optimality, have been proposed as approximate algorithms. They are drawing attention as new approximate algorithms because they can obtain deviations from the optimal solutions. The value of optimality is an artificially established partition of state space, and there is a need to change the value for different network topologies. In this paper, we propose a method that uses swarm intelligence as a new DCOP algorithm. Each agent evaluates the state space using swarm intelligence. The available state is determined not based on values decided by each agent. Instead, a cooperative space is produced based on heuristic values to determine the optimal solutions. We also show that a new criteria of optimality can be obtained using swarm intelligence.

关键词： Particle Swarm Optimization (PSO) Distributed Constraint Optimization Problem (DCOP) Multiagent approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On Approximating Constructions of Restricted Shortest Paths in Digraphs

On Approximating Constructions of Restricted Shortest Paths ...

引用

2014 International Conference on Computer,Network Security and Communication Engineering(CNSCE 2014)

作者： Jian-ping LI Hong-lin DING Wei-dong LI Department of Mathematics Yunnan University Department of Atmospheric Science Yunnan University

For a given weighted digraph D =（V, A;s, t;w, c;B）, certain stock pieces of length L and an unit price c for each stock piece, where a length function w: A → Z, a construction cost function c: A → Z0 and a constant positive integer B, we are asked to construct a path P from s to t in D, having total length ∑w（ e）≤ B, such that the arcs in P are to be cut from some stock pieces of length L, the new objective is to minimize the total cost ∑c（ e） k（ P）c where k（ P） , denotes the number of necessary stock pieces to construct the arcs in P. Moreover, we consider a special version of this problem, where c（e） =0 holds for each arc e ∈A. We design two asymptotic approximation algorithms to solve them, respectively.

关键词： Path construction Restricted shortest path Inapproximability approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the approximation of minimum cost homomorphism to bipartite graphs

引用

DISCRETE APPLIED MATHEMATICS 2013年第4-5期161卷 670-676页

作者： Mastrolilli, Monaldo Rafiey, Arash IDSIA Switzerland

For a fixed target graph H, the minimum cost homomorphism problem, MinHOM(H), asks, for a given graph G with integer costs c(i)(u), u is an element of V (G), i is an element of V (H), and an integer k, whether or not there exists a homomorphism of G to H of cost not exceeding k. When the target graph H is a bipartite graph a dichotomy classification is known: MinHOM(H) is solvable in polynomial time if and only if H does not contain bipartite claws, nets, tents and any induced cycles C-2k for k >= 3 as an induced subgraph. In this paper, we start studying the approximability of MinHOM(H) when H is bipartite. First we note that if H has as an induced subgraph C-2k for k >= 3, then there is no approximation algorithm. Then we suggest an integer linear program formulation for MinHOM(H) and show that the integrality gap can be made arbitrarily large if H is a bipartite claw. Finally, we obtain a 2-approximation algorithm when H is a subclass of doubly convex bipartite graphs that has as special case bipartite nets and tents. Crown Copyright (C) 2011 Published by Elsevier B.V. All rights reserved.

关键词： Minimum cost homomorphism approximation algorithm Min-max ordering

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：