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

Parallel batch scheduling: Impact of increasing machine capacity

OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 2022年 108卷 102567-102567页

作者： Xu, Jun Wang, Jun-Qiang Liu, Zhixin Northwestern Polytech Univ Performance Anal Ctr Prod & Operat Syst PacPos Xian 710072 Shaanxi Peoples R China Northwestern Polytech Univ Sch Mech Engn Dept Ind Engn Xian 710072 Shaanxi Peoples R China Univ Michigan Dearborn Coll Business Dept Management Studies 19000 Hubbard Dr Dearborn MI 48126 USA

Scheduling performance naturally improves with increased machine capacity, but the per-unit improvement typically decreases or even keeps unchanged with excessive capacity. We consider parallel batch scheduling on identical machines to minimize the makespan, with and without preemption. The machine capacity is the maximum number of jobs that a machine can process simultaneously. We quantitatively analyze the impact of capacity augmentation on the makespan in the form of increasing machine capacity. Considering machines costs, we need to determine the machine capacity that minimizes the weighted sum of the makespan and capacity costs. First, we obtain an upper bound of the ratio between the minimum makespans of two scheduling problems with different machine capacities. Second, noting the intractability of the scheduling problem without preemption, we analyze the upper bound of the ratio between the obtained makespans by heuristics of two scheduling problems with different machine capacities. Third, for the preemptive case, we develop a polynomial time algorithm to obtain the optimal machine capacity, and also present another polynomial time algorithm to obtain the optimal machine capacity as well as for bounding the approximation ratio of the non-preemptive case. Fourth, we design an approximation algorithm using machine capacity found in the preemptive case to yield a schedule for the non-preemptive case, and analyze the worst case performance ratio of the algorithm. This research provides new insights into performance improvement with increased machine capacity in parallel batch scheduling, and analyzes the trade-off between the makespan and capacity costs. (c) 2021 Elsevier Ltd. All rights reserved.

关键词： Scheduling Parallel machines Parallel batch Capacity augmentation approximation algorithm Worst case ratio

来源：评论

学校读者我要写书评

暂无评论

On dominating set of some subclasses of string graphs

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2022年 107卷

作者： Chakraborty, Dibyayan Das, Sandip Mukherjee, Joydeep Indraprastha Inst Informat Technol Delhi India Indian Stat Inst Kolkata India Ramakrishna Mission Vivekananda Educ & Res Inst Belur West Bengal India

We provide constant factor approximation algorithms for the MINIMUM DOMINATING SET (MDS) problem on several subclasses of string graphs i.e. intersection graphs of simple curves on the plane. For k & GE;0, unit B-k-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. We give an 18-approximation algorithm for the MDS problem on unit B-0-VPG graphs. This partially addresses a question of Katz et al. (2005) [24]. We also give an O (k(4))-approximation algorithm for the MDS problem on unit B-k-VPG graphs. We show that there is an 8-approximation algorithm for the MDS problem on vertically-stabbed L-graphs. We also give a 656-approximation algorithm for the MDS problem on stabbed rectangle overlap graphs. This is the first constant-factor approximation algorithm for the MDS problem on stabbed rectangle overlap graphs and extends a result of Bandyapadhyay et al. (2019) [31]. We prove some hardness results to complement the above results.(c) 2022 Elsevier B.V. All rights reserved.

关键词： Dominating set approximation algorithm Geometric intersection graph String graph

来源：评论

学校读者我要写书评

暂无评论

Approximate separable multichoice optimization over monotone systems

引用

DISCRETE OPTIMIZATION 2022年第Part1期44卷

作者： Koutecky, Martin Levin, Asaf Meesum, Syed M. Onn, Shmuel Charles Univ Prague Prague Czech Republic Technion Israel Inst Technol Haifa Israel HBNI Inst Math Sci Chennai Tamil Nadu India

