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

23rd IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGrid)

作者： Vasconcelos, Miguel Cordeiro, Daniel Da Costa, Georges Dufosse, Fanny Nicod, Jean-Marc Rehn-Sonigo, Veronika Univ Sao Paulo Sch Arts Sci & Humanities Sao Paulo Brazil Univ Toulouse CNRS IRIT UMR 5505 Toulouse France Univ Grenoble Alpes CNRS INRIA Grenoble INPLIG Grenoble France Univ Bourgogne Franche Comte CNRS FEMTO ST Inst ENSMM Besancon France

ISBN: (纸本)9798350301199

The carbon footprint of IT technologies has been a significant concern in recent years. This concern mainly focuses on the electricity consumption of data centers;many cloud suppliers commit to using 100% of renewable energy sources. However, this approach neglects the impact of device manufacturing. We consider in this paper the question of dimensioning the renewable energy sources of a geographically distributed cloud with considering the carbon impact of both the grid electricity consumption in the considered locations and the manufacturing of solar panels and batteries. We design a linear program to optimize cloud dimensioning over one year, considering worldwide locations for data centers, real-life workload traces, and solar irradiation values. Our results show a carbon footprint reduction of about 30% compared to a cloud fully supplied by solar energy and of 85% compared to the 100% grid electricity model.

关键词： cloud computing renewable energy energy storage linear program job scheduling follow-the-sun green computing

来源：评论

学校读者我要写书评

暂无评论

A note on LP-based approximation algorithms for capacitated facility location problem

引用

THEORETICAL COMPUTER SCIENCE 2022年 932卷 31-40页

作者： Miao, Runjie Yuan, Jinjiang Zhengzhou Univ Sch Math & Stat Zhengzhou 450001 Henan Peoples R China

In the capacitated facility location problem, we are given a set F of potential facilities and a set D of clients, where each facility has a capacity and an open cost, and each client has a demand to be served by the facilities with service costs. The goal is to open some facilities in F and assign all clients in D to these open facilities such that the total cost is minimum. Based on the natural integer programming formulation, Levi et al. [8] presented an LP-based 5-approximation algorithm for this problem under the assumption that the facility costs are uniform. Based on the same integer programming formulation, we remove the uniformity assumption and present an ( R+root R-2+8R/2 + 3)-approximation algorithm for the capacitated facility location problem, where R is the upper bound of the ratio between facility costs. Our result is a slight extension of the corresponding result in [8], as when R = 1 the worst-case ratio of our algorithm is R+root R-2+8R/2 + 3 = 5. (c) 2022 Elsevier B.V. All rights reserved.

关键词： linear program Approximation algorithm Capacitated facility location problem

来源：评论

学校读者我要写书评

暂无评论

An improved primal-dual approximation algorithm for the k-means problem with penalties

引用

MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE 2022年第2期32卷 151-163页

作者： Ren, Chunying Xu, Dachuan Du, Donglei Li, Min Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

In the k-means problem with penalties, we are given a data set D subset of R-l of n points where each point j is an element of D is associated with a penalty cost p(j) and an integer k. The goal is to choose a set CS subset of R-l with vertical bar CS vertical bar <= k and a penalized subset D-p subset of D to minimize the sum of the total squared distance from the points in D\D-p to CS and the total penalty cost of points in D-p, namely Sigma(j is an element of D\Dp) d(2)(j, CS)+ Sigma(j is an element of Dp) p(j). We employ the primaldual technique to give a pseudo-polynomial time algorithm with an approximation ratio of (6.357+ epsilon) for the k-means problem with penalties, improving the previous best approximation ratio 19.849 + epsilon for this problem given by Feng et al. in Proceedings of FAW(2019).

关键词： K-means problem with penalties linear program approximation algorithm JV algorithm

来源：评论

学校读者我要写书评

暂无评论

An LP-based Online Dispatching Method with Privacy-preserving in Online Ride-hailing

An LP-based Online Dispatching Method with Privacy-preservin...

引用

IEEE Conference on Global Communications (IEEE GLOBECOM) - Intelligent Communications for Shared Prosperity

