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

Adaptive Two-Stage Stochastic Programming with an Analysis on Capacity Expansion Planning Problem

M&SOM-MANUFACTURING & SERVICE OPERATIONS MANAGEMENT 2024年第6期26卷 1981-2350, C2页

作者： Basciftci, Beste Ahmed, Shabbir Gebraeel, Nagi Univ Iowa Tippie Coll Business Dept Business Analyt Iowa City IA 52242 USA Georgia Inst Technol H Milton Stewart Sch Ind & Syst Engn Atlanta GA 30332 USA

Problem definition: : Multistage stochastic programming is a well-established framework for sequential decision making under uncertainty by seeking policies that can be dynamically adjusted as uncertainty is realized. Often, for example, because of contractual constraints, such flexible policies are not desirable, and the decision maker may need to commit to a set of actions for a certain number of periods. Two-stage stochastic programming might be better suited to such settings, where first-stage decisions do not adapt to the uncertainty realized. In this paper, we propose a novel alternative approach, named as adaptive two-stage stochastic programming, where each component of the decision policy requiring limited flexibility has its own revision point, a period prior to which the decisions are determined at the beginning of the planning until this revision point, and after which they are revised for adjusting to the uncertainty realized thus far until the end of the planning. We then analyze this approach over the capacity expansion planning problem, that may require limited flexibility over expansion decisions. Methodology/results: : We provide a generic mixed-integer programming formulation for the adaptive two-stage stochastic programming problem with finite support, in particular, for scenario trees, and show that this problem is NP-hard in general. Next, we focus on the capacity expansion planning problem and derive bounds on the value of adaptive two-stage programming in comparison with the two-stage and multistage approaches in terms of revision points. We propose several heuristic solution algorithms based on this bound analysis. These algorithms either provide approximation guarantees or computational advantages in solving the resulting adaptive two-stage stochastic problem. Managerial implications: : We provide insights on the choice of the revision times based on our analytical analysis. We further present an extensive computational study on a generatio

关键词： stochastic programming mixed-integer programming capacity expansion planning approximation algorithm energy

来源：评论

学校读者我要写书评

暂无评论

Maximizing full-view target coverage in camera sensor networks

引用

AD HOC NETWORKS 2019年 94卷 101973-000页

作者： Jia, Jinglan Dong, Cailin Hong, Yi Guo, Ling Yu, Ying Yangtze Univ Sch Informat & Math Jingzhou Peoples R China Cent China Normal Univ Sch Math & Stat Wuhan Hubei Peoples R China Beijing Forestry Univ Sch Informat Sci & Technol Beijing Peoples R China Northwest Univ Sch Informat Sci & Technol Xian Shaanxi Peoples R China Cent China Normal Univ Sch Comp Wuhan Hubei Peoples R China

Traditional target coverage only ensures monitoring of targets. However, as people's security awareness increases, the requirement for target coverage also increases from monitoring to identification. Thus full-view coverage model is proposed to guarantee that any facing direction of a target could be covered. Based on this coverage model, we study the maximum full-view target coverage problem in camera sensor networks, where each camera sensor has P working directions, aiming at maximizing the number of full-view covered targets by scheduling the working directions of camera sensors. To solve this problem, we design a (1 - 1/e)-approximation algorithm based on pipage rounding and an efficient heuristic algorithm. Finally, simulation results are presented to demonstrate the performance of our algorithms. (C) 2019 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Camera sensor networks Full-view target coverage

来源：评论

学校读者我要写书评

暂无评论

Total (restrained) domination in unit disk graphs

引用

INFORMATION AND COMPUTATION 2024年 300卷

作者： Yang, Yu Wang, Cai-Xia Xu, Shou-Jun Lanzhou Univ Sch Math & Stat Gansu Key Lab Appl Math & Complex Syst Lanzhou 730000 Gansu Peoples R China Minnan Normal Univ Sch Math & Stat Zhangzhou 363000 Fujian Peoples R China

The minimum total domination problem and the minimum total restrained domination problem are classical combinatorial optimization problems. In this paper, we first show that the decision versions of both the minimum total domination problem and the minimum total restrained domination problem are NP-complete for grid graphs (a subclass of unit disk graphs), thereby strengthening the result on the total domination decision problem in unit disk graphs established by Jena et al. (2021). Then, we present a linear-time 6.387approximation algorithm for the minimum total domination problem in unit disk graphs, improving upon the previous algorithm with a ratio of 8 by Jena et al. (2021). Finally, we propose a linear-time 10.387-approximation algorithm and a PTAS for the minimum total restrained domination problem in unit disk graphs. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： Total dominating set Total restrained dominating set Unit disk graph NP-complete approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Bag-of-Tasks Scheduling with Rejection in Large Computing Systems

引用

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH 2023年第4期40卷 2340011-2340011页

