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

Nearly tight approximation algorithm for (connected) Roman dominating set

OPTIMIZATION LETTERS 2022年第8期16卷 2261-2276页

作者： Li, Ke Ran, Yingli Zhang, Zhao Du, Ding-Zhu Zhejiang Normal Univ Coll Math & Comp Sci Jinhua 321004 Zhejiang Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

A Roman dominating function of graph G is a function r : V (G) -> {0, 1, 2} satisfying that every vertex v with r(v) = 0 is adjacent to at least one vertex u with r(u) = 2. The minimum Roman dominating set problem (MinRDS) is to compute a Roman dominating function r that minimizes the weight Sigma(v is an element of V) r (v). The minimum connected Roman dominating set problem (MinCRDS) is to find a minimum weight Roman dominating function r(c) such that the subgraph of G induced by D-R = {v is an element of V vertical bar r(c)(v) = 1 or r(c) (v) = 2} is connected. In this paper, we present a greedy algorithm for MinRDS with a guaranteed performance ratio at most H(delta(max) + 1), where H(.) is the Harmonic number and delta(max) is the maximum degree of the graph. For any epsilon > 0, we show that there exists a greedy algorithm for MinCRDS with approximation ratio at most (1 + epsilon) In delta(max) + O(1). The challenge for the analysis of the MinCRDS algorithm lies in the fact that the potential function is not only non-submodular but also non-monotone.

关键词： Roman dominating set Connected Roman dominating set Non-submodular optimization greedy algorithm Approxiamtion ratio

来源：评论

学校读者我要写书评

暂无评论

Objective Selection for Cancer Treatment: An Inverse Optimization Approach

引用

OPERATIONS RESEARCH 2022年第3期000卷 1-22页

作者： Ajayi, Temitayo Lee, Taewoo Schaefer, Andrew J. Rice Univ Dept Computat & Appl Math Houston TX 77005 USA Univ Texas Maryland Anderson Canc Ctr Dept Radiat Oncol Houston TX 77030 USA Univ Houston Dept Ind Engn Houston TX 77004 USA

In radiation therapy treatment plan optimization, selecting a set of clinical objectives that are tractable and parsimonious yet effective is a challenging task. In clinical practice, this is typically done by trial and error based on the treatment planner's subjective assessment, which often makes the planning process inefficient and inconsistent. We develop the objective selection problem that infers a sparse set of objectives for prostate cancer treatment planning based on historical treatment data. We formulate the problem as a non-convex bilevel mixed-integer program using inverse optimization and highlight its connection with feature selection to propose multiple solution approaches, including greedy heuristics and regularized problems and application-specific methods that use anatomical information of the patients. Our results show that the proposed heuristics find objectives that are near optimal. Via curve analysis on dose-volume histograms, we show that the learned objectives closely represent latent clinical preferences.

关键词： inverse optimization objective selection feature selection greedy algorithm multiobjective optimization cancer therapy

来源：评论

学校读者我要写书评

暂无评论

Online Unit Clustering and Unit Covering in Higher Dimensions

引用

algorithmICA 2022年第5期84卷 1213-1231页

作者： Dumitrescu, Adrian Toth, Csaba D. Algoresearch LLC Milwaukee WI USA Calif State Univ Northridge Dept Math Los Angeles CA 91330 USA Tufts Univ Dept Comp Sci Medford MA 02155 USA

We revisit the online UNIT CLUSTERING and UNIT COVERING problems in higher dimensions: Given a set of n points in a metric space, that arrive one by one, Unit Clustering asks to partition the points into the minimum number of clusters (subsets) of diameter at most one;whereas UNIT COVERING asks to cover all points by the minimum number of balls of unit radius. In this paper, we work in Rd using the L-infinity norm. We show that the competitive ratio of any online algorithm (deterministic or randomized) for UNIT CLUSTERING is Omega(d). In particular, it depends on the dimension d, and this resolves an open problem raised by Epstein and van Stee (Theor Comput Sci 407(1-3):85-96, 2008). We also give a randomized online algorithm with competitive ratio O(d(2)) for UNIT CLUSTERING of integer points (i.e., points in Z(d), d is an element of N, under the L-infinity norm). We show that the competitive ratio of any deterministic online algorithm for UNIT COVERING is at least 2d. This ratio is the best possible, as it can be attained by a simple deterministic algorithm that assigns points to a predefined set of unit hypercubes. We complement these results with some additional lower bounds for related problems in higher dimensions.

