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

Construction of node- and link-fault-tolerant virtual backbones in wireless networks

JOURNAL OF SUPERCOMPUTING 2023年第12期79卷 13050-13074页

作者： Liang, Jiarong Zeng, Weijian Du, Xiaojiang Guangxi Univ Sch Comp Elect & Informat Guangxi Key Lab Multimedia Commun & Network Techno Nanning 530004 Guangxi Peoples R China Nanning Univ Coll Informat Engn Nanning 530200 Guangxi Peoples R China Stevens Inst Technol Dept Elect & Comp Engn Hoboken NJ USA

In wireless sensor networks (WSNs), the virtual backbone (VB) consists of a subset of nodes, which are responsible for routing tasks. Fault-tolerant VBs are desirable for overcoming the effects of node or link failure in WSNs. Usually, a homogeneous WSN (VB) is abstracted as a unit disk graph (UDG) (connected dominating set(CDS)). This paper introduces the concept of a fault-tolerant CDS in a UDG called a ((2, 2), m)-CDS, which is different from a traditional fault-tolerant CDS ((k, m)-CDS). A ((2, 2), m)-CDS can still function even if one edge or one node fails, which implies that it possesses fault-tolerant properties for both nodes and edges, in contrast to traditional (k, m)-CDSs, which possess fault tolerance only for nodes. Then, we propose a 5a-approximation algorithm for computing a ((2, 2), m)-CDS, where a is the performance ratio for computing a (2, m)-CDS, and analyze its time complexity. In simulations, we compare our algorithm with an existing algo-rithm for fault-tolerant CDS construction based on CDS size. From the simulations, we find that our algorithm outperforms its competitor in constructing a quality VB.

关键词： Wireless sensor network Fault-tolerant virtual backbone (2,2)-connected m-dominating set Unit disk graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Placing Wireless Chargers With Limited Mobility

引用

IEEE TRANSACTIONS ON MOBILE COMPUTING 2023年第6期22卷 3589-3603页

作者： Dai, Haipeng Wang, Xiaoyu Lin, Xuzhen Gu, Rong Shi, Shuyu Liu, Yunhuai Dou, Wanchun Chen, Guihai Nanjing Univ State Key Lab Novel Software Technol Nanjing 210023 Jiangsu Peoples R China Soochow Univ Sch Comp Sci & Technol Suzhou 215006 Jiangsu Peoples R China Peking Univ Beijing 100080 Peoples R China

Several recent works have studied mobile charging under the "one-to-many" charging pattern where a single charger can charge multiple devices simultaneously. However, most of them focus on path planning and charging time allocation, but overlook the underlying dependence of the charging efficiency on initial deployment positions of chargers. This paper studies the problem of Placing directional wIreless chargers with Limited mObiliTy (PILOT), that is, maximize the overall charging utility for a set of static rechargeable devices on a 2D plane by determining deployment positions, stop positions and orientations, and portions of time for all deployed chargers that can move in a limited area after their deployment. To the best of our knowledge, we are the first to study placement of mobile directional chargers under the "one-to-many" pattern. To address PILOT, we propose a(1/2 - epsilon)-approximation algorithm. First, we present a method to approximate nonlinear charging power of chargers, and further propose an approach to construct Maximal Covered Set uniform subareas to reduce the infinite continuous search space for stop positions and orientations to a finite discrete one. Second, we present geometrical techniques to further reduce the infinite solution space for candidate deployment positions to a finite one without performance loss, and transform PILOT to a mixed integer nonlinear programming problem. Finally, we propose a linear programming based greedy algorithm to address it. Simulation and experimental results show that our algorithm outperforms six comparison algorithms by 19.74% similar to 500.01%.

关键词： Wireless communication Wireless sensor networks Mobile computing Sensors approximation algorithms Wireless power transfer Resource management Placement directional charging limited mobility wireless power transfer approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

An Overall Evaluation on Benefits of Competitive Influence Diffusion

引用

