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

SINGLE-MACHINE SCHEDULING WITH COUPLED TASK AND REJECTION

MATHEMATICAL FOUNDATIONS OF COMPUTING 2024年第3期7卷 328-335页

作者： Kong, Fanyu Miao, Cuixia Huo, Yujia Song, Jiaxin Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China

We consider the single-machine scheduling with coupled task and rejection, in which each coupled task is either accepted and processed on a single machine or rejected with a certain rejection penalty. Each accepted coupled task Ja is made of two tasks with processing times aa and ba, respectively, and a fixed exactly time interval La between the two tasks is required. The objective is to minimize the makespan of the accepted coupled task and the total penalty of the rejected coupled task. We present 3-approximation algorithm for the cases of aa = La = p and ba = La = p, respectively, and prove that the problems with common ba or common aa is polynomially solvable. Furthermore, when aa = ba = p, we provide a 2-approximation algorithm for La > p and show that the problem with for La & LE;p can be solved in polynomial time.

关键词： Single-machine scheduling coupled task rejection approximation algorithm polynomially solvable

来源：评论

学校读者我要写书评

暂无评论

Two-agent scheduling in a two-machine open shop

引用

ANNALS OF OPERATIONS RESEARCH 2024年第1期333卷 275-301页

作者： Liu, Peihai Gu, Manzhan Lu, Xiwen East China Univ Sci & Technol Sch Math Shanghai Peoples R China Shanghai Univ Finance & Econ Sch Math Shanghai 200433 Peoples R China

This paper considers several two-machine open shop problems with two agents. Each agent has an independent set of nonpreemptive jobs, and the objective is to find either a schedule minimizing a linear combination of the makespans of both agents, a schedule minimizing the makespan of one agent with the makespan of the other agent not exceeding a threshold, or all Pareto-optimal schedules with respect to the makespans of both agents. We present a number of results for the problems above, including a polynomial algorithm and a pseudo-polynomial algorithm for special cases, non-approximability, two approximation algorithms, and a fully polynomial-time approximation scheme. Finally, we run numerical experiments to show the effectiveness of the pseudo-polynomial algorithm and the approximation algorithms.

关键词： Scheduling Two-agent Open shop approximation algorithm FPTAS

来源：评论

学校读者我要写书评

暂无评论

Maximization of k-Submodular Function with d-Knapsack Constraints Over Sliding Window

引用

Tsinghua Science and Technology 2025年第2期30卷 488-498页

作者： Wenqi Wang Yuefang Sun Zhiren Sun Donglei Du Xiaoyan Zhang School of Mathematical Science&Institute of Mathematics Nanjing Normal UniversityNanjing 210023China Key Laboratory of Ministry of Education Numerical Simulation of Large Scale Complex Systems Nanjing 210023China School of Mathematics and Statistics Ningbo UniversityNingbo 315211China Faculty of Management University of New BrunswickFredericton E3B9Y2Canada

Submodular function maximization problem has been extensively studied recently.A natural variant of submodular function is k-submodular function,which has many applications in real life,such as influence maximization and sensor placement *** domain of a k-submodular function has k disjoint subsets,and hence includes submodular function as a special case when k=*** work investigates the k-submodular function maximization problem with d-knapsack constraints over the sliding *** on the smooth histogram technique,we design a deterministic approximation ***,we propose a randomized algorithm to improve the approximation ratio.

关键词： k-submodular function d-knapsack constraints sliding window streaming algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Two parallel-machine scheduling with maximum waiting time for an emergency job

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年第16期62卷 6016-6027页

作者： Jiang, Yiwei Yuan, Haodong Zhou, Ping Cheng, T. C. E. Ji, Min Zhejiang Gongshang Univ Contemporary Business & Trade Res Ctr Sch Management & E Business Hangzhou 310018 Peoples R China Zhejiang Business Coll Coll Humanities Hangzhou Peoples R China Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China

In modern manufacturing and service industries, urgent orders and service tasks are common, and the speed of handling such urgent tasks is an important indicator of production and service efficiency. In this study, we consider scheduling jobs on two parallel machines with the random arrival of an emergency job. The objective is to minimise the makespan, subject to a given maximum waiting time of the emergency job. We first show that the worst-case ratio of the existing algorithm LPTl-SPTm-l is at least 3/2 when m = 2. We then analyse some properties of the optimal schedule and derive lower bounds on the optimal makespan. Finally, we present an improved approximation algorithm with a tight worst-case ratio of 4/3. We also provide numerical results showing that our proposed algorithm outperforms algorithm LPTl-SPTm-l.

关键词： Parallel machines emergency job makespan approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithm for the k-Means Problem with Must-Link and Cannot-Link Constraints

引用

Tsinghua Science and Technology 2023年第6期28卷 1050-1062页

