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

Cyclic lot-sizing problems with sequencing costs

JOURNAL OF SCHEDULING 2021年第2期24卷 123-135页

作者： Grigoriev, Alexander Kreuzen, Vincent J. Oosterwijk, Tim Maastricht Univ Maastricht Netherlands

We study a single-machine lot-sizing problem, where n types of products need to be scheduled on the machine. Each product is associated with a constant demand rate, maximum production rate and inventory costs per time unit. Every time when the machine switches production between products, sequencing costs are incurred. These sequencing costs depend both on the product the machine just produced and on the product the machine is about to produce. The goal is to find a cyclic schedule minimizing total average costs, subject to the condition that all demands are satisfied. We establish the complexity of the problem, and we prove a number of structural properties largely characterizing optimal solutions. Moreover, we present two algorithms approximating the optimal schedules by augmenting the problem input. Due to the high-multiplicity setting, even trivial cases of the corresponding conventional counterparts become highly non-trivial with respect to the output sizes and computational complexity, even without sequencing costs. In particular, the length of an optimal solution can be exponential in the input size of the problem. Nevertheless, our approximation algorithms produce schedules of a polynomial length and with a good quality compared to the optimal schedules of exponential length.

关键词： Lot-sizing problem Sequencing costs High multiplicity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Connectivity-Constrained Placement of Wireless Chargers

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2021年第3期20卷 909-927页

作者： Yu, Nan Dai, Haipeng Chen, Guihai Liu, Alex X. Tian, Bingchuan He, Tian Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Peoples R China Nanjing Univ Dept Comp Sci & Technol Nanjing 210023 Peoples R China Univ Minnesota Dept Comp Sci & Engn Minneapolis MN 55455 USA

In this article, we first study the problem of Connected wIReless Charger pLacEment (CIRCLE). That is, given a fixed number of directional wireless chargers and candidate positions, determining the placement position and orientation angle for each charger under connectivity constraint for wireless chargers such that the overall charging utility is maximized. To address CIRCLE problem, we first consider a relaxed version of CIRCLE (CIRCLE-R for short). We prove that CIRCLE-R falls into the realm of maximizing a submodular set function subject to a connectivity constraint, and propose an algorithm whose approximation ratio is at least 1.5 times better than that of the state-of-the-art algorithm. Next, we reduce the solution space for CIRCLE from infinite to finite, and propose an algorithm with a constant approximation ratio to address CIRCLE. Besides, we consider a variant of CIRCLE, CIRCLE-NB, and propose an approximation algorithm to address it. We conduct both simulation experiments and field experiments to verify our theoretical findings. The results show that our algorithm can outperform comparison algorithms by 83.35 percent.

关键词： Connectivity directional charging wireless power transfer approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Combinatorial Optimization and Decision-Making with Applications in Computational Sustainability

Combinatorial Optimization and Decision-Making with Applicat...

引用

作者： Shi, Qinru Cornell University

学位级别：Ph.D., Doctor of Philosophy

Combinatorial optimization and decision-making problems are critical in many real-world computational sustainability problems. The main goals for these projects are often to provide decision-support tools for various groups and institutions to help solve complex computation problems encountered in sustainable planning and development. This thesis mainly focuses on two real-world applications of combinatorial optimization and decision-making in computational sustainability. The first is a multiobjective optimization problem inspired by the real-world problem of placing hydropower dams in the Amazon basin. We propose a fully polynomial-time approximation scheme based on Dynamic Programming (DP) for computing the Pareto frontier within an arbitrarily small error margin ϵ > 0 on tree-structured networks. We also developed a complementary mixed integer programming (MIP) approach for approximating the Pareto frontier and methods for approximating high-dimensional Pareto frontiers. The second is an online matching problem coordinating citizen scientists for invasive species survey efforts. We developed a learning-augmented matching algorithm that can utilize partial information and provides good performance and approximation guarantees. For both applications, we provide not only practical solutions to real-world problems but also novel computational algorithms and techniques

关键词： approximation algorithm Combinatorial optimization Computational sustainability Hydropower Multiobjective optimization

来源：评论

学校读者我要写书评

暂无评论

Multi-Satellite Imaging Task Planning for Large Regional Coverage: A Heuristic algorithm Based on Triple Grids Method

引用

REMOTE SENSING 2024年第1期16卷 194页

作者： Li, Feng Wan, Qiuhua Wen, Feifei Zou, Yongkui He, Qien Li, Da Zhong, Xing Garzelli, Andrea Chinese Acad Sci Changchun Inst Opt Fine Mech & Phys Changchun 130033 Peoples R China Univ Chinese Acad Sci Daheng Coll Beijing 100049 Peoples R China Chang Guang Satellite Technol Co Ltd Changchun 130102 Peoples R China Jilin Univ Sch Math Changchun 130012 Peoples R China