关键词： Online algorithm Unit covering Unit clustering Competitive ratio greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Multidimensional Assignment Problem for Multipartite Entity Resolution

引用

JOURNAL OF GLOBAL OPTIMIZATION 2022年第2期84卷 491-523页

作者： Kammerdiner, Alla Semenov, Alexander Pasiliao, Eduardo L. Univ Florida Res & Engn Educ Facil REEF Shalimar FL 32579 USA Univ Florida Herbert Wertheim Coll Engn Gainesville FL USA Munit Directorate Eglin FL USA

Multipartite entity resolution aims at integrating records from multiple datasets into one entity. We derive a mathematical formulation for a general class of record linkage problems in multipartite entity resolution across many datasets as a combinatorial optimization problem known as the multidimensional assignment problem. As a motivation for our approach, we illustrate the advantage of multipartite entity resolution over sequential bipartite matching. Because the optimization problem is NP-hard, we apply two heuristic procedures, a greedy algorithm and very large scale neighborhood search, to solve the assignment problem and find the most likely matching of records from multiple datasets into a single entity. We evaluate and compare the performance of these algorithms and their modifications on synthetically generated data. We perform computational experiments to compare performance of recent heuristic, the very large-scale neighborhood search, with a greedy algorithm, another heuristic for the MAP, as well as with two versions of genetic algorithm, a general metaheuristic. Importantly, we perform experiments to compare two alternative methods of re-starting the search for the former heuristic, specifically a random-sampling multi-start and a deterministic design-based multi-start. We find evidence that design-based multi-start can be more efficient as the size of databases grow large. In addition, we show that very large scale search, especially its multi-start version, outperforms simple greedy heuristic. Hybridization of greedy search with very large scale neighborhood search improves the performance. Using multi-start with as few as three additional runs of very large scale search offers some improvement in the performance of the very large scale search procedure. Last, we propose an approach to evaluating complexity of the very large-scale neighborhood search.

关键词： Multidimensional assignment problem Multipartite entity resolution Very large scale neighborhood search greedy algorithm Genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Maximization problems of balancing submodular relevance and supermodular diversity

引用

JOURNAL OF GLOBAL OPTIMIZATION 2022年第1期82卷 179-194页

作者： Liu, Zhicheng Guo, Longkun Du, Donglei Xu, Dachuan Zhang, Xiaoyan Nanjing Normal Univ Coll Taizhou Taizhou 225300 Peoples R China Fuzhou Univ Sch Comp Sci & Bigdata Fuzhou 350116 Peoples R China Univ New Brunswick Fac Management Fredericton NB E3B 5A3 Canada Beijing Univ Technol Beijing Inst Sci & Engn Comp Beijing 100124 Peoples R China Nanjing Normal Univ Sch Math Sci Nanjing 210023 Peoples R China Nanjing Normal Univ Inst Math Nanjing 210023 Peoples R China

Relevance and diversity are two desirable properties in data retrieval applications, an important field in data science and machine learning. In this paper, we consider three maximization problems to balance these two factors. The objective function in each problem is the sum of a monotone submodular function f and a supermodular function g, where f and g capture the relevance and diversity of any feasible solution, respectively. In the first problem, we consider a special supermodular diversity function g of a sum-sum format satisfying the relaxed triangle inequality, for which we propose a greedy-type approximation algorithm with an (1 -1/e, 1/(2 alpha))-bifactor approximation ratio, improving the previous (1/(2 alpha), 1/(2 alpha))-bifactor approximation ratio. In the second problem, we consider an arbitrary supermodular diversity function g, for which we propose a distorted greedy method to give a min {1 - k(f)e(-1), 1 - k(g)e(-(1-kg))}-approximation algorithm, improving the previous k(f)(-1) (1 - e(-kf(1-kg)))-approximation ratio, where k(f) and k(g) are the curvatures of the submodular function f and the supermodular funciton g, respectively. In the third problem, we generalize the uniform matroid constraint to the p matroid constraints, for which we present a local search algorithm to improve the previous 1-k(g)/(1-k(g))k(f)+p-approximation ratio to min {p+1-k(f)/p(p+1), (1-k(g)/p + k(g)(1-k(g))(2)/p+(1-k(g))(2))}.

关键词： submodular Max-sum diversification greedy algorithm Local search Supermodular Curvature Matroid

来源：评论

学校读者我要写书评