作者： Chen, Xinyu Xu, Evan Yifan Tao, Jun Chen, Rujie Southeast Univ Sch Cyber Sci & Engn Nanjing 211189 Jiangsu Peoples R China Southeast Univ Key Lab CNII MOE Nanjing 211189 Jiangsu Peoples R China Purple Mt Labs Network & Commun Secur Nanjing 211111 Jiangsu Peoples R China

ISBN: (纸本)9798350310900

While ride-hailing brings great convenience to our daily life, it also poses a threat to the passengers' location privacy. Although many perturbation-based methods have been proposed to protect the passengers' location privacy, imprecise can still result in poor assignments of the ride-hailing platform. In addition, the platform often has to balance multiple conflicting objectives when dispatching drivers. Thus, trading these objectives in an appropriate way is critical to the long-term development of the platform. In this paper, we focus on the assignment strategy design in ride-hailing, aiming to promote the performance of the dispatching system while protecting the passengers' location privacy. We first model the online order dispatching as a bipartite matching problem, where drivers are assumed to be offline available and orders arrive sequentially following a known distribution. Then, we construct several linear programs (LPs) to obtain the obfuscation matrix (for privacy-preserving) and the guiding solutions of assignments (for online dispatching). Finally, a parameterized LP-based online dispatching algorithm is proposed to flexibly trade the two assignment objectives, i.e., dispatch efficiency and fairness. Experimental results on real-world datasets demonstrate the effectiveness of our algorithms.

关键词： privacy-preserving ride-hailing online dispatching linear program tradeoff

来源：评论

学校读者我要写书评

暂无评论

Solving Tall Dense linear programs in Nearly linear Time 2020

Solving Tall Dense Linear Programs in Nearly Linear Time

引用

52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： van den Brand, Jan Lee, Yin Tat Sidford, Aaron Song, Zhao KTH Royal Inst Technol Stockholm Sweden Univ Washington Seattle WA 98195 USA MSR Redmond Redmond WA USA Stanford Univ Stanford CA 94305 USA Princeton Univ Princeton NJ 08544 USA Inst Adv Study Olden Lane Princeton NJ 08540 USA

ISBN: (纸本)9781450369794

In this paper we provide an (O) over tilde (nd + d(3)) time randomized algorithm for solving linear programs with d variables and n constraints with high probability. To obtain this result we provide a robust, primaldual (O) over tilde(root d)-iteration interior point method inspired by the methods of Lee and Sidford (2014, 2019) and show how to efficiently implement this method using new data-structures based on heavy-hitters, the Johnson Lindenstrauss lemma, and inverse maintenance. Interestingly, we obtain this running time without using fast matrix multiplication and consequently, barring a major advance in linear system solving, our running time is near optimal for solving dense linear programs among algorithms that do not use fast matrix multiplication.

关键词： linear program interior point method nearly linear time

来源：评论

学校读者我要写书评

暂无评论

The joint maintenance operation selection and technician routing problem

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 167卷

作者： Delavernhe, Florian Castanier, Bruno Gueret, Christelle Mendoza, Jorge E. Univ Bourgogne Lab DRIVE Nevers France Univ Angers LARIS SFR MATHST F-49000 Angers France HEC Montreal CIRRELT Montreal PQ Canada

Numerous studies have explored the challenge of optimizing maintenance grouping, aiming to efficiently manage maintenance resources and reduce costs associated with various maintenance opportunities. Maintenance grouping is even more important when the systems to maintain are geographically distributed because it significantly reduces travel costs. In this research, we tackle a novel problem that integrates condition -based maintenance with the selection of maintenance operations and technician routing. The problem involves the selection of machines requiring maintenance for each time period, determining the nature of required operations (based on the uncertain degradation state of the machines), selecting suitable technicians based on their skills and availability, and planning their routes. We formulate this problem as a mixed -integer program and propose a heuristic approach for its solution. Our method constructs a solution by iteratively adding maintenance operations to technician routes. To assess the method's performance, we conduct experiments that evaluate both running times and solution quality.

关键词： Maintenance Combinatorial optimization Technician routing Heuristic linear program

来源：评论

学校读者我要写书评

暂无评论

Scheduling Cluster Tools with Multi-Space Process Modules and a Multi-Finger-Arm Robot in Wafer Fabrication Subject to Wafer Residency Time Constraints

引用

APPLIED SCIENCES-BASEL 2024年第20期14卷 9490页