作者： Chaoqi Jia Longkun Guo Kewen Liao Zhigang Lu Faculty of Computer Science and Technology Qilu University of Technology(Shandong Academy of Sciences)Jinan 250353China HilstLab Peter Faber Business SchoolAustralian Catholic UniversitySydney 2060Australia Macquarie University Cyber Security Hub Macquarie UniversitySydney 2109Australia

Constrained clustering,such as k-means with instance-level Must-Link(ML)and Cannot-Link(CL)auxiliary information as the constraints,has been extensively studied recently,due to its broad applications in data science and *** some heuristic approaches,there has not been any algorithm providing a non-trivial approximation ratio to the constrained k-means *** address this issue,we propose an algorithm with a provable approximation ratio of O(logk)when only ML constraints are *** also empirically evaluate the performance of our algorithm on real-world datasets having artificial ML and disjoint CL *** experimental results show that our algorithm outperforms the existing greedy-based heuristic methods in clustering accuracy.

关键词： Constrained k-means Must-Link(ML)and Cannot-Link(CL)constraints approximation algorithm constrained clustering

来源：评论

学校读者我要写书评

暂无评论

A Polynomial-Time approximation Scheme for Thief Orienteering on Directed Acyclic Graphs 1

引用

34th International Workshop on Combinatorial algorithms (IWOCA)

作者： Bloch-Hansen, Andrew Page, Daniel R. Solis-Oba, Roberto Western Univ Dept Comp Sci London ON Canada PageWizard Games Learning & Entertainment Sunnyside MB Canada Univ Regina Dept Comp Sci Regina SK Canada

ISBN: (数字)9783031343476

ISBN: (纸本)9783031343469;9783031343476

We consider the scenario of routing an agent called a thief through a weighted graph G = (V, E) from a start vertex s to an end vertex t. A set I of items each with weight wi and profit p(i) is distributed among V \ {s, t}. In the thief orienteering problem, the thief, who has a knapsack of capacity W, must follow a simple path from s to t within a given time T while packing in the knapsack a set of items, taken from the vertices along the path, of total weight at most W and maximum profit. The travel time across an edge depends on the edge length and current knapsack load. The thief orienteering problem is a generalization of the orienteering problem and the 0-1 knapsack problem. We present a polynomial-time approximation scheme (PTAS) for the thief orienteering problem when G is directed and acyclic, and adapt the PTAS for other classes of graphs and special cases of the problem. In addition, we prove there exists no approximation algorithm for the thief orienteering problem with constant approximation ratio, unless P= NP.

关键词： thief orienteering problem knapsack problem dynamic programming approximation algorithm approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Joint Optimization of Coverage and Reliability for Application Placement in Mobile Edge Computing

引用

IEEE TRANSACTIONS ON SERVICES COMPUTING 2023年第6期16卷 3946-3957页

作者： Chen, Feifei Zhou, Jingwen Xia, Xiaoyu Xiang, Yong Tao, Xuehong He, Qiang Deakin Univ Sch Informat Technol Geelong Vic 3217 Australia RMIT Univ Sch Comp Technol Melbourne Vic 3001 Australia Swinburne Univ Technol Dept Comp Technol Melbourne Vic 3122 Australia Huazhong Univ Sci & Technol Serv Comp Technol & Syst Lab Natl Engn Res Ctr Big Data Technol & Syst Sch Comp Sci & TechnolCluster & Grid Comp Lab Wuhan 430074 Peoples R China

Mobile edge computing (MEC) provides a new distributed computing paradigm that overcomes the inability of cloud computing to offer low end-to-end latency. In a MEC environment, app vendors can deliver lower-latency services to mobile app users by placing applications on edge servers in close proximity to app users. From an app vendor's perspective, an optimal edge application placement strategy under a budget (k) constraint aims to place application instances on k edge servers within a specific area to maximize user coverage. However, edge servers may be subject to failure due to multiple reasons, e.g., hardware faults, software exceptions, cyber-attacks, etc. App users served by failed edge servers need to access applications from remote cloud servers if they cannot access any other edge servers. This impacts app users' quality of experience significantly. Thus, app vendors need to consider the reliability of the edge server network when choosing edge servers for placing their application instances. We make the first attempt in this paper to tackle this problem of joint optimization of coverage and reliability for edge application placement (EAP-CR). We formulate this problem as a constrained optimization problem and prove its NP-hardness theoretically. Then, we propose an optimal approach to find the optimal solutions with the integer programming technique, an approximation approach is also proposed to find approximate solutions for large-scale EAP-CR problems. We evaluate EAP-OPT and EAP-APX against three relevant approaches through experiments conducted on a widely-used real-world data set and a synthetic data set. The results demonstrate that our proposed approaches can solve the EAP-CR problem effectively and efficiently.

