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

11th International Conference on Learning and Intelligent Optimization (LION)

作者： Kononov, Alexander Kovalenko, Yulia Sobolev Inst Math 4 Akad Koptyug Ave Novosibirsk 630090 Russia

ISBN: (纸本)9783319694047;9783319694030

In this paper we consider a problem of preemptive scheduling rigid parallel jobs on speed scalable processors. Each job is specified by its release date, its deadline, its processing volume and the number of processors, which are required for execution of the job. We propose a new strongly polynomial approximation algorithm for the energy minimization problem with migration of jobs.

关键词： Parallel jobs Speed scaling Scheduling Migration approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Local Search approximation algorithm for a Squared Metric k-Facility Location Problem 11th

A Local Search Approximation Algorithm for a Squared Metric ...

引用

11th Annual International Conference on Combinatorial Optimization and Applications (COCOA)

作者： Zhang, Dongmei Xu, Dachuan Wang, Yishui Zhang, Peng Zhang, Zhenning Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Beijing Univ Technol Coll Appl Sci Dept Informat & Operat Res Beijing 100124 Peoples R China Shandong Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

ISBN: (纸本)9783319711508;9783319711492

In this paper, we introduce a squared metric k-facility location problem (SM-k-FLP) which is a generalization of the squared metric facility location problem (SMFLP) and k-facility location problem (k-FLP). In the SM-k-FLP, we are given a client set C and a facility set F from a metric space, a facility opening cost f(i) >= 0 for each i is an element of F, and an integer k. The goal is to open a facility subset F subset of F with vertical bar F vertical bar <= k and to connect each client to the nearest open facility such that the total cost (including facility opening cost and the sum of squares of distances) is minimized. Using local search and scaling techniques, we offer a constant approximation algorithm for the SM-k-FLP.

关键词： approximation algorithm Facility location Local search

来源：评论

学校读者我要写书评

暂无评论

approximation algorithm for uniform quay crane scheduling at container ports

引用

DISCRETE MATHEMATICS algorithmS AND APPLICATIONS 2016年第2期8卷

作者： Liu, Ming Zheng, Feifeng Xu, Yinfeng Chu, Chengbin Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China Donghua Univ Glorious Sun Sch Business & Management Shanghai 200051 Peoples R China Sichuan Univ Sch Business Chengdu 610065 Peoples R China State Key Lab Mfg Syst Engn Xian 710049 Peoples R China Univ Paris Saclay Cent Supelec Lab Genie Ind F-92290 Chatenay Malabry France

At a container port, container vessels are served by quay cranes for loading and unloading containers. Each vessel is typically split into bays from head to tail where containers are stored. Parallel quay cranes can process different bays simultaneously, and their processing efficiency significantly affects the turn-around time of a container vessel. Sharing a single traveling rail, the quay cranes cannot crossover each other, and this phenomenon is referred as the non-crossing constraint. In addition, the quay cranes may have different processing speeds due to gradual equipment updates. Inspired by updating activities of cranes in modern container terminals, this paper studies a scheduling problem with two uniform quay cranes, aiming at minimizing the turn-around time of a vessel, i.e., the makespan. We mainly develop an integrated approximation algorithm which is min{(s + 1)/s, (s + 1)(2)/(s + 2)}-approximation, where the two quay cranes are of processing speeds 1 and s(>= 1), respectively.

关键词： Quay crane scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for maximum weight budgeted connected set cover

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第4期31卷 1505-1517页

作者： Ran, Yingli Zhang, Zhao Ko, Ker-I Liang, Jun Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China Natl Chiao Tung Univ Dept Comp Sci Hsinchu 30050 Taiwan Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

This paper studies approximation algorithm for the maximum weight budgeted connected set cover (MWBCSC) problem. Given an element set , a collection of sets , a weight function on , a cost function on , a connected graph (called communication graph) on vertex set , and a budget , the MWBCSC problem is to select a subcollection such that the cost , the subgraph of induced by is connected, and the total weight of elements covered by (that is ) is maximized. We present a polynomial time algorithm for this problem with a natural communication graph that has performance ratio , where is the maximum degree of graph and is the number of sets in . In particular, if every set has cost at most , the performance ratio can be improved to .

