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

Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection

JOURNAL OF SCHEDULING 2020年第5期23卷 525-538页

作者： Ou, Jinwen Jinan Univ Sch Management Dept Management Adm Guangzhou 510632 Peoples R China

In this paper we study a single batch-processing machine scheduling model. In our model, a set of jobs having different release dates needs to be scheduled onto a single machine that can process a batch of jobs simultaneously at a time. Each batch incurs a fixed setup time and a fixed setup cost. The decision maker may reject some of the jobs by paying penalty cost so as to achieve a tight makespan, but the total rejection penalty cost is required to be no greater than a given value. Our model extends several existing batch-processing machine scheduling models in the literature. We present efficient approximation algorithms with near-linear-time complexities.

关键词： Scheduling Batch processing Job rejection approximation algorithm Performance analysis

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the fault-tolerant facility location problem with penalties

引用

DISCRETE APPLIED MATHEMATICS 2019年 264卷 62-75页

作者： Ji, Sai Xu, Dachuan Du, Donglei Wu, Chenchen Beijing Univ Technol Coll Appl Math Dept Informat & Operat Res Beijing Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB Canada Tianjin Univ Technol Coll Sci Tianjin Peoples R China

We study the fault-tolerant facility location problem with penalties (FTFLPWP). We present an LP-rounding 4-approximation algorithm. Then we apply the randomized rounding technique to improve the approximation to 3.16, which is further improved to 2.408 by the greedy augmentation technique. (C) 2019 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Fault-tolerant Facility location problem Penalty

来源：评论

学校读者我要写书评

暂无评论

On approximating partial scenario set cover

引用

THEORETICAL COMPUTER SCIENCE 2025年 1023卷

作者： Dimant, Shai Michael Krumke, Sven O. RPTU Kaiserslautern Landau Dept Math Paul Ehrlich Str 14 D-67663 Kaiserslautern Germany

The Partial Scenario Set Cover problem (PSSC) generalizes the Partial Set Cover problem, which is itself a generalization of the classical Set Cover problem. We are given a finite ground set Q , a collection S of subsets of Q to choose from, each of which is associated with a nonnegative cost, and a second collection U of subsets of Q of which a given number l must be covered. The task is to choose a minimum cost sub-collection from S that covers at least l sets from U. PSSC is motivated by an application for locating emergency doctors. We present two approximation approaches. The first one combines LP-based rounding with a greedy consideration of the scenarios. The other is a variant of the greedy set cover algorithm, and in each iteration tries to minimize the ratio of cost to number of newly covered scenarios. We show that this subproblem, which we call Dense Scenario Set Cover (DSSC), is itself as hard to approximate as Set Cover and NP-hard, even when there is only a single scenario and all sets contain at most three elements. Furthermore, we consider a special case of DSSC where the sets are pairwise disjoint and show that in this case DSSC can be solved in polynomial time. We also provide an approximation for the general case, which we use as a subroutine in the greedy algorithm to obtain an approximation for PSSC.

关键词： Combinatorial optimization Set cover Partial cover approximation algorithm NP-hardness

来源：评论

学校读者我要写书评

暂无评论

Prize-Collecting Steiner Tree: A 1.79 approximation 2024

Prize-Collecting Steiner Tree: A 1.79 Approximation

引用

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

作者： Ahmadi, Ali Gholami, Iman Hajiaghayi, MohammadTaghi Jabbarzade, Peyman Mahdavi, Mohammad Univ Maryland College Pk MD 20742 USA

ISBN: (纸本)9798400703836