暂无评论

Multi-period two-echelon location routing problem for disaster waste clean-up

引用

TRANSPORTMETRICA A-TRANSPORT SCIENCE 2022年第3期18卷 1053-1083页

作者： Cheng, Cheng Zhu, Rui Costa, Alysson M. Thompson, Russell G. Huang, Xiang Singapore MIT Alliance Res & Technol Future Urban Mobil IRG Singapore Singapore Hong Kong Polytech Univ Land Surveying & GeoInformat Kowloon Hong Kong Peoples R China Univ Melbourne Sch Math & Stat Melbourne Vic Australia Univ Melbourne Dept Infrastruct Engn Melbourne Vic Australia

Waste clean-up after a disaster is one of the most critical tasks in the response stage of disaster management. We develop a model to minimise the cost and duration of disaster waste clean-up considering using Temporary Disaster Waste Management Sites (TDWMSs), which can store and process waste before it is sent to the final disposal sites. The problem that arises can be seen as a Multi-Period Two-echelon Location Routing Problem (MP-2ELRP) in which the main decisions are the location of the TDWMSs and the routing of vehicles in both echelons. In this paper, we propose both a mixed-integer program and a Genetic algorithm (GA) to model and solve the problem. Computational tests indicate: (i) the performance of proposed GA is robust;(ii) the use of TDWMSs can reduce both total waste clean-up cost and duration;and (iii) the capacities of TDWMSs have a significant impact on the total waste clean-up time and duration.

关键词： Disaster waste management two-echelon location routing problem MIP genetic algorithm greedy algorithm

来源：评论

学校读者我要写书评

暂无评论

Automated Placement of In-Network ACL Rules 9

Automated Placement of In-Network ACL Rules

引用

9th IEEE International Conference on Network Softwarization (IEEE NetSoft) - Boosting Future Networks through Advanced Softwarization

作者： Zahwa, Wafik Lahmadi, Abdelkader Rusinowitch, Michael Ayadi, Mondher Univ Lorraine CNRS Inria Loria F-54000 Nancy France NUMERYX Nancy France

ISBN: (纸本)9798350399806

Automatically deploying distributed Access Control Lists (ACLs) in a software-defined network can ensure their internal services and hosts connectivity, security and reliability. ACLs are often deployed in a switch using Ternary Content-Addressable Memory (TCAM). Since TCAM memory is often too limited to store a large ACL, one has to split the lists and distribute the parts on several switches in such a way that every packet travelling from a source to a destination undergoes the required match-action rules. In this paper, we develop and compare three algorithms based on graph theory and Reinforcement Learning (RL) techniques to automatically distribute ACLs across networks switches, while minimizing their TCAM memory occupancy. We compare the three algorithms on several network topologies to evaluate their efficiency in terms of memory occupancy.

关键词： ACL automated rule placement SDN mincut greedy algorithm reinforcement learning

来源：评论

学校读者我要写书评

暂无评论

A Novel Real-Time Deterministic Scheduling Mechanism in Industrial Cyber-Physical Systems for Energy Internet

引用

IEEE TRANSACTIONS ON INDUSTRIAL INFORMATICS 2022年第8期18卷 5670-5680页

作者： Peng, Yuhuai Jolfaei, Alireza Yu, Keping Northeastern Univ Sch Comp Sci & Engn Shenyang 110819 Peoples R China Flinders Univ S Australia Coll Sci & Engn Adelaide SA 5042 Australia Waseda Univ Global Informat & Telecommun Inst Tokyo 1698050 Japan

As an effective distributed renewable energy utilization paradigm, a microgrid is expected to realize the high integration of the industrial cyber-physical systems (CPS), which has attracted extensive attention from academia and industry. However, the real-time interaction and feedback loop between physical systems and cyber systems have posed severe challenges to the reliability, determinacy, and energy efficiency of the multiway flow of information and communication transmission. In order to solve the problem of slot scheduling and data transmission (SSDT) in the microgrid, a novel real-time deterministic scheduling (RTDS) scheme for industrial CPS is proposed in this article. First, the SSDT is formulated as a multiway flow scheduling problem, and it is theoretically proved that the SSDT problem is NP-hard. Then, the RTDS scheme designs two heuristic algorithms: scheduling request preprocessing and greedy-based multichannel time slot allocation for an optimal scheduling solution. Practical experimental results demonstrate that the proposed RTDS scheme has significant advantages in packet loss rate, deadline guarantee rate, and energy consumption compared with the traditional schemes, and thus, is more suitable for deployment in microgrid systems.