IEEE TRANSACTIONS ON BIG DATA 2023年第2期9卷 653-664页

作者： Guo, Jianxiong Zhang, Yapu Wu, Weili Univ Texas Dallas Erik Jonsson Sch Engn & Comp Sci Dept Comp Sci Richardson TX 75080 USA Univ Chinese Acad Sci Sch Math Sci Beijing 100049 Peoples R China

Influence maximization (IM) is a representative and classic problem that has been studied extensively before. The most important application derived from the IM problem is viral marketing. Take us as a promoter, we want to get benefits from the influence diffusion in a given social network, where each influenced (activated) user is associated with a benefit. However, there is often competing information initiated by our rivals that diffuses in the same social network at the same time. Consider such a scenario, a user is influenced by both our information and our rivals' information. Here, the benefit from this user should be weakened to a certain degree. How to quantify the degree of weakening? Based on that, we propose an overall evaluation on benefits of influence (OEBI) problem. We prove the objective function of the OEBI problem is not monotone, not submodular, and not supermodular. Fortunately, we can decompose this objective function into the difference of two submodular functions and adopt a modular-modular procedure to approximate it with a data-dependent approximation guarantee. Because of the difficulty to compute the exact objective value, we design a group of unbiased estimators by exploiting the idea of reverse influence sampling, which can improve time efficiency significantly without losing its approximation ratio. Finally, numerical experiments on real datasets verified the effectiveness of our approaches regardless of performance and efficiency.

关键词： Social networking (online) approximation algorithms Linear programming Computational modeling Greedy algorithms Heuristic algorithms Big Data Overall evaluations influence maximization submodularity modular-modular proceduce sampling techniques social networks approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Model-Free Assortment Pricing with Transaction Data

引用

MANAGEMENT SCIENCE 2023年第10期69卷 5830-5847页

作者： Chen, Ningyuan Cire, Andre A. Hu, Ming Lagzi, Saman Univ Toronto Rotman Sch Management Toronto ON M5S 3E6 Canada Univ Toronto Scarborough Dept Management Toronto ON M1C 1A4 Canada Univ N Carolina Kenan Flagler Business Sch Chapel Hill NC 27599 USA

We study the problem when a firm sets prices for products based on the transaction data, that is, which product past customers chose from an assortment and what were the historical prices that they observed. Our approach does not impose a model on the distribution of the customers' valuations and only assumes, instead, that purchase choices satisfy incentive-compatible constraints. The uncertainty set of potential valuations of each past customer can then be encoded as a polyhedral set, and our approach maximizes the worst case revenue, assuming that new customers' valuations are drawn from the empirical distribution implied by the collection of such polyhedra. We study the single-product case analytically and relate it to the traditional model-based approach. Then, we show that the optimal prices in the general case can be approximated at any arbitrary precision by solving a compact mixed-integer linear program. We further design three approximation strategies that are of low computational complexity and interpretable. In particular, the cutoff pricing heuristic has a competent provable performance guarantee. Comprehensive numerical studies based on synthetic and real data suggest that our pricing approach is uniquely beneficial when the historical data has a limited size or is susceptible to model misspecification.

关键词： data-driven incentive-compatible robust optimization pricing assortment approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Offline preemptive bottom left decreasing height scheduling of power loads in smart grids

引用

ENERGY SYSTEMS-OPTIMIZATION MODELING SIMULATION AND ECONOMIC ASPECTS 2023年第4期14卷 959-984页

作者： Ranjan, Anshu Khargonekar, Pramod Sahni, Sartaj Bloomberg LP New York NY 10022 USA Univ Calif Irvine Irvine CA USA Univ Florida Gainesville FL USA

We are considering the scheduling of flexible preemptable electric loads in a smart grid so as to minimize peak load when all loads have the same earliest start time and deadline. We show that when this scheduling is done using the bottom left decreasing height heuristic, the ratio of the peak load of the schedule generated by this heuristic and the optimal peak load has the tight bound 4/3 - 1/(3D), where D is the duration of the scheduling interval. This settles an outstanding conjecture regarding the worst-case performance of this heuristic. Our experiments indicate a reduction in peak load of up to 45% using the bottom left decreasing height heuristic and benchmark data.