Prize-Collecting Steiner Tree (PCST) is a generalization of the Steiner Tree problem, a fundamental problem in computer science. In the classic Steiner Tree problem, we aim to connect a set of vertices known as terminals using the minimum-weight tree in a given weighted graph. In this generalized version, each vertex has a penalty, and there is flexibility to decide whether to connect each vertex or pay its associated penalty, making the problem more realistic and practical. Both the Steiner Tree problem and its Prize-Collecting version had long-standing 2-approximation algorithms, matching the integrality gap of the natural LP formulations for both. This barrier for both problems has been surpassed, with algorithms achieving approximation factors below 2. While research on the Steiner Tree problem has led to a series of reductions in the approximation ratio below 2, culminating in a ln( 4) + epsilon approximation by Byrka, Grandoni, Rothvob, and Sanita [STOC'10], the Prize-Collecting version has not seen improvements in the past 15 years since the work of Archer, Bateni, Hajiaghayi, and Karloff [FOCS'09, SIAM J. Comput.'11], which reduced the approximation factor for this problem from 2 to 1.9672. Interestingly, even the Prize-Collecting TSP approximation, which was first improved below 2 in the same paper, has seen several advancements since then (see, e.g., Blauth and Nagele [STOC'23]). In this paper, we reduce the approximation factor for the PCST problem substantially to 1.7994 via a novel iterative approach.

关键词： Steiner tree prize-collecting approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Chasing Common Knowledge: Joint Large Model Selection and Pulling in MEC With Parameter Sharing

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2025年第3期36卷 437-454页

作者： Zhou, Lizhen Xu, Zichuan Xia, Qiufen Xu, Zhou Ren, Wenhao Qi, Wenbo Ma, Jinjing Yan, Song Yang, Yuan DUT Sch Software Technol Dalian 116024 Liaoning Peoples R China DUT RU Int Sch Informat Sci & Engn Dalian 116024 Liaoning Peoples R China Ant Grp Hangzhou 310000 Zhejiang Peoples R China Alibaba Cloud Hangzhou 310030 Zhejiang Peoples R China

Pretrained Foundation Models (PFMs) are regarded as a promising accelerator for the development of various Artificial Intelligence (AI) applications, and have recently been widely fine-tuned to satisfy users' personalized inference demands. As many users are attracted to PFM-based AI applications, remote data centers are increasingly unable to solely bear the enormous computational demands and meet the delay requirements of inference requests. Mobile edge computing (MEC) offers a viable solution for delivering low-latency inference services by pulling fine-tuned PFMs from the remote data center to cloudlets in the proximity of users. However, a fine-tuned PFM typically comprises billions of model parameters, which are highly resource-intensive, time-consuming, and cost-prohibitive to execute at the edge. To address this, we investigate a novel joint large model selection and pulling problem in MEC networks. The novelty of our study lies in exploring parameter sharing among fine-tuned PFMs based on their common knowledge. Specifically, we first formulate a Non-Linear Integer Programming (NLIP) for the problem to minimize the total delay of implementing all inference requests. We then transform the NLIP into an equivalent Integer Linear Program (ILP) that is much simpler to solve. We further propose a randomized algorithm with a provable approximation ratio for the problem. We also consider the online version of the problem with uncertain request demand, and develop an online learning algorithm with a bounded regret. The crux of the online algorithm is the adoption of the multi-armed bandit technique with restricted context for dynamic admissions of inference requests. We finally conduct extensive experiments based on real datasets. Experimental results demonstrate that our algorithms reduce at least 38% in total delays and average costs, while achieving a 5% improvement in average accuracies.

关键词： Computational modeling Accuracy Delays Inference algorithms Heuristic algorithms Costs Adaptation models Context modeling approximation algorithms Load modeling Mobile edge computing (MEC) model selection model pulling approximation algorithm online learning

来源：评论

学校读者我要写书评

暂无评论

A greedy heuristic for graph burning

引用

COMPUTING 2025年第3期107卷 1-24页

作者： Garcia-Diaz, Jesus Cornejo-Acosta, Jose Alejandro Trejo-Sanchez, Joel Antonio Secretaria Ciencia Human Tecnol & Innovac Ave InsurgentesBenito Juarez Mexico City 03940 Mexico Inst Nacl Astrofis Opt & Electr Coordinac Ciencias Computac Luis Enr ErroSta Maria Tonanzintla Puebla 72840 Mexico Tecnol Nacl Mexico ITS Purisima Rincon Div Ingn Bioquim Blvd Valle Purisima Del Rincon 36425 Guanajuato Mexico Ctr Invest Matemat Km 5 5 Carretera Sierra Papacal Chuburna Puerto Merida 97302 Yucatan Mexico