With each separable optimization problem over a given set of vectors is associated its multichoice counterpart which involves choosing n rather than one solutions from the set so as to maximize the given separable function over the sum of the chosen solutions. Such problems have been studied in various contexts under various names, such as load balancing in machine scheduling, congestion routing, minimum shared and vulnerable edge problems, and shifted optimization. Separable multichoice optimization has a very broad expressive power and can be hard already for explicitly given sets of binary points. In this article we consider the problem over monotone systems, also called independence systems. Typically such a system has exponential size, and we assume that it is presented implicitly by a linear optimization oracle. Our main results for separable multichoice optimization are the following. First, the problem over any monotone system with any separable concave function can be approximated in polynomial time with a constant approximation ratio which is independent of n. Second, the problem over any monotone system with an arbitrary separable function can be approximated in polynomial time with an approximation ratio of 1/(O(log n)). (C) 2021 Elsevier B.V. All rights reserved.

关键词： Combinatorial optimization Load balancing Congestion routing Independence system Matching approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for the Maximum Happy Vertices and Edges Problems

引用

algorithmICA 2018年第5期80卷 1412-1438页

作者： Zhang, Peng Xu, Yao Jiang, Tao Li, Angsheng Lin, Guohui Miyano, Eiji Shandong Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Univ Calif Riverside Dept Comp Sci & Engn Riverside CA 92521 USA Tsinghua Univ MOE Key Lab Bioinformat Beijing 100084 Peoples R China Tsinghua Univ Bioinformat Div TNLIST Dept Comp Sci & Technol Beijing 100084 Peoples R China Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing 100190 Peoples R China Kyushu Inst Technol Dept Syst Design & Informat Iizuka Fukuoka 8208502 Japan

The Maximum Happy Vertices (MHV) problem and the Maximum Happy Edges (MHE) problem are two fundamental problems arising in the study of the homophyly phenomenon in large scale networks. Both of these two problems are NP-hard. Interestingly, the MHE problem is a natural generalization of Multiway Uncut, the complement of the classic Multiway Cut problem. In this paper, we present new approximation algorithms for MHV and MHE based on randomized LP-rounding technique and non-uniform approach. Specifically, we show that MHV can be approximated within , where is the maximum vertex degree and , and MHE can be approximated within , where is a function of the color number k. These results improve over the previous approximation ratios for MHV, MHE as well as Multiway Uncut in the literature.

关键词： Maximum Happy Vertices Maximum Happy Edges approximation algorithm Randomized rounding Network homophyly

来源：评论

学校读者我要写书评

暂无评论

Randomized approximation algorithms for planar visibility counting problem

引用

THEORETICAL COMPUTER SCIENCE 2018年 707卷 46-55页

作者： Alipour, Sharareh Ghodsi, Mohammad Jafari, Amir Inst Res Fundamental Sci IPM Sch Comp Sci Tehran Iran Sharif Univ Technol Dept Comp Engn Tehran Iran Sharif Univ Technol Dept Math Sci Tehran Iran Inst Res Fundamental Sci IPM Sch Math Tehran Iran