作者： Gu, Lei Wu, Naiqi Qiao, Yan Zhang, Siwei Li, Tan Macau Univ Sci & Technol Fac Innovat Engn Dept Engn Sci Taipa 999078 Macao Peoples R China

To increase productivity, more sophisticated cluster tools are developed. To achieve this, one of the ways is to increase the number of spaces in a process module (PM) and the number of fingers on a robot arm as well, leading to a cluster tool with multi-space PMs and a multi-finger-arm robot. This paper discusses the scheduling problem of cluster tools with four-space PMs and a four-finger-arm robot, a typical tool with multi-space PMs and a multi-finger-arm robot adopted in modern fabs. With two arms in such a tool, one is used as a clean one, while the other is used as a dirty one. In this way, wafer quality can be improved. However, scheduling such cluster tools to ensure the residency time constraints is very challenging, and there is no research report on this issue. This article conducts an in-depth analysis of the steady-state scheduling for this type of cluster tools to explore the effect of different scheduling strategies. Based on the properties, four robot task sequences are presented as scheduling strategies. With them, four linear programming models are developed to optimize the cycle time of the system and find feasible schedules. The performance of these strategies is dependent on the activity parameters. Experiments are carried out to test the effect of different parameters on the performance of different strategies. It shows that, given a group of parameters, one can apply all the strategies and choose the best result obtained by one of the strategies.

关键词： semiconductor manufacturing cluster tools scheduling linear program

来源：评论

学校读者我要写书评

暂无评论

Flow Time Scheduling and Prefix Beck-Fiala 2022

Flow Time Scheduling and Prefix Beck-Fiala

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Bansal, Nikhil Rohwedder, Lars Svensson, Ola Univ Michigan Ann Arbor MI 48109 USA Maastricht Univ Maastricht Netherlands Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9781450392648

We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines. Specifically, we give a general reduction that allows us to transfer discrepancy bounds in the prefix Beck-Fiala (bounded iota 1-norm) setting to bounds on the flow time of an optimal schedule. Combining our reduction with a deep result proved by Banaszczyk via convex geometry, give guarantees of O(root logn) and O( root logn logp) for max flow time and total flow time, respectively, improving upon the previous best guarantees of O(logn) and O( log n log p). Apart from the improved guarantees, the reduction motivates seemingly easy versions of prefix discrepancy questions: any constant bound on prefix Beck-Fiala where vectors have sparsity two (sparsity one being trivial) would already yield tight guarantees for both max flow time and total flow time. While known techniques solve this case when the entries take values in {-1, 0, 1}, we show that they are unlikely to transfer to the more general 2-sparse case of bounded iota 1-norm.

关键词： integrality gap discrepancy linear program

来源：评论

学校读者我要写书评

暂无评论

An LP-rounding based algorithm for a capacitated uniform facility location problem with penalties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第4期41卷 888-904页

作者： Lv, Wei Wu, Chenchen Tianjin Renai Coll Comp Sci & Technol Dept Tianjin 306136 Peoples R China Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China

Facility location problem is a well established research area within Operations Research. Capacitated facility location problem is one of the most important variants, in which each facility has an upper bound on the demand, i.e., capacity. Moreover, the integrality gap of the natural linear program relaxation for the problem is infinite. Fortunately, the gap is finite when all opening costs for the facilities are the same. We consider a capacity facility location problem with penalties in which it is allowed some customers are not served by facilities and all opening costs are uniform. Based on LP-rounding framework, we propose a 5.732-approximation algorithm.

关键词： Capacitated facility location problem Approximation algorithm linear program

来源：评论

学校读者我要写书评

暂无评论

Using Feedback Functions in linear programming Problems

引用

COMPUTATIONAL MATHEMATICS AND MATHEMATICAL PHYSICS 2019年第10期59卷 1626-1638页

作者： Umnov, A. E. Umnov, E. A. Moscow Inst Phys & Technol Dolgoprudnyi 141700 Moscow Oblast Russia

A scheme for solving linear programming problems based on the use of auxiliary functions that implement feedback in the system of constraints imposed on the variables to be found and on the Lagrange multipliers is pro... 详细信息

关键词： linear program penalty function method feedback functions modified Lagrangian function regularization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：