关键词： Budgeted set cover Connected set cover approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines

引用

JOURNAL OF SCHEDULING 2016年第1期19卷 21-31页

作者： Zhao, Kejun Lu, Xiwen Gu, Manzhan E China Univ Sci & Technol Sch Sci Dept Math Shanghai 200237 Peoples R China Shanghai Univ Finance & Econ Sch Math Shanghai 200433 Peoples R China

This paper studies a multi-agent scheduling problem on two identical parallel machines. There are g agents, and each agent's objective is to minimize its makespan. We present an approximation algorithm such that the performance ratio of the makespan achieved by our algorithm relative to the minimum makespan is no more than for the ith completed agent. Moreover, we show that the performance ratio is tight.

关键词： Multi-agent scheduling Identical machines Makespan approximation algorithm Performance ratio vector

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the longest cycle problem in solid grid graphs

引用

DISCRETE APPLIED MATHEMATICS 2016年 204卷 6-12页

作者： Sardroud, Asghar Asgharian Bagheri, Alireza Amirkabir Univ Technol Dept Comp Engn & IT Tehran Iran

Although, the Hamiltonicity of solid grid graphs are polynomial-time decidable, the complexity of the longest cycle problem in these graphs is still open. In this paper, by presenting a linear-time constant-factor approximation algorithm, we show that the longest cycle problem in solid grid graphs is in APX. More precisely, our algorithm finds a cycle of length at least 2n/3 + 1 in 2-connected n-node solid grid graphs. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Longest cycle Hamiltonian cycle approximation algorithm Solid grid graph

来源：评论

学校读者我要写书评

暂无评论

A 2-approximation algorithm for Scheduling Parallel and Time-Sensitive Applications to Maximize Total Accrued Utility Value

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2016年第7期27卷 1864-1878页

作者： Li, Shuhui Song, Miao Wan, Peng-Jun Ren, Shangping Dalian Univ Technol Dept Engn Mech Dalian 116024 Peoples R China IIT Dept Comp Sci Chicago IL 60616 USA