Over the past few decades, there has been a significant increase in the number of Earth observation satellites, and the area of ground targets requiring observation has also been expanding. To effectively utilize the capabilities of these satellites and capture larger areas of ground targets, it has become essential to plan imaging tasks for large regional coverage using multiple satellites. First, we establish a 0-1 integer programming model to accurately describe the problem and analyze the challenges associated with solving the model. Second, we propose a heuristic algorithm based on the triple grids method. This approach utilizes a generated grid to create fewer candidate strips, a calculation grid to determine the effective coverage area more accurately, and a refined grid to solve the issue of repeated coverage of strips. Furthermore, we employ an approximation algorithm to further improve the solutions obtained from the heuristic algorithm. By comparing the proposed method to the traditional greedy heuristic algorithm and three evolutionary algorithms, the results show that our method has better performance in terms of coverage and efficiency.

关键词： multi-satellite large regional coverage heuristic algorithm triple grids method approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Stealthy DGoS Attack: DeGrading of Service Under the Watch of Network Tomography

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2021年第3期29卷 1294-1307页

作者： Chiu, Cho-Chun He, Ting Penn State Univ Dept Comp Sci & Engn University Pk PA 16801 USA

Network tomography is a powerful tool to monitor the internal state of a closed network that cannot be measured directly, with broad applications in the Internet, overlay networks, and all-optical networks. However, existing network tomography solutions all assume that the measurements are trust-worthy, leaving open how effective they are in an adversarial environment with possibly manipulated measurements. To understand the fundamental limit of network tomography in such a setting, we formulate and analyze a novel type of attack that aims at maximally degrading the performance of targeted paths without being localized by network tomography. By analyzing properties of the optimal attack strategy, we formulate novel combinatorial optimizations to design the optimal attack strategy, which are then linked to well-known NP-hard problems and approximation algorithms. As a byproduct, our algorithms also identify approximations of the most vulnerable set of links that once manipulated, can inflict the maximum performance degradation. Our evaluations on real topologies demonstrate the large potential damage of such attacks, signaling the need of new defenses.

关键词： Tomography Measurement Monitoring Delays approximation algorithms Optimization Current measurement Network tomography denial of service attack combinatorial optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A new LP rounding algorithm for the active time problem

引用

JOURNAL OF SCHEDULING 2021年第5期24卷 543-552页

作者： Calinescu, Gruia Wang, Kai IIT Dept Comp Sci Chicago IL 60616 USA City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China HHL Leipzig Grad Sch Management Ctr Adv Studies Management CASiM Jahnallee 59 D-04109 Leipzig Germany

In this paper, we work on the scheduling problem with active time model. We have a set of preemptive jobs with integral release times, deadlines and required processing lengths, while the preemption of jobs is only allowed at integral time points. We have a single machine that can process at most g distinct job units at any given time unit when the machine is switched on. The objective is to find a schedule that completes all jobs within their timing constraints and minimizes the time when the machine is on, i.e., the active time. This problem has been studied by Chang et al. where they proposed an LP rounding approach which gives a 2-approximation solution. In this paper, we also give a 2-approximation algorithm based on LP rounding approach with a different rounding technique and analysis. Finally, we give a new linear programming formulation for which we conjecture that the integrality gap is 5/3, which might bring new hope for beating the barrier of 2 for the approximation ratio.

关键词： approximation algorithm Scheduling Linear program rounding Active time

来源：评论

学校读者我要写书评

暂无评论

Optimal Deployment of Solar Insecticidal Lamps Over Constrained Locations in Mixed-Crop Farmlands

引用

IEEE INTERNET OF THINGS JOURNAL 2021年第16期8卷 13095-13114页

作者： Yang, Fan Shu, Lei Yang, Yuli Han, Guangjie Pearson, Simon Li, Kailiang Nanjing Agr Univ Coll Engn Nanjing 210031 Peoples R China Jiangsu Normal Univ Sch Math & Stat Xuzhou 221116 Jiangsu Peoples R China Nanjing Agr Univ NAU Lincoln Joint Res Ctr Intelligent Engn Nanjing 210031 Peoples R China Univ Lincoln Coll Sci Sch Engn Lincoln LN6 7TS England Univ Lincoln Sch Engn Lincoln LN6 7TS England Hohai Univ Dept Informat & Commun Syst Changzhou 213022 Peoples R China Univ Lincoln Lincoln Inst Agrifood Technol Lincoln LN6 7TS England Nanjing Agr Univ Sch Artificial Intelligence Nanjing 210031 Peoples R China

Solar insecticidal lamps (SILs) play a vital role in green prevention and control of pests. By embedding SILs in wireless sensor networks (WSNs), we establish a novel agricultural Internet of Things (IoT), referred to as the SIL-IoTs. In practice, the deployment of SIL nodes is determined by the geographical characteristics of an actual farmland, the constraints on the locations of SIL nodes, and the radio-wave propagation in a complex agricultural environment. In this article, we mainly focus on the constrained SIL deployment problem (cSILDP) in a mixed-crop farmland, where the locations used to deploy SIL nodes are a limited set of candidates located on the ridges. We formulate the cSILDP in this Scenario as a connected set cover (CSC) problem and propose a hole-aware node deployment method (HANDM) based on the greedy algorithm to solve the constrained optimization problem. The HANDM is a two-phase method. In the first phase, a novel deployment strategy is utilized to guarantee only a single coverage hole in each iteration, based on which a set of suboptimal locations is found for the deployment of SIL nodes. In the second phase, according to the operations of deletion and fusion, the optimal locations are obtained to meet the requirements on complete coverage and connectivity. Experimental results show that our proposed method achieves better performance than the peer algorithms, specifically in terms of deployment cost.