关键词： Job shop scheduling Optimal scheduling Microgrids Switches Real-time systems Data communication Wireless sensor networks Deterministic scheduling greedy algorithm industrial cyber-physical systems (CPS) microgrid systems optimal scheduling

来源：评论

学校读者我要写书评

暂无评论

A strategy of model space search for dynamic causal modeling in task fMRI data exploratory analysis

引用

PHYSICAL AND ENGINEERING SCIENCES IN MEDICINE 2022年第3期45卷 867-882页

作者： Ou, Yilin Dai, Peishan Zhou, Xiaoyan Xiong, Tong Li, Yang Chen, Zailiang Zou, Beiji Cent South Univ Sch Comp Sci & Engn Changsha 410083 Peoples R China Cent South Univ Hunan Engn Res Ctr Machine Vis & Intelligent Med Changsha 410083 Peoples R China

Dynamic causal modeling (DCM) is a tool used for effective connectivity (EC) estimation in neuroimage analysis. But it is a model-driven analysis method, and the structure of the EC network needs to be determined in advance based on a large amount of prior knowledge. This characteristic makes it difficult to apply DCM to the exploratory brain network analysis. The exploratory analysis of DCM can be realized from two perspectives: one is to reduce the computational cost of the model;the other is to reduce the model space. From the perspective of model space reduction, a model space exploration strategy is proposed, including two algorithms. One algorithm, named greedyEC, starts with reducing EC from full model, and the other, named greedyROI, start with adding EC from one node model. Then the two algorithms were applied to the task state functional magnetic resonance imaging (fMRI) data of visual object recognition and selected the best DCM model from the perspective of model comparison based on Bayesian model compare method. Results show that combining the results of the two algorithms can further improve the effect of DCM exploratory analysis. For convenience in application, the algorithms were encapsulated into MATLAB function based on SPM to help neuroscience researchers to analyze the brain causal information flow network. The strategy provides a model space exploration tool that may obtain the best model from the perspective of model comparison and lower the threshold of DCM analysis.

关键词： Functional magnetic resonance imaging Dynamic causal modeling greedy algorithm Effective connectivity pattern exploration

来源：评论

学校读者我要写书评

暂无评论

Pilot Contamination Mitigation in Massive MIMO Cloud Radio Access Networks

引用

IEEE ACCESS 2022年 10卷 58212-58224页

作者： Taleb, Hussein Khawam, Kinda Lahoud, Samer El Helou, Melhem Martin, Steven St Joseph Univ Beirut Ecole Super Ingn Beyrouth Beirut 11042020 Lebanon Univ Versailles UVSQ F-78035 Versailles France Univ Paris Saclay Lab Interdisciplinaire Sci Numer CNRS F-91405 Orsay France

Massive multiple-input multiple-output (MIMO) technology is expected to achieve significant gains in both signal-to-noise-plus-interference ratio (SINR) and throughput for 5G cellular wireless networks. Efficient and highly accurate channel state information (CSI) acquisition at the base stations (BS) is essential to achieve the potential benefits of massive MIMO systems. However, the inadequate number of orthogonal pilot sequences used for CSI estimation leads to erroneous channel estimation as it causes interference between pilot sequences. This phenomenon is coined pilot contamination and severely limits the system performance. Therefore, we address in this paper the pilot contamination problem in massive MIMO Cloud-Radio Access Networks systems. Leveraging on a real telecom operator data delivered by Call Detail Records (CDR), our objective is to maximize the average uplink achievable rate by reducing the effect of pilot contamination in massive MIMO Cloud-Radio Access Networks (C-RAN). As such a problem is a non-linear integer problem that has no solution in polynomial time, we develop a two-stage solution to solve it. First, a coalition game is proposed where Remote Radio Heads (RRHs) gather into clusters with random user-pilot allocation. Then, two greedy heuristics are applied to match each user in the cluster with a given pilot. The goal is to further improve the average uplink rate achieved in the first stage. Simulation results show that our heuristic solutions for pilot contamination mitigation outperform the traditional pilot allocation solution and a state-of-the-art pilot allocation scheme based on large-scale fading in terms of average uplink achievable rate and SINR.

关键词： Call detail records coalition game cloud-radio access networks epsilon-greedy algorithm greedy algorithm massive MIMO pilot contamination

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：