For a time-sensitive application, the usefulness of its end results (also called the application's accrued utility value in the paper) depends on the time when the application is completed and its results are delivered. In this paper, we address the accrued utility value maximization problem for narrow parallel and time-sensitive applications. We first consider the problem in the context of a discrete time domain and present the Spatial-Temporal Interference Based (STIB) scheduling algorithm. We formally prove that the STIB algorithm is a 2-approximation algorithm. Second, we extend our work to a continuous time domain and present a heuristic scheduling algorithm, i.e., the Continuous Spatial-Temporal Interference Based (STIB-C) algorithm to maximize the system's total accrued utility value when the system operates in a continuous time domain. The extensive empirical evaluations reveal that: (1) in a discrete time domain, the systems' total accrued utility values obtained through the STIB algorithm are consistent with the theoretic bound, i.e., they never go below 50 percent of the optimal value. In fact, on average, the STIB algorithm can achieve over 92.5 percent of the optimal value;(2) compared to other scheduling policies listed in the literature, the developed STIB and STIB-C algorithms have clear advantages in terms of the system's total accrued utility value and the profitable application ratio. In particular, in terms of the system's total accrued utility value, both the STIB and the STIB-C algorithms achieve as much as six times for both the First Come First Come Serve(FCFS) with backfilling algorithm and the Gang Earliest Deadline First (EDF) algorithm, and 4.5 times for the 0-1 Knapsack based scheduling algorithm. In terms of the profitable application ratio, both the STIB and the STIB-C algorithms obtain as much as four times for both the FCFS with backfilling algorithm and the Gang EDF algorithm, and two times for the 0-1 Knapsack based scheduling algo

关键词： Parallel time-sensitive scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An improved approximation algorithm for the shortest link scheduling in wireless networks under SINR and hypergraph models

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第4期32卷 1052-1067页

作者： Wang, Cui Yu, Jiguo Yu, Dongxiao Huang, Baogui Yu, Shanshan Qufu Normal Univ Sch Informat Sci & Engn Rizhao 276826 Shandong Peoples R China Univ Hong Kong Dept Comp Sci Pokfulam Hong Kong Peoples R China Shandong Univ Sch Informat Sci & Engn Jinan 250100 Peoples R China

Link scheduling is a fundamental problem in wireless ad hoc and sensor networks. In this paper, we focus on the shortest link scheduling (SLS) under Signal-to-Interference-plus-Noise-Ratio and hypergraph models, and propose an approximation algorithm (A link scheduling algorithm with oblivious power assignment for the shortest link scheduling) with oblivious power assignment for better performance than GOW* proposed by Blough et al. [IEEE/ACM Trans Netw 18(6):1701-1712, 2010]. For the average scheduling length of is 1 / m of GOW*, where is the expected number of the links in the set V returned by the algorithm HyperMaxLS (Maximal links schedule under hypergraph model) and is the constant. In the worst, ideal and average cases, the ratios of time complexity of our algorithm to that of GOW* are , and , respectively. Where () is a constant called the SNR diversity of an instance G.

关键词： Wireless network Shortest link scheduling approximation algorithm Hypergraph model SINR

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithm for the Combination of Parallel Machine Scheduling and Vertex Cover

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2017年第8期28卷 977-992页

作者： Hong, Wenyi Wang, Zhenbo Tsinghua Univ Dept Math Sci Beijing 100084 Peoples R China

This paper studies the combination problem of parallel machine scheduling and the vertex cover problem. Wang and Cui developed a (3 - 2/m+1)-approximation algorithm for this problem [13], where m is the number of parallel machines. We reduce the approximation factors from 2.33 to 2.25 for m = 2, from 2.5 to 2.33 for m = 3, and to 3 - 3/m+1 for m >= 4.

关键词： approximation algorithm combination of optimization problems local ratio LPT rule parallel machine scheduling vertex cover

来源：评论

学校读者我要写书评

暂无评论

A Connectivity-Aware approximation algorithm for Relay Node Placement in Wireless Sensor Networks

引用

IEEE SENSORS JOURNAL 2016年第2期16卷 515-528页

作者： Ma, Chaofan Liang, Wei Zheng, Meng Sharif, Hamid Chinese Acad Sci Key Lab Networked Control Syst Shenyang 110016 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Univ Nebraska Dept Comp & Elect Engn Omaha NE 68182 USA

In two-tiered wireless sensor networks (WSNs), relay node placement is one of the key factors impacting the network energy consumption and the system overhead. In this paper, a novel connectivity-aware approximation algorithm for relay node placement in the WSNs is proposed to offer a major step forward in saving system overhead. In particular, a unique local search approximation algorithm (LSAA) is introduced to solve the relay node single cover (RNSC) problem. In this proposed LSAA approach, the sensor nodes are allocated into groups and then a local set cover (SC) for each group is achieved by a local search algorithm. The union set of all the local SCs constitutes a SC of the RNSC problem. The approximation ratio and the time complexity of the LSAA are analyzed by rigorous proof. In addition, the LSAA approach has been extended to solve the relay node double cover problem. Then, a relay location selection algorithm (RLSA) is proposed to utilize the resulting SC from the LSAA in combining RLSA with the minimum spanning tree heuristic to build the high-tier connectivity. As the RLSA searches for a nearest location to the sink node for each relay node, the high-tier network built by the RLSA becomes denser than that by existing works. As a result, the number of added relay nodes for building the connectivity of the high-tier WSN can be significantly saved. Simulation results clearly demonstrate that the proposed LSAA outperforms the approaches reported in literature and the RLSA-based algorithm can noticeably save relay nodes newly deployed for the high-tier connectivity.

关键词： Wireless sensor networks relay node placement geometric disc cover network connectivity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：