Given a set S of n disjoint line segments in R-2, the visibility counting problem (VCP) is to preprocess S such that the number of segments in S visible from any query point p can be computed quickly. This problem can be solved trivially in O (log n) query time using O(n(4) log n) preprocessing time and O(n(4)) space. Gudmundsson and Morin (2010) [101 proposed a 2-approximation algorithm for this problem with a tradeoff between the space and the query time. For any constant 0 <= alpha <= 1, their algorithm answers any query in O-epsilon (m((1-alpha)/2)) time with O (epsilon)(M1+alpha) of preprocessing time and space, where epsilon > 0 is a constant that can be made arbitrarily small and O-epsilon (f (n)) = O (f (n)n(epsilon)) and in m = O (n(2)) is a number that depends on the configuration of the segments. In this paper, we propose two randomized approximation algorithms for VCP. The first algorithm depends on two constants 0 <= beta <= 2/3 and 0 < delta <= 1, and the expected preprocessing time, the expected space, and the expected query time are O (m(2-3 beta/2) log m), O(m(2-3 beta/2)), and O (1/delta(2)m(beta/2) log m), respectively. The algorithm, in the preprocessing phase, selects a sequence of random samples, whose size and number depend on the tradeoff parameters. When a query point p is given by an adversary unaware of the random sample of our algorithm, it computes the number of visible segments from p, denoted by m(p), exactly, if m(p) <= 3/delta(2)m(beta/2) log(2m). Otherwise, it computes an approximated value, m(p), such that with the probability of at least 1 - 1/m, we have (1 - delta)m(p) <= m'(p) <= (2 + 2 delta)m(p). The preprocessing time and space of the second algorithm are O(n(2) log n) and O(n(2)), respectively. This algorithm computes the exact value of m(p) if m(p) <= 1/delta(2) root n log n, otherwise it returns an approximated value m ''(p) in expected O(1/delta(2)root n log n) time, such that with the probability at least 1 - 1/log n, we

关键词： Computational geometry Visibility Randomized algorithm approximation algorithm Graph theory

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Caregiver Routing and Scheduling in Home Health Care Services

Efficient Algorithms for Caregiver Routing and Scheduling in...

引用

IEEE SmartWorld, Ubiquitous Intelligence and Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Internet of People, and Smart City Innovations (SmartWorld/ScalCom/UIC/ATC/IoP/SCI)

作者： Huang, Jinyao Wu, Yalan Huang, Xinxuan Chen, Long Wu, Jigang Guangdong Univ Technol Sch Comp Sci & Technol Guangzhou 510006 Peoples R China

ISBN: (纸本)9781665412360

Caregiver routing and scheduling is one of the challenge problems in home health care services. Efficient approaches can not only reduce the operating cost but also increase the service efficiency of caregivers. The budget of patients is a critical factor for the patients to make feasible choices among different services, especially for patients with the limited budget. However, few existing works pay attention to the budget of patients. To fill this gap, we initially formulate a novel problem for caregiver routing and scheduling in home health care services by introducing a constraint based on the budget of patients. The objective of the problem is to minimize the total cost of home health care organizations. We provide the proof for its NP-hardness, followed by an approximation algorithm (APA) for the formulated problem. The strategy of the proposed algorithm directly aims to reduce the total cost of home health care organizations, by assigning the caregiver with the minimum total cost to the patient with early time for starting service. Then, we propose two heuristic algorithms, a genetic algorithm (GA) and a tabu search algorithm (TS). Simulation results show that, the proposed algorithms outperform the existing work for various cases, on the same datasets and configuration of the state-of-art work. The total cost of home health care organizations can be reduced by 45.75%, 53.01% and 57.74% on average, by APA, GA and TS, respectively.

关键词： Home health care Routing Scheduling approximation algorithm Heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Capacitated Fault-Tolerant k-Center

引用

algorithmICA 2018年第3期80卷 1041-1072页

作者： Fernandes, Cristina G. de Paula, Samuel P. Pedrosa, Lehilton L. C. Univ Sao Paulo Dept Comp Sci Sao Paulo Brazil Univ Estadual Campinas Inst Comp Campinas SP Brazil

In the -center problem, given a metric space V and a positive integer k, one wants to select k elements (centers) of V and an assignment from V to centers, minimizing the maximum distance between an element of V and its assigned center. One of the most general variants is the capacitated -fault-tolerant k-center, where centers have a limit on the number of assigned elements, and, if any centers fail, there is a reassignment from V to non-faulty centers. In this paper, we present a new approach to tackle fault tolerance, by selecting and pre-opening a set of backup centers, then solving the obtained residual instance. For the -capacitated case, we give approximations with factor 6 for the basic problem, and 7 for the so called conservative variant, when only clients whose centers failed may be reassigned. Our algorithms improve on the best previously known factors of 9 and 17, respectively. Moreover, we consider the case with general capacities. Assuming is constant, our method leads to the first approximations for this case. We also derive approximations for the capacitated fault-tolerant k-supplier problem.

关键词： Capacitated k-center Fault tolerance approximation algorithm Non-uniform capacities Linear Programming LP rounding

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for Minimum Cost Node-Connectivity Augmentation Problems

引用

THEORY OF COMPUTING SYSTEMS 2018年第3期62卷 510-532页

作者： Nutov, Zeev Open Univ Israel Raanana Israel

Let kappa (G) (s, t) denote the maximum number of pairwise internally disjoint st-paths in a graph G = (V, E). For a set of terminals, G is k-T-connected if kappa (G) (s, t) ae k for all s, t a T;if T = V then G is k-connected. Given a root node s, G is k- (T, s)-connected if kappa (G) (t, s) ae k for all t a T. We consider the corresponding min-cost connectivity augmentation problems, where we are given a graph G = (V, E) of connectivity k, and an additional edge set on V with costs. The goal is to compute a minimum cost edge set such that has connectivity k + 1. For the k-T-Connectivity Augmentation problem when is an edge set on T we obtain ratio , improving the ratio of Nutov (Combinatorica, 34(1), 95-114, 2014). For the k -Connectivity Augmentation problem we obtain the following approximation ratios. For n ae 3k - 5, we obtain ratio 3 for directed graphs and 4 for undirected graphs, improving the previous ratio 5 of Nutov (Combinatorica, 34(1), 95-114, 2014). For directed graphs and k = 1, or k = 2 and n odd, we further improve to 2.5 the previous ratios 3 and 4, respectively. For the undirected 2-(T, s)-Connectivity Augmentation problem we achieve ratio , improving the previous best ratio 12 of Nutov (ACM Trans. algorithms, 9(1), 1, 2014). For the special case when all the edges in are incident to s, we give a polynomial time algorithm, improving the ratio of Kortsarz and Nutov, (2015) and Nutov (algorithmica, 63(1-2), 398-410, 2012) for this variant.

关键词： Node-connectivity augmentation approximation algorithm Crossing biset family

来源：评论

学校读者我要写书评

暂无评论

Streaming algorithm for Submodular Cover Problem Under Noise 15

Streaming Algorithm for Submodular Cover Problem Under Noise

引用

15th RIVF International Conference on Computing and Communication Technologies (RIVF)

作者： Nguyen, Bich-Ngan T. Pham, Phuong N. H. Pham, Canh, V Su, Anh N. Snasel, Vaclav HCMC Univ Food Ind Ho Chi Minh Vietnam Peoples Secur Acad Fac Informat Secur Hanoi Vietnam Tech Univ Ostrava Ostrava Czech Republic

ISBN: (纸本)9781665404358

Submodular Cover problem has attracted the attention of researchers because of its wide variety of applications in economics, machine learning, digital marketing, and computer science. Previous studies on this problem have focused on solving it under the assumption in a non-noise environment, or using the greedy algorithm to solve under noise. However, in some applications, the data is often large scale and brings the noisy version, so the effectiveness of existing solutions is low or not applicable in large and noisy data. Motivated by this phenomenon, we study the Submodular Cover under Noise (SCN) problem and propose a single pass streaming algorithm, which provides a bicriteria approximation solution for SCN. The experiment results indicate that our algorithm provides solutions with the high value of objective functions and outperforms the-state-of-art algorithm in terms of both number of queries and running time.

关键词： Submodular Cover approximation algorithm Streaming algorithm Noise

来源：评论

学校读者我要写书评

暂无评论

Two-Stage Submodular Maximization Under Curvature 1

引用

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

作者： Li, Yanzhi Liu, Zhicheng Xu, Chuchu Li, Ping Chang, Hong Zhang, Xiaoyan Univ Sci & Technol China Sch Math Sci Hefei 230026 Anhui Peoples R China Nanjing Normal Univ Coll Taizhou Taizhou 225300 Peoples R China Nanjing Normal Univ Sch Math Sci Nanjing 210023 Jiangsu Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Jiangsu Peoples R China Huawei Technol Co Ltd Theory Lab Cent Res Inst 2012 Labs Hong Kong 9990777 Peoples R China

ISBN: (数字)9783030926816

ISBN: (纸本)9783030926816;9783030926809

Submodular function optimization has been widely studied in machine learning and economics, which is a relatively new research field in the context of big data and has attracted more attention. In this paper, we consider a two-stage submodular maximization problem subject to cardinality and p-matroid constraints, and propose an approximation algorithm with constant approximation ratio depends on the maximum curvature of the submodular functions involved, which generalizes the previous bound.

关键词： Two-stage submodular maximization Submodular term approximation algorithm Curvature

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：