关键词： Application placement application reliability approximation algorithm integer programming low-latency services mobile edge computing optimization

来源：评论

学校读者我要写书评

暂无评论

Complexity of Near-3-Choosability Problem

引用

GRAPHS AND COMBINATORICS 2024年第6期40卷 1-19页

作者： Mishra, Sounaka Rohini, S. Sawant, Sagar S. Indian Inst Technol Madras Dept Math Chennai 600036 Tamil Nadu India

It is currently an unsolved problem to determine whether, for every 2-list assignment L of a Delta-free planar graph G, there exists an independent set AL L such that G[V-G\A(L)] is L-colorable. However, in this paper, we take a slightly different approach to the above problem. We prove the NP-completeness of the decision problem of determining an independent set A such that G[V-G\A(L)] is 2-choosable for Delta-free, 4-colorable graphs of diameter 3. Building upon this notion, we examine the computational complexity of two optimization problems: minimum near-3-choosability and minimum 2-choosable-edge-deletion. In the former problem, the goal is to find an independent set A of minimum size in a given graph G , such that the induced subgraph G[V-G\A] is 2choosable. We establish that this problem is NP-hard to approximate within a factor of |V-G|(1-epsilon) for any epsilon > 0, for planar bipartite graphs of arbitrary large girth. On the other hand, the problem of minimum 2-choosable-edge-deletion involves determining an edge set F subset of E-G of minimum cardinality such that the spanning subgraph G[E-G\F] is 2-choosable. We prove that this problem can be approximated within a factor of O (log |V-G|) .

关键词： Graph coloring List coloring NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Determining cost-efficient controls of electrical energy storages using dynamic programming

引用

JOURNAL OF MATHEMATICS IN INDUSTRY 2024年第1期14卷 2页

作者： Stiglmayr, Michael Uhlemeyer, Svenja Uhlemeyer, Bjoern Zdrallek, Markus Univ Wuppertal Sch Math & Nat Sci IZMD Wuppertal Germany Univ Wuppertal Sch Elect Informat & Media Engn Wuppertal Germany

Volatile electrical energy prices are a challenge and an opportunity for small and medium-sized companies in energy-intensive industries. By using electrical energy storage and/or an adaptation of production processes, companies can significantly profit from time-depending energy prices and reduce their energy *** consider a time-discrete optimal control problem to reach a desired final state of the energy storage at a certain time step. Thereby, the energy input is discrete since only multiples of 100 kWh can be purchased at the EPEX SPOT market. We use available price estimates to minimize the total energy cost by a rounding based dynamic programming approach. With our model non-linear energy loss functions of the storage can be considered and we obtain a significant speed-up compared to the integer (linear) programming formulation.

关键词： Discrete control problem Rounding-based dynamic programming Volatile energy market approximation algorithm Mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

Scalable Pythagorean Mean-based Incident Detection in Smart Transportation Systems

引用

ACM TRANSACTIONS ON CYBER-PHYSICAL SYSTEMS 2024年第2期8卷 1-25页

作者： Islam, Md. Jaminur Talusan, Jose Paolo Bhattacharjee, Shameek Tiausas, Francis Dubey, Abhishek Yasumoto, Keiichi Das, Sajal K. Western Michigan Univ 1903 WesternMichigan Ave Kalamazoo MI 49008 USA Vanderbilt Univ 2201 West End Ave Nashville TN 37212 USA Nara Inst Sci & Technol Nara 6300192 Japan Missouri Univ Sci & Technol Rolla MO 65401 USA

Modern smart cities need smart transportation solutions to quickly detect various traffic emergencies and incidents in the city to avoid cascading traffic disruptions. To materialize this, roadside units and ambient transportation sensors are being deployed to collect speed data that enables the monitoring of traffic conditions on each road segment. In this article, we first propose a scalable data-driven anomaly-based traffic incident detection framework for a city-scale smart transportation system. Specifically, we propose an incremental region growing approximation algorithm for optimal Spatio-temporal clustering of road segments and their data;such that road segments are strategically divided into highly correlated clusters. The highly correlated clusters enable identifying a Pythagorean Mean-based invariant as an anomaly detection metric that is highly stable under no incidents but shows a deviation in the presence of incidents. We learn the bounds of the invariants in a robust manner such that anomaly detection can generalize to unseen events, even when learning from real noisy data. Second, using cluster-level detection, we propose a folded Gaussian classifier to pinpoint the particular segment in a cluster where the incident happened in an automated manner. We perform extensive experimental validation using mobility data collected from four cities in Tennessee and compare with the state-of-the-art ML methods to prove that our method can detect incidents within each cluster in real-time and outperforms known ML methods.

关键词： Weakly unsupervised learning anomaly detection smart transportation graph algorithms cluster analysis regression incident detection approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：