关键词： approximation algorithms Wireless sensor networks Internet of Things Peer-to-peer computing Wireless communication Monitoring Heuristic algorithms approximation algorithm connected set cover (CSC) problem constrained SIL deployment problem (cSILDP) mixed-crop farmland path-loss model Solar insecticidal lamp-Internet of Things (SIL-IoTs) wireless sensor network (WSN)

来源：评论

学校读者我要写书评

暂无评论

View-based Explanations for Graph Neural Networks

引用

Proceedings of the ACM on Management of Data 2024年第1期2卷 1-27页

作者： Tingyang Chen Dazhuo Qiu Yinghui Wu Arijit Khan Xiangyu Ke Yunjun Gao Zhejiang University Ningbo China Aalborg University Aalborg Denmark Case Western Reserve University Cleveland USA Zhejiang University & Zhejiang University Ningbo China Zhejiang University Hangzhou China

Generating explanations for graph neural networks (GNNs) has been studied to understand their behaviors in analytical tasks such as graph classification. Existing approaches aim to understand the overall results of GNNs rather than providing explanations for specific class labels of interest, and may return explanation structures that are hard to access, nor directly queryable. We propose GVEX, a novel paradigm that generates Graph Views for GNN EXplanation. (1) We design a two-tier explanation structure called explanation views. An explanation view consists of a set of graph patterns and a set of induced explanation subgraphs. Given a database G of multiple graphs and a specific class label l assigned by a GNN-based classifier M, it concisely describes the fraction of G that best explains why l is assigned by M. (2) We propose quality measures and formulate an optimization problem to compute optimal explanation views for GNN explanation. We show that the problem is Σ2P-hard. (3) We present two algorithms. The first one follows an explain-and-summarize strategy that first generates high-quality explanation subgraphs which best explain GNNs in terms of feature influence maximization, and then performs a summarization step to generate patterns. We show that this strategy provides an approximation ratio of 1/2. Our second algorithm performs a single-pass to an input node stream in batches to incrementally maintain explanation views, having an anytime quality guarantee of 1/4-approximation. Using real-world benchmark data, we experimentally demonstrate the effectiveness, efficiency, and scalability of GVEX. Through case studies, we showcase the practical applications of GVEX.

关键词： approximation algorithm data mining deep learning explainable ai graph neural networks graph views

来源：评论

学校读者我要写书评

暂无评论

Fully Dynamic k-Center Clustering with Outliers 28th

Fully Dynamic k-Center Clustering with Outliers

引用

28th International Computing and Combinatorics Conference (COCOON)

作者： Chan, T-H Hubert Lattanzi, Silvio Sozio, Mauro Wang, Bo HKU Pok Fu Lam Hong Kong Peoples R China Google Res Mountain View CA USA Inst Polytech Paris Telecom Paris Paris France

ISBN: (纸本)9783031221040;9783031221057

We consider the robust version of the classic k-center clustering problem, where we wish to remove up to z points (outliers), so as to be able to cluster the remaining points in k clusters with minimum maximum radius. We study such a problem under the fully dynamic adversarial model, where points can be inserted or deleted arbitrarily. In this setting, the main goal is to design algorithms that maintain a high quality solution at any point in time, while requiring a "small" amortized cost, i.e. a "small" number of operations per insertion or deletion, on average. In our work, we provide the first constant bi-criteria approximation algorithm for such a problem with its amortized cost being independent of both z and the size of the current input.

关键词： Clustering Fully dynamic approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

No-wait two-stage flowshop problem with multi-task flexibility of the first machine

引用

INFORMATION SCIENCES 2021年 544卷 25-38页

作者： Dong, Jianming Pan, Hong Ye, Cunkui Tong, Weitian Hu, Jueliang Zhejiang Sci Tech Univ Dept Math Hangzhou 310018 Zhejiang Peoples R China Eastern Michigan Univ Dept Comp Sci Ypsilanti MI 48165 USA

For the creation of intelligent management systems in hospitals, efficient resource arrangement is essential. Motivated by a real-world scenario in hospitals, we introduce the no-wait two-stage flowshop scheduling problem with the first-stage machine having multi-task flexibility. In this problem, each job has two operations which are processed in order on a two-stage flowshop without preemption and time delay between or on machines. The multi-task flexibility allows the first-stage machine to process the second-stage operations. The goal is to minimize the maximum completion time of all jobs. To the best of our knowledge, this is a pioneering work on this problem. We discover several novel structural properties, based on which we present a linear-time combinatorial algorithm with an approximation ratio 13/8. This problem and its variants can find many other meaningful applications in modern manufacturing systems, such as the robot cell scheduling with computer numerical control machines or printed circuit boards. The idea behind our algorithm may inspire more practical algorithms. (C) 2020 Published by Elsevier Inc.

关键词： Flowshop No-wait Blocking Multi-task flexibility Worst-case performance ratio approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：