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

THEORY OF COMPUTING SYSTEMS 2025年第2期69卷 1-37页

作者： Balkanski, Eric Ou, Tingting Stein, Clifford Wei, Hao-Ting Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA

algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. In this paper, we study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. Our main result is an algorithm that achieves a min{eta 2(1+alpha),(2+2/alpha)}-approximation, for any alpha is an element of(0,1), where eta >= 1 is the prediction error. When the predictions are accurate, this approximation outperforms the best known approximation for speed-robust scheduling without predictions of 2-1/m, where m is the number of machines, while simultaneously maintaining a worst-case approximation of 2+2/alpha even when the predictions are arbitrarily wrong. In addition, we obtain improved approximations for three special cases: equal job sizes, infinitesimal job sizes, and binary machine speeds. We also complement our algorithmic results with lower bounds. Finally, we empirically evaluate our algorithm against existing algorithms for speed-robust scheduling.

关键词： algorithms with prediction Scheduling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

The circular balancing problem☆

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2025年第1期321卷 41-56页

作者： Lee, Myungho Lee, Kangbok Pinedo, Michael LG CNS Seoul 07795 South Korea Pohang Univ Sci & Technol Dept Ind & Management Engn Pohang 37673 South Korea NYU Stern Sch Business New York NY 10012 USA

We propose a balancing problem with a minmax objective in a circular setting. This balancing problem involves the arrangement of an even number of items with different weights on a circle while minimizing the maximum total weight of items arranged on any half circle. Due to its generic structure, it may have applications in fair resource allocation schemes. We show the NP-hardness of the problem and develop polynomial-time algorithms when the number of distinct weights is a fixed constant. We propose for the general case a tight 7/6- approximation algorithm and show that it performs better than two existing algorithms designed for an equivalent problem in the literature. The worst-case performance ratio is derived through a linear combination of valid inequalities that are obtained from the problem definition, the properties of the proposed algorithm, and the optimal circular permutation structure. Furthermore, we formulate a more general problem of minimizing the maximum total weight of items on equally divided circular sectors and present its computational complexity and a tight approximation algorithm.

关键词： Combinatorial optimization Circular permutation Computational complexity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the pure fixed charge transportation problem

引用

DISCRETE OPTIMIZATION 2025年 55卷

作者： Zhu, Pengfei Chen, Guangting Chen, Yong Zhang, An Hangzhou Dianzi Univ Dept Math Hangzhou 310018 Zhejiang Peoples R China Zhejiang Univ Water Resources & Elect Power Hangzhou 310018 Zhejiang Peoples R China

The pure fixed charge transportation problem is a well-known variant of the classic transportation problem where the cost of sending goods from a source to a destination only equals a fixed charge, regardless of the flow quantity. The objective is to minimize the total cost of shipping available goods to meet the required demands. Hence, we first demonstrate that this problem is NP-hard even when there are only two destinations, and it is Strong NP-hard when the number of destinations is input. These two new complexity results are an important supplement to the previous complexity results of this problem. Then, we propose two simple but novel approximation algorithms with a constant worst-case ratio, which is proved using an integer convex optimization model. Although our approximation algorithm applies to a few destinations, to our knowledge, it is the first approximation algorithm to handle the pure fixed-charge transportation problem.

关键词： Transportation problem Fixed charge NP-hard approximation algorithm Worst case ratio

来源：评论

学校读者我要写书评

暂无评论

Through-Wall Mobile Charging: Theory, Methodology, and Implementation

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2025年第6期24卷 4971-4986页

作者： Sun, Yu Lin, Chi Yang, Wei Dai, Haipeng Ren, Jiankang Wang, Lei Wu, Guowei Dalian Univ Technol DUT Sch Software Technol Dalian 116024 Peoples R China Dalian Univ Technol DUT RU Int Sch Informat Sci & Engn Dalian 116024 Peoples R China Serv Software Liaoning Prov Key Lab Ubiquitous Network Dalian 116621 Peoples R China Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Dalian Univ Technol Sch Comp Sci & Technol Dalian 116024 Peoples R China

Wireless Power Transfer (WPT) has revolutionized the field of Wireless Rechargeable Sensor Networks (WRSNs), enabling sustainable operation of sensor nodes. Traditional mobile charging methods often require sensors to be within line-of-sight or physically accessed by the mobile charger, which may potentially lead to user safety or privacy concerns. Addressing this concern, this work is the first to introduce and validate the feasibility of Through-Wall charging. We formulate the Wireless charging thrOugh Walls (WOW) problem to simultaneously enhance user safety and maximize charging utility. Our approach leverages fundamental principles of electromagnetics to construct an accurate charging model for Magnetic Resonance Coupling-based WPT systems. Additionally, we thoroughly analyze the impact of wall obstruction and provide a generalized framework for through-wall charging. By employing discretization techniques and approximation algorithms, we derive a near-optimal solution to the WOW problem. Extensive simulations and test-bed experiments demonstrate that our proposed approach reduces the reliance on physical access to devices, simplifies deployment in complex environments, and thereby optimizes the travel paths of mobile chargers and enhances the overall performance and lifetime of WRSNs. Compared to conventional methods, our method benefits from more reasonable scheduling order and path construction, achieving an average energy efficiency improvement of 27.8%.