关键词： approximation algorithm Smart grid Scheduling

来源：评论

学校读者我要写书评

暂无评论

Partial-monotone adaptive submodular maximization

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-13页

作者： Tang, Shaojie Yuan, Jing Univ Texas Dallas Naveen Jindal Sch Management Richardson TX 75080 USA Univ North Texas Dept Comp Sci & Engn Denton TX USA

Many AI/Machine learning problems require adaptively selecting a sequence of items, each selected item might provide some feedback that is valuable for making better selections in the future, with the goal of maximizing an adaptive submodular function. Most of existing studies in this field focus on either monotone case or non-monotone case. Specifically, if the utility function is monotone and adaptive submodular, Golovin and Krause (J Artif Intell Res 42:427-486, 2011) developed (1 - 1/e) approximation solution subject to a cardinality constraint. For the cardinality-constrained non-monotone case, Tang (Theor Comput Sci 850:249-261, 2021) showed that a random greedy policy attains an approximation ratio of 1/e. In this work, we generalize the above mentioned results by studying the partial-monotone adaptive submodular maximization problem. To this end, we introduce the notation of adaptive monotonicity ratio m is an element of [0, 1] to measure the degree of monotonicity of a function. Our main result is to show that for the case of cardinality constraints, if the utility function has an adaptive monotonicity ratio of m and it is adaptive submodular, then a random greedy policy attains an approximation ratio of m(1 - 1/e) + (1 - m)(1/e). Notably this result recovers the aforementioned (1 - 1/e) and 1/e approximation ratios when m = 1 and m = 0, respectively. We further extend our results to consider a knapsack constraint and develop a (m + 1)/10 approximation solution for this general case. One important implication of our results is that even for a non-monotone utility function, we still can attain an approximation ratio close to (1-1/e) if this function is "close" to a monotone function. This leads to improved performance bounds for many machine learning applications whose utility functions are almost adaptive monotone.

关键词： approximation algorithm Adaptive submodular maximization Partial-monotonicity

来源：评论

学校读者我要写书评

暂无评论

Fast approximations for Dynamic Behavior in Manufacturing Systems With Regular Orders: An Aggregation Method

引用

IEEE ROBOTICS AND AUTOMATION LETTERS 2023年第11期8卷 7122-7129页

作者： Chen, Jingchuan Shen, Zuo-Jun Max Univ Hong Kong Dept Ind & Mfg Syst Engn Hong Kong Peoples R China Univ Hong Kong Fac Engn Hong Kong Peoples R China Univ Hong Kong Fac Business & Econ Hong Kong Peoples R China Univ Calif Berkeley Coll Engn Berkeley CA 94720 USA

Both manufacturing systems and inventory models have received substantial research attention, but they are mainly investigated independently without considering their interactions. In fact, from the supply chain network perspective, manufacturing systems and warehouses may interact. This article considers the manufacturing systems with regular orders. In addition to machines and work-in-process buffers usually considered in current literature, a finished goods buffer is added to the manufacturing system to store the final products. For a fixed shipping period, a certain amount of products are shipped to the customers. For these systems, the production process and inventory level may fluctuate when goods are shipped. As a result, they are in dynamic modes in part or all the processing cycles, and an unacceptable error occurs when employing the steady-state analysis algorithm. Therefore, this article develops effective algorithms for analyzing the dynamic behavior in manufacturing systems with regular orders. Specifically, the system with one machine and finished goods buffer isolated from the manufacturing system is first modeled and estimated. Then, based on it, we proposed an aggregation method, which can be employed in larger systems. The approach substantially decreases the state space of the problem and leads to the modeling and estimation of the system solvable. Numerical experiments show that the proposed methods maintain high accuracy.

关键词： Aggregation method approximation algorithm customer demand dynamic behavior manufacturing system