作者： Li, Weidong Yunnan Univ Sch Math & Stat Kunming 650504 Peoples R China

We are given a set of m identical parallel machines and a set of n jobs in large computing systems, where each job J(j) consists of a bag of bj identical tasks with a processing time p(j), and has a rejection penalty wj. Job J(j )is either accepted in which case all the b(j) tasks must be processed by one of the machines, or rejected which incurs a rejection penalty w(j). The problem of bag-of-tasks scheduling with rejection is to find a feasible schedule, so as to minimize the makespan plus the total rejection penalty of all rejected jobs. In this paper, we present a polynomial time approximation scheme.

关键词： Bag-of-tasks scheduling approximation algorithm rejection penalty polynomial time approximation scheme

来源：评论

学校读者我要写书评

暂无评论

Approximately EFX allocations for indivisible chores

引用

ARTIFICIAL INTELLIGENCE 2024年 326卷

作者： Zhou, Shengwei Wu, Xiaowei Univ Macau IOTSC Macau Peoples R China

In this paper, we study how to fairly allocate a set of m indivisible chores to a group of n agents, each of which has a general additive cost function on the items. Since envy-free (EF) allocations are not guaranteed to exist, we consider the notion of envy-freeness up to any item (EFX). In contrast to the fruitful results regarding the (approximation of) EFX allocations for goods, very little is known for the allocation of chores. Prior to our work, for the allocation of chores, it is known that EFX allocations always exist for two agents or general number of agents with identical ordering cost functions. For general instances, no non-trivial approximation result regarding EFX allocation is known. In this paper, we make progress in this direction by providing several polynomial time algorithms for the computation of EFX and approximately EFX allocations. We root show that for three agents we can always compute a (2 + 6) -approximation of EFX allocation. For n >= 4 agents, our algorithm always computes a (3n2 - n) -approximation. We also study the bi-valued instances, in which agents have at most two cost values on the chores. For three agents, we provide an algorithm for the computation of EFX allocations. For n >= 4 agents, we present algorithms for the computation of partial EFX allocations with at most (n - 1) unallocated items;and (n - 1) -approximation of EFX allocations.

关键词： Fair allocation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On approximate near-neighbors search under the (continuous) Frechet distance in higher dimensions

引用

INFORMATION PROCESSING LETTERS 2024年 183卷

作者： Mirzanezhad, Majid Univ Michigan Transportat Res Inst 2901 Baxter rd Ann Arbor MI 48109 USA

Previous studies on Approximate Near-Neighbors Search (ANNS) among curves are either focused on curves in R-1 or under the discrete Frechet distance. In this paper, we propose the first data structure for curves under the (continuous) Frechet distance in higher dimensions. Given a set P of n curves each with number of vertices at most m in R-d, and a fixed delta > 0, we aim to preprocess P into a data structure so that for any given query curve Q with k vertices, we can efficiently report all curves in P whose Frechet distances to Q are at most delta. In the case that k is given in the preprocessing stage, for any epsilon > 0 we propose a deterministic data structure whose space is n center dot O (max{(root d/epsilon)(kd), (D root d/epsilon(2))(kd)}) that can answer (1 + epsilon)delta-ANNS queries in O (kd) query time, where D is the diameter of P. Considering k as part of the query slightly changes the space to n center dot O (1/epsilon)(md) with O (kd) query time within an approximation factor of 5 + epsilon. Moreover, we show that our generic data structure for ANNS can give an alternative treatment of the approximate subtrajectory range searching problem studied by de Berg et al. [1]. (c) 2023 Elsevier B.V. All rights reserved.

关键词： Frechet distance Nearest neighbor search Data structure approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Elimination Graphs

引用

ACM TRANSACTIONS ON algorithmS 2012年第2期8卷 14-14页

作者： Ye, Yuli Borodin, Allan Univ Toronto Dept Comp Sci Toronto ON M5S 1A1 Canada

In this article we study graphs with inductive neighborhood properties. Let P be a graph property, a graph G = (V, E) with n vertices is said to have an inductive neighborhood property with respect to P if there is an ordering of vertices v(1), ... , v(n) such that the property P holds on the induced subgraph G[N(v(i)) boolean AND V-i], where N(v(i)) is the neighborhood of v(i) and V-i = {v(i), ... , v(n)}. It turns out that if we take P as a graph with maximum independent set size no greater than k, then this definition gives a natural generalization of both chordal graphs and (k + 1)-claw-free graphs. We refer to such graphs as inductive k-independent graphs. We study properties of such families of graphs, and we show that several natural classes of graphs are inductive k-independent for small k. In particular, any intersection graph of translates of a convex object in a two dimensional plane is an inductive 3-independent graph;furthermore, any planar graph is an inductive 3-independent graph. For any fixed constant k, we develop simple, polynomial time approximation algorithms for inductive k-independent graphs with respect to several well-studied NP-complete problems. Our generalized formulation unifies and extends several previously known results.