关键词： Safety Wireless communication Wireless sensor networks Mobile computing Inductive charging Coils Privacy Smart homes Energy efficiency Costs approximation algorithm mobile charging through-wall charging wireless rechargeable sensor network

来源：评论

学校读者我要写书评

暂无评论

Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem

引用

OPERATIONS RESEARCH LETTERS 2022年第6期50卷 693-698页

作者： Iglesias, Jennifer Ravi, R. Waymo Inc 1600 Amphitheatre Pkwy Mountain View CA 94043 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

In this paper, we investigate the weighted tree augmentation problem (TAP), where the goal is to augment a tree with a minimum cost set of edges such that the graph becomes two edge connected. First we show that in weighted TAP, we can restrict our attention to trees which are binary and where all the non-tree edges go between two leaves of the tree. We then give a top-down coloring algorithm that differs from known techniques for approximating TAP. The algorithm we describe always gives a 2-approximation starting from any feasible fractional solution to the natural tree cut covering LP. When the structure of the fractional solution is such that all the edges with non-zero weight are at least alpha, then this algorithm achieves a 2 1+alpha -approximation. We also investigate a variant of TAP where every tree edge must belong to a cycle of length three (triangle) in the solution. We give a O(logn)-approximation algorithm for this problem in the weighted case in n-node graphs and a 4-approximation in the unweighted case. (c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： approximation algorithm Network design Integrality gap

来源：评论

学校读者我要写书评

暂无评论

W-PRIZE-COLLECTING WITH RELEASE DATES ON A SINGLE MACHINE

引用

JOURNAL OF INDUSTRIAL AND MANAGEMENT OPTIMIZATION 2025年第1期21卷 769-782页

作者： Sun, Ruiqing Yunnan Univ Sch Math & Stat Kunming Yunnan Peoples R China

In many practical make-to-order production systems, to obtain the profit requirements but with limited resources and delivery requirements, a decision-maker may only accept some of the orders and reject the others, and schedule the accepted orders onto the machines for processing. Meanwhile, accepted jobs (orders) will generate a corresponding profit, and the decision-maker wants to obtain maximum profits. It is common in practical make-to-order production systems that jobs (orders) may have different release dates. In this paper, this scheduling problem is modeled as W-prize-collecting with release dates on a single machine. In this problem, each job is either accepted and processed on a single machine, or is rejected by paying a rejection cost, where each job has a release date and profit. The objective is to minimize the makespan of the accepted jobs plus the total cost of the rejected jobs, conditional on their total profit being no less than a given threshold. It will be proved that the problem is NP-hard for a special case, that is, when the job has the same processing time but no release dates. Furthermore, a 3-approximation algorithm for this problem is also proposed. Then, a pseudopolynomial time dynamic programming algorithm is provided. Next, based on the dynamic programming algorithm, a fully polynomial time approximation scheme (FPTAS) for this problem is also obtained. Finally, our numerical tests indicate that the dynamic programming algorithm can solve medium-size problems in reasonable running time.

关键词： W-prize-collecting release date approximation algorithm dynamic programming FPTAS

来源：评论

学校读者我要写书评

暂无评论

On the parenthesisations of matrix chains: All are useful, few are essential

引用

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

作者： Lopez, Francisco Karlsson, Lars Bientinesi, Paolo Umea Univ Dept Comp Sci Umea Sweden

The product of a matrix chain consisting of n matrices can be computed in Cn-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C_{n-1}$$\end{document} (Catalan's number) different ways, each identified by a distinct parenthesisation of the chain. The best algorithm to select a parenthesisation that minimises the cost runs in O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n \log n)$$\end{document} time. Approximate algorithms run in O(n) time and find solutions that are guaranteed to be within a certain factor from optimal;the best factor is currently 1.155. In this article, we first prove two results that characterise different parenthesisations, and then use those results to improve on the best known approximation algorithms. Specifically, we show that (a) each parenthesisation is optimal somewhere in the problem domain, and (b) exactly n+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n + 1$$\end{document} parenthesisations are essential in the sense that the removal of any one of them causes an unbounded penalty for an infinite number of problem instances. By focusing on essential parenthesisations, we improve on the best known approximation algorithm and show that the approximation factor is at most 1.143.

关键词： Matrix multiplication Matrix chain approximation algorithm Linear algebra compilers

来源：评论

学校读者我要写书评

暂无评论

Improved approximation for maximum edge colouring problem

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 42-52页

作者： Chandran, L. Sunil Lahiri, Abhiruk Singh, Nitin Indian Inst Sci Dept Comp Sci & Automat Bangalore India IBM India Res Lab Bangalore India

The anti-Ramsey number, ar(G, H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H, namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erdos and Simonovits in 1973. Since then the parameter has been studied extensively. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q-colouring problem: Find a colouring of the edges of G, maximizing the number of colours satisfying the constraint that each vertex spans at most q colours on its incident edges. It is easy to see that the maximum value of the above optimization problem equals ar(G, K1,q+1) - 1. In this paper, we study the maximum edge 2-colouring problem from the approx-imation algorithm point of view. The case q = 2 is particularly interesting due to its application in real-life problems. algorithmically, this problem is known to be NP-hard for q - 2. For the case of q = 2, it is also known that no polynomial-time algorithm can approximate to a factor less than 3/2 assuming the unique games conjecture. Feng et al. showed a 2-approximation algorithm for this problem. Later Adamaszek and Popa presented a 5/3-approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say M) and different colours to the connected components of G \ M. In this article, we give a new analysis of the aforementioned algorithm to show that for triangle-free graphs with perfect matching the approximation ratio is 8/5. We also show that this algorithm cannot achieve a factor better than 58/37 o

关键词： approximation algorithm Graph algorithm Graph colouring Anti-Ramsey number

来源：评论

学校读者我要写书评

暂无评论

Towards Constant-Factor approximation for Chordal/Distance-Hereditary Vertex Deletion

引用

algorithmICA 2022年第7期84卷 2106-2133页

作者： Ahn, Jungho Kim, Eun Jung Lee, Euiwoong Korea Adv Inst Sci & Technol Dept Math Sci Daejeon South Korea Inst Basic Sci IBS Discrete Math Grp Daejeon South Korea Univ Paris 09 PSL Univ LAMSADE CNRS F-75016 Paris France Univ Michigan Dept EECS Ann Arbor MI 48109 USA

For a family of graphs F, WEIGHTED F-DELETION is the problem for which the input is a vertex weighted graph G = (V, E) and the goal is to delete S subset of V with minimum weight such that G \ S is an element of F. Designing a constant-factor approximation algorithm for large subclasses of perfect graphs has been an interesting research direction. Block graphs, 3-leaf power graphs, and interval graphs are known to admit constant-factor approximation algorithms, but the question is open for chordal graphs and distance-hereditary graphs. In this paper, we add one more class to this list by presenting a constant-factor approximation algorithm when F is the intersection of chordal graphs and distance-hereditary graphs. They are known as ptolernaic graphs and form a superset of both block graphs and 3-leaf power graphs above. Our proof presents new properties and algorithmic results on inter-clique digraphs as well as an approximation algorithm for a variant of FEEDBACK VERTEX SET that exploits this relationship (named FEEDBACK VERTEX SET WITH PRECEDENCE CONSTRAINTS), each of which may be of independent interest.

关键词： Chordal graphs Distance-hereditary graphs Ptolemaic graphs approximation algorithm Linear programming Feedback vertex set

来源：评论

学校读者我要写书评

暂无评论

Asymptotic Quasi-Polynomial Time approximation Scheme for Resource Minimization for Fire Containment

引用

algorithmICA 2022年第9期84卷 2462-2479页

作者： Rahgoshay, Mirmahdi Salavatipour, Mohammad R. Univ Alberta Dept Comp Sci Edmonton AB Canada

Resource Minimization Fire Containment (RMFC) is a natural model for optimal inhibition of harmful spreading phenomena on a graph. In the RMFC problem on trees, we are given an undirected tree G, and a vertex r where the fire starts at, called root. At each time step, the firefighters can protect up to B vertices of the graph while the fire spreads from burning vertices to all their neighbors that have not been protected so far. The task is to find the smallest B that allows for saving all the leaves of the tree. The problem is hard to approximate up to any factor better than 2 even on trees unless P= NP (King and MacGillivray in Discret Math 310(3):614-621, 2010). Chalermsook and Chuzhoy (In: Proceedings of the 21st annual ACM-SIAM symposium on discrete algorithms, SODA 2010, Austin, Texas, USA, 17-19 Jan 2010, SIAM, pp 1334-1349, 2010) presented a Linear Programming (LP) based O (log* n) approximation for RMFC on trees that matches the integrality gap of the natural Linear Programming relaxation. This was recently improved by Adjiashvili et al. (ACM Trans algorithms 15(2):20:1-20:33, 2019) to a 12-approximation through a combination of LP rounding along with several new techniques. In this paper we present an asymptotic QPTAS for RMFC on trees. More specifically, let epsilon > 0, and I be an instance of RMFC where the optimum number of firefighters to save all the leaves is OPT (I). We present an algorithm which uses at most inverted right perpendicular(1 + epsilon) O PT (I)inverted left perpendicular many firefighters at each time step and runs in time n(O(log log n/)(epsilon)). This suggests that the existence of an asymptotic PTAS is plausible especially since the exponent is O(log log n), not O(log n). Our result combines a more refined height reduction lemma than the one in Adjiashvili et al. (2019) with LP rounding and dynamic programming to find the solution. We also apply our height reduction lemma to the algorithm provided in Adjiashvili et al. (2019) plu

关键词： Firefighter problem Resource management Fire containment approximation algorithm Asymptotic approximation scheme

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：