来源：评论

学校读者我要写书评

暂无评论

Vertex downgrading to minimize connectivity

引用

MATHEMATICAL PROGRAMMING 2023年第1-2期199卷 215-249页

作者： Aissi, Hassene Chen, Da Qi Ravi, R. Paris Dauphine Univ Paris France Carnegie Mellon Univ Pittsburgh PA 15213 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA USA

We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the case when both ends of an arc must be downgraded to remove it, for example. For this generalization, we provide a bicriteria (4, 2)-approximation that downgrades nodes with total weight at most 4 times the budget and provides a solution where the downgraded connectivity from the source to the sink is at most 2 times that in an optimal solution. We accomplish this with an LP relaxation and rounding using a ball-growing algorithm based on the LP values. Furthermore, we show that other bicriteria approximations exist where one can worsen the approximation factor for one of the costs in order to improve the other. We further generalize the downgrading problem to one where each vertex can be downgraded to one of k levels, and the arc capacities are functions of the pairs of levels to which its ends are downgraded. We generalize our LP rounding to get a (4k, 4k)-approximation for this case. Trade-offs between the two approximation ratios similar to the two-level case also exist for the generalized problem. By transferring node values to edge values, we also derive new bicriteria approximation results for the vertex interdiction versions of the multiway cut problem in digraphs and multicut problems in undirected graphs.

关键词： Vertex interdiction Vertex downgrading Network interdiction approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Minimum Power Partial Cover Problem 1

引用

13th International Conference on algorithmic Aspects in Information and Management (AAIM)

作者： Li, Menghong Ran, Yingli Zhang, Zhao Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China

ISBN: (数字)9783030271954

ISBN: (纸本)9783030271954;9783030271947

In this paper, we study the minimum power partial cover problem (MinPowerPartCov). Suppose X is a set of points and S is a set of sensors on the plane, each sensor can adjust its power, the covering range of a sensor s with power p(s) is a disk centered at s which has radius r(s) satisfying p(s) = c center dot r(s)(alpha). Given an integer k <= vertical bar X vertical bar, the MinPowerPartCov problem is to determine the power assignment on each sensor such that at least k points are covered and the total power consumption is the minimum. We present an approximation algorithm with approximation ratio 3(alpha), using a local ratio method, which coincides with the best known ratio for the minimum power (full) cover problem. Compared with the paper [9] which studies the MinPowerPartCov problem for alpha = 2, our ratio improves their ratio from 12 + epsilon to 9.

关键词： Power Partial cover approximation algorithm Local ratio

来源：评论

学校读者我要写书评

暂无评论

2-approximation Polynomial-Time algorithm for a Cardinality-Weighted 2-Partitioning Problem of a Sequence 3rd

2-Approximation Polynomial-Time Algorithm for a Cardinality-...

引用

3rd International Conference on Numerical Computations - Theory and algorithms (NUMTA)

作者： Kel'manov, Alexander Khamidullin, Sergey Panasenko, Anna Sobolev Inst Math 4 Koptyug Ave Novosibirsk 630090 Russia Novosibirsk State Univ 2 Pirogova St Novosibirsk 630090 Russia

ISBN: (纸本)9783030406165

We consider a problem of 2-partitioning a finite sequence of points in Euclidean space into clusters of the given sizes with some constraints. The solution criterion is the minimum of the sum of weighted intracluster sums of squared distances between the elements of each cluster and its center. The weight of the intracluster sum is equal to the cluster size. The center of one cluster is given as input (is the origin without loss of generality), while the center of the other one is unknown and is determined as a geometric center. The following constraints hold: the difference between the indices of two subsequent points included in the first cluster is bounded from above and below by some given constants. In this paper, we have shown that the considered problem is the strongly NP-hard one and propose a polynomial-time 2-approximation algorithm for solving the problem.

关键词： Euclidean space Sequence of points Weighted 2-partition Quadratic variation NP-hard problem approximation algorithm Polynomial time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：