Given a graph G, the optimization version of the graph burning problem seeks for a sequence of vertices, (u1,u2,...,up)is an element of V(G)p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(u_1,u_2,...,u_p) \in V(G)<^>p$$\end{document}, with minimum p and such that every v is an element of V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v \in V(G)$$\end{document} has distance at most p-i\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p-i$$\end{document} to some vertex ui\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u_i$$\end{document}. The length p of the optimal solution is known as the burning number and is denoted by b(G), an invariant that helps quantify the graph's vulnerability to contagion. This paper explores the advantages and limitations of an O(mn+pn2)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal {O}}(mn + pn<^>2)$$\end{document} deterministic greedy heuristic for this problem, where n is the graph's order, m is the graph's size, and p is a guess on b(G). This heuristic is based on the relationship between the graph burning problem and the clust

关键词： Graph burning Clustered maximum coverage approximation algorithm Greedy heuristic Social contagion

来源：评论

学校读者我要写书评

暂无评论

Submodular batch scheduling on parallel machines

引用

NAVAL RESEARCH LOGISTICS 2025年第2期72卷 242-259页

作者： Sun, Tao Wang, Jun-Qiang Fan, Guo-Qiang Liu, Zhixin Northwestern Polytech Univ Performance Anal Ctr Prod & Operat Syst PacPos Xian Peoples R China Northwestern Polytech Univ Sch Mech Engn Dept Ind Engn Xian 710072 Shaanxi Peoples R China Xidian Univ Sch Econ & Management Dept Management Sci & Engn Xian Peoples R China Univ Michigan Dearborn Coll Business Dept Informat & Operat Management Dearborn MI USA

This article studies a submodular batch scheduling problem motivated by the vacuum heat treatment. The batch processing time is formulated by a monotone nondecreasing submodular function characterized by decreasing marginal gain property. The objective is to minimize the makespan. We show the NP-hardness of the problem on a single machine and of finding a polynomial-time approximation algorithm with the worst-case performance ratio strictly less than 65$$ \frac{6}{5} $$ for the problem on parallel machines. We introduce a bounded interval to model the batch processing time using two parameters, that is, the total curvature and the quantization indicator. Based on the decreasing marginal gain property and the two parameters, we make a systematic analysis of the full batch longest processing time algorithm and the longest processing time greedy algorithm, and propose the instances with the bound of batch capacity b$$ b $$ for these two algorithms for the submodular batch scheduling problem. Moreover, we prove the submodularity of batch processing time function of the existing batch models including the parallel batch, serial batch, and mixed batch models. We compare the worst-case performance ratios in the existing batch models with those deduced from our work in the submodular batch model. In most situations, the worst-case performance ratios deduced from our work are comparable to the best-known worst-case performance ratios with tailored examinations.

关键词： approximation algorithm batch machine scheduling submodular function worst-case performance ratio

来源：评论

学校读者我要写书评

暂无评论

Uav trajectory optimization for maximizing the ToI-based data utility in wireless sensor networks

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2025年第3期49卷 1-25页

作者： Zhao, Qing Li, Zhen Li, Jianqiang Guo, Jianxiong Ding, Xingjian Li, Deying Beijing Univ Technol Coll Comp Sci Beijing Peoples R China Beijing Normal Univ Adv Inst Nat Sci Zhuhai Peoples R China BNU HKBU United Int Coll Guangdong Key Lab AI & Multimodal Data Proc Zhuhai Peoples R China Renmin Univ China Sch Informat Beijing Peoples R China