关键词： Graph class structure property approximation algorithm independent set greedy algorithm local ratio time complexity

来源：评论

学校读者我要写书评

暂无评论

Q-SR: An extensible optimization framework for segment routing

引用

COMPUTER NETWORKS 2021年 200卷 108517-108517页

作者： Zhang, Jianwei Zhao, Chenwei Zhejiang Univ City Coll Sch Comp & Comp Sci 51 Huzhou St Hangzhou 310015 Zhejiang Peoples R China Zhejiang Univ Coll Comp Sci & Technol 38 Zheda Rd Hangzhou 310027 Zhejiang Peoples R China

Segment routing (SR) combines the advantages of source routing powered by software-defined networking (SDN) paradigm and hop-by-hop routing in legacy network infrastructure. The recent applications of SR in multi-domain network and service function chaining (SFC) entail the efficient use of multiple segments. However, because of the computation inefficiency, it is nearly impossible to accurately evaluate whether and to what extent various types of networks will benefit from SR with multiple segments using conventional approaches. In this paper, we propose a flexible Q-SR framework as well as its formulation in order to fully explore the potential of SR from an algorithmic perspective. The framework is highly extensible to design and evaluate algorithms that can be adapted to various network topologies and traffic matrices. For the offline setting, we develop a fully polynomial time approximation scheme (FPTAS) which can find a (1 +w) approximation solution for any specified w > 0 in time that is a polynomial function of the network size. To the best of our knowledge, the proposed FPTAS is the first algorithm that can compute arbitrarily accurate solution. For the online setting, we develop an online primal-dual algorithm that is proven to be O(1)-competitive and violates link capacities by a factor of O(logn), where n is the node number of the network. For the proposed approximation algorithms, we prove theoretical performance bounds and conduct extensive simulations on synthetic and realistic networks to analyze SR related and algorithmic parameters and validate the computation efficiency in both offline and online scenarios.

关键词： Segment routing (SR) Traffic engineering (TE) approximation algorithm Online algorithm Software-defined networking (SDN)

来源：评论

学校读者我要写书评

暂无评论

A note on approximating the survivable network design problem in hypergraphs

引用

IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS 2002年第2期E85D卷 322-326页

作者： Zhao, L Nagamochi, H Ibaraki, T Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Kyoto 6068501 Japan Toyohashi Univ Technol Dept Informat & Comp Sci Toyohashi Aichi 4418580 Japan

We consider to design approximation algorithms for the survivable network design problem in hypergraphs (SNDPHG) based on algorithms developed for the survivable network design problem in graphs (SNDP) or the element connectivity problem in graphs (ECP). Given an instance of the SNDPHG. by replacing each hyperedge e = {v(1),...,v(k)} with a new vertex omega(e) and k edges {omega(e),nu(1)},...,{omega(e),nu(k)} we define an SNDP or ECP in the resulting graph. We show that by approximately solving the. SNDP or ECP defined in this way, several approximation algorithms for the SNDPHG can be obtained. One of our results is a d(max)(+)-approximation algorithm for the SNDPHG with d(max) less than or equal to 3, where d(max) (resp. d(max)(+)) is the maximum degree of hyperedges (resp. hyperedges with positive cost). Another is a d(max)(+)H(r(max))-approximation algorithm for the SNDPHG, where H(i) = Sigma(j=1)(l) 1/j is the harmonic function and r(max) is the maximum connectivity requirement.

关键词： survivable network design problem approximation algorithm connectivity graph hypergraph

来源：评论

学校读者我要写书评

暂无评论

COMPUTING WEIGHTED STRENGTH AND APPLICATIONS TO PARTITIONING

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第4期32卷 2747-2782页

作者： Galtier, Jerome Orange Labs 44 AV Republ F-92320 Chatillon France

We study the mathematical concept of the strength of a graph as defined by Cunningham to partition very large graphs. The strength is the objective value of an attack problem on a graph where the striker aims at dividing the graph into a maximum number of connected components removing as few edges as possible per component uncoupled. The strength is the optimal number of edges per component uncoupled or, in the weighted version, the sum of the weights of the edges removed per component uncoupled. Given a connected graph with n vertices and m weighted edges, we denote by W the total sum of the integer weights, and we describe an algorithm that approximates within a factor of 1 + epsilon the weighted strength in time O(m log(W) log(3)(n)/epsilon(2)), and that can be implemented with O(m) memory use if we allow a complexity of O(m log(2)(W) log(3)(n)/epsilon(2)). This result has several important applications, in particular for the detection of dense areas of a graph, in terms of weighted edges, which in turn can be used for spam detection, community identification, and partitioning.

关键词： strength of a graph nested clustering approximation algorithm graphic matroid dendogram Multiplicative-Weights-Update Method Kruskal algorithm community detection small-world ranking classification

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：