It's a promising way to use Unmanned Aerial Vehicles (UAVs) as mobile base stations to collect data from sensor nodes, especially for large-scale wireless sensor networks. There are a lot of works that focus on improving the freshness of the collected data or the data collection efficiency by scheduling UAVs. Given that sensing data in certain applications is time-sensitive, with its value diminishing as time progresses based on Timeliness of Information (ToI), this paper delves into the UAV Trajectory optimization problem for Maximizing the ToI-based data utility (TMT). We give the formal definition of the problem and prove its NP-Hardness. To solve the TMT problem, we propose a deep reinforcement learning-based algorithm that combines the Action Rejection Mechanism and the Deep Q-Network with Priority Experience Replay (ARM-PER-DQN). Where the action rejection mechanism could reduce the action space and PER helps improve the utilization of experiences with high value, thus increasing the training efficiency. To avoid the unbalanced data collection problem, we also investigate a variant problem of TMT (named V-TMT), i.e., each sensor node can be visited by the UAV at most once. We prove that the V-TMT problem is also NP-Hard, and propose a 2-approximation algorithm as the baseline of the ARM-PER-DQN algorithm. We conduct extensive simulations for the two problems to validate the performance of our designs, and the results show that our ARM-PER-DQN algorithm outperforms other baselines, especially in the V-TMT problem, the ARM-PER-DQN algorithm always outperforms the proposed 2-approximation algorithm, which suggests the effectiveness of our algorithm.

关键词： Data collection Trajectory optimization Deep reinforcement learning approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Desynchronized Wake-Up algorithm for Energy Efficient EPON-Based 5G Backhaul

引用

JOURNAL OF LIGHTWAVE TECHNOLOGY 2025年第10期43卷 4516-4529页

作者： Dutta, Sourav Roy, Dibbendu Das, Goutam Indian Inst Technol Kharagpur GS Sanyal Sch Telecommun Kharagpur 721302 India KTH Royal Inst Technol Dept Sch Elect Engn & Comp Sci S-11428 Stockholm Sweden

This paper focuses on enhancing the energy savings of EPON-based backhaul for 5G and beyond networks. Here, we introduce a novel technique of the desynchronization of wake-up cycles among Optical Network Units (ONUs) in Low-Power Mode (LPM). In this technique, the Optical Line Terminal (OLT) decides the wake-up slots of all ONUs such that they are spread out and staggered, maximizing the likelihood of fewer ONUs waking up simultaneously. We have shown that this technique can be implemented in addition to any of the existing protocols to improve the energy savings of the protocol. We formulate an optimization problem to achieve wake-up desynchronization while ensuring latency requirements. To address this problem, we present a polynomial-time 1-approximation algorithm. The convergence and complexity of the algorithm are analyzed. Through simulations, we illustrate a significant increase in energy savings and a reduction in the probability of delay violation by implementing our proposed method.

关键词： Optical network units Energy conservation Protocols X reality Standards IEEE 802.3 Standard EPON approximation algorithm extended reality energy-efficiency 5G-backhaul XR

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for querying incomplete databases

引用

INFORMATION SYSTEMS 2019年 86卷 28-45页

作者： Greco, Sergio Molinaro, Cristian Trubitsyna, Irina Univ Calabria DIMES Calabria Italy

Certain answers are a widely accepted semantics of query answering over incomplete databases. As their computation is a coNP-hard problem, recent research has focused on developing (polynomial time) evaluation algorithms with correctness guarantees, that is, techniques computing a sound but possibly incomplete set of certain answers. The aim is to make the computation of certain answers feasible in practice, settling for under-approximations. In this paper, we present novel evaluation algorithms with correctness guarantees, which provide better approximations than current techniques, while retaining polynomial time data complexity. The central tools of our approach are conditional tables and the conditional evaluation of queries. We propose different strategies to evaluate conditions, leading to different approximation algorithms- more accurate evaluation strategies have higher running times, but they pay off with more certain answers being returned. Thus, our approach offers a suite of approximation algorithms enabling users to choose the technique that best meets their needs in terms of balance between efficiency and quality of the results. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Incomplete database Certain query answer approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：