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

Broadcasting a file in a communication network

JOURNAL OF SCHEDULING 2020年第2期23卷 211-232页

作者： Goetzmann, Kai-Simon Harks, Tobias Klimm, Max Tech Univ Berlin Inst Math Str 17 Juni 136 D-10623 Berlin Germany Humboldt Univ Sch Business & Econ Spandauer Str 1 D-10178 Berlin Germany Univ Augsburg Inst Math D-86135 Augsburg Germany

We study the problem of distributing a file, initially located at a server, among a set of n nodes. The file is divided into m = 1 equally sized packets. After downloading a packet, nodes can upload it to other nodes, possibly to multiple nodes in parallel. Each node, however, may receive each packet from a single source node only. The upload and download rates between nodes are constrained by node- and server-specific upload and download capacities. The objective is to minimize the makespan. This problem has been proposed and analyzed first by Mundinger et al. (J Sched 11:105-120, 2008. https://***/ 10.1007/ s10951- 007-0017-9) under the assumption that uploads obey the fair sharing principle, that is, concurrent upload rates from a common source are equal at any point in time. Under this assumption, the authors devised an optimal polynomial time algorithm for the case where the upload capacity of the server and the nodes' upload and download capacities are all equal. In this work, we drop the fair sharing assumption and derive an exact polynomial time algorithm for the case when upload and download capacities per node and among nodes are equal. We further show that the problem becomes strongly NP-hard for equal upload and download capacities per node that may differ among nodes, even for a single packet. For this case, we devise a polynomial time (1 + 2v 2)-approximation algorithm. Finally, we devise two polynomial time algorithms with approximation guarantees of 5 and 2 + log2 n/m /m, respectively, for the general case of m packets.

关键词： Broadcasting problem Content distribution File sharing Load balancing Makespan Peer-to-peer approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Improving on Best-of-Many-Christofides for T -tours

引用

OPERATIONS RESEARCH LETTERS 2020年第6期48卷 798-804页

作者： Traub, Vera Swiss Fed Inst Technol Zurich Switzerland

The T-tour problem is a natural generalization of TSP and Path TSP. Given a graph G = (V, E), edge cost c : E -> R->= 0, and an even cardinality set T subset of V, we want to compute a minimum-cost T-join connecting all vertices of G (and possibly containing parallel edges). In this paper we give an 11/7-approximation for the T-tour problem and show that the integrality ratio of the standard LP relaxation is at most 11/7. Despite much progress for the special case Path TSP, for general T-tours this is the first improvement on Seb's analysis of the Best-of-Many-Christofides algorithm (Seb, 2013). (c) 2020 The Author. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： Traveling salesman problem T-join approximation algorithm Integrality gap

来源：评论

学校读者我要写书评

暂无评论

Bi-Objective Vehicle Routing for Muck Transportation in Urban Road Networks

引用

IEEE ACCESS 2020年 8卷 114219-114227页

作者： Guo, Qinge Wang, Nengmin Su, Bing Zhang, Meng Xi An Jiao Tong Univ Sch Management Xian 710049 Peoples R China Xian Technol Univ Sch Econ & Management Xian 710021 Peoples R China Kunming Univ Sci & Technol Fac Management & Econ Kunming 650500 Yunnan Peoples R China

As a consequence of expedited urban construction, large quantities of wastes are shipped every day. Because of the excessive pursuit of economic benefits by muck truck drivers and unreasonable transportation route choices, the accident rates of these drivers continue to increase. It is very important to optimize the safe transportation routing of muck trucks. In this paper, a safe transportation routing model was established to minimizes path safety risks and single driving time as the bi-objective, and two different situations for the optimal path of the model were analyzed. For the situation in which there are several short paths in the network, one of which is the path with the least safety risks, an exact algorithm, A*, was designed, and time complexity was analyzed. For the situation in which there is a single path or several shortest paths in the network but the path with the minimal path safety risks is not included in the set of shortest paths, an approximation algorithm, GA*, was designed, and time complexity and the approximation ratio were analyzed. Our experimental results demonstrated the validity of our developed model and approaches. Moreover, a case study is carried out on a real-case application related to the network in the Xi'an International Port District.

关键词： Accidents Safety Roads Economics Vehicles Vehicle routing Muck trucks safety transportation vehicle routing bi-objective programming approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Delivery Route Optimization with automated vehicle in smart urban environment

引用

THEORETICAL COMPUTER SCIENCE 2020年 836卷 42-52页

作者： Luo, Chuanwen Li, Deying Ding, Xingjian Wu, Weili Renmin Univ China Sch Informat Beijing 100872 Peoples R China Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

As a part of the smart urban construction, automated driving is introduced to improve the utilization efficiency of cars and roads, which not only reduces the incidence of traffic accidents, but also improves the environment quality. With the development of the smart urban, it is predictable that, in the city of the future, the service of package pickup and delivery or takeout will be supported mainly by automated vehicles. However, the existing works mainly focus on the variants of the Vehicle Routing Problem (VRP), in which they either take no account of service time of automated vehicle for customers when the automated vehicle arrives at the locations of customers or ignore the impact of rewards gained from customers on path planning of the automated vehicles. In this paper, we also extend a variant of VRP where an automated vehicle is used to package delivery or distribution of food in the smart urban environment, which is called the Delivery Reward Maximization (DRM) problem. The problem aims at designing a route of the automated vehicle while considering the service time for customers before their deadlines and the impact of rewards of the automated vehicle on path planning. We first prove that the DRM problem is NP-hard. Then we study two special cases of the DRM problem, which are called Linear DRM (LDRM) problem and Two-dimensional DRM (TDRM) problem, respectively. In the LDRM and TDRM problems, all customers have the same visiting deadlines and are deployed on the one-dimensional line and two-dimensional plane, respectively. Then we prove that the LDRM and TDRM problems are also NP-hard and propose a constant approximation algorithm for each of them. Afterward, we propose a greedy algorithm to solve the DRM problem, and give the analysis by counterexample. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Smart urban Automated vehicle Path planning approximation algorithm Delivery Route Optimization

来源：评论

学校读者我要写书评

暂无评论

A continuous review policy for two complementary products with interrelated demand

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2020年 150卷 106980-106980页

作者： Poormoaied, Saeed Atan, Zumbul Eindhoven Univ Technol Dept Ind Engn & Innovat Sci OPAC Grp NL-5612 AZ Eindhoven Netherlands

We consider a retailer selling two complementary products. The products are demanded individually or jointly. The retailer uses a continuous review (Q, r) policy to manage the inventory of each product. The customers arrive according to a Poisson process and unmet demands are lost. We aim to calculate the optimal policy parameters which maximize the expected profit rate. A shortage of one product might result in a lost sale of its complementary product, even if this product is in stock. This fact complicates the analysis. We rely on a simulation-based optimization approach to derive the optimal parameters of the (Q, r) policy for each product. Our results reveal that the maximum profit rate is attained when all customers demand both products, i.e., the bundle of complementary products. In addition, we observe that when the demand rate is low, the interaction between product demands has significant impact on the expected profit rate, and this effect becomes even more prominent when the unit lost sale costs are low and the unit holding costs are high. We derive the analytical properties of a single-product inventory system based on which an efficient approximation algorithm is developed.

关键词： Complementary products Continuous review policy Simulation-based optimization approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time

引用

JOURNAL OF THE ACM 2020年第6期67卷 1–22页

作者： Chakraborty, Diptarka Das, Debarati Goldenberg, Elazar Koucky, Michal Saks, Michael Natl Univ Singapore Sch Comp 13 Comp Dr Singapore 117417 Singapore Univ Copenhagen Univ Pk 1 DK-2100 Copenhagen Denmark Acad Coll Tel Aviv Yaffo Rabenu Yeruham St IL-61083 Yaffo Israel Charles Univ Prague Malostranske Nam 25 Prague 11800 Czech Republic Rutgers State Univ Dept Math 110 Frelinghuysen Rd Piscataway NJ USA

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this article, we provide an algorithm with running time (O) over tildeO(n(2-2/7)) that approximates the edit distance within a constant factor.

关键词： Edit distance approximation algorithm sub-quadratic time algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Influence Maximization: Seeding Based on Community Structure

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2020年第6期14卷 1-22页

作者： Guo, Jianxiong Wu, Weili Univ Texas Dallas Dept Comp Sci 800 W Campbell Rd Richardson TX 75080 USA

Influence maximization problem attempts to find a small subset of nodes in a social network that makes the expected influence maximized, which has been researched intensively before. Most of the existing literature focus only on maximizing total influence, but it ignores whether the influential distribution is balanced through the network. Even though the total influence is maximized, but gathered in a certain area of social network. Sometimes, this is not advisable. In this article, we propose a novel seeding strategy based on community structure, and formulate the Influence Maximization with Community Budget (IMCB) problem. In this problem, the number of seed nodes in each community is under the cardinality constraint, which can be classified as the problem of monotone submodular maximization under the matroid constraint. To give a satisfactory solution for IMCB problem under the triggering model, we propose the IMCB-Framework, which is inspired by the idea of continuous greedy process and pipage rounding, and derive the best approximation ratio for this problem. In IMCB-Framework, we adopt sampling techniques to overcome the high complexity of continuous greedy. Then, we propose a simplified pipage rounding algorithm, which reduces the complexity of IMCB-Framework further. Finally, we conduct experiments on three real-world datasets to evaluate the correctness and effectiveness of our proposed algorithms, as well as the advantage of IMCB-Framework against classical greedy method.

关键词： Influence maximization community structure social network continuous greedy matorid approximation algorithm IMCB-Framework

来源：评论

学校读者我要写书评

暂无评论

The seeding algorithm for k-means problem with penalties

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第1期39卷 15-32页

作者： Li, Min Xu, Dachuan Yue, Jun Zhang, Dongmei Zhang, Peng Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Beijing Univ Technol Coll Appl Sci Dept Operat Res & Sci Comp Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China Shandong Univ Sch Software Jinan 250101 Peoples R China

The k-means problem is a classic NP-hard problem in machine learning and computational geometry. And its goal is to separate the given set into k clusters according to the minimal squared distance. The k-means problem with penalties, as one generalization of k-means problem, allows that some point need not be clustered instead of being paid some penalty. In this paper, we study the k-means problem with penalties by using the seeding algorithm. We propose that the accuracy only involves the ratio of the maximal penalty value to the minimal one. When the penalty is uniform, the approximation factor reduces to the same one for the k-means problem. Moreover, our result generalizes the k-means++ for k-means problem to the penalty version. Numerical experiments show that our seeding algorithm is more effective than the one without using seeding.

关键词： approximation algorithm k-means Penalty Seeding algorithm

来源：评论

学校读者我要写书评

暂无评论

A survey on influence maximization in a social network

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2020年第9期62卷 3417-3455页

作者： Banerjee, Suman Jenamani, Mamata Pratihar, Dilip Kumar IIT Gandhinagar Dept Comp Sci & Engn Gandhinagar Gujarat India IIT Kharagpur Dept Ind & Syst Engn Kharagpur W Bengal India IIT Kharagpur Dept Mech Engn Kharagpur W Bengal India

Given a social network with diffusion probabilities as edge weights and a positive integer k, which k nodes should be chosen for initial injection of information to maximize the influence in the network? This problem is popularly known as the Social Influence Maximization Problem (SIM Problem). This is an active area of research in computational social network analysis domain, since one and half decades or so. Due to its practical importance in various domains, such as viral marketing, target advertisement and personalized recommendation, the problem has been studied in different variants, and different solution methodologies have been proposed over the years. This paper presents a survey on the progress in and around SIM Problem. At last, it discusses current research trends and future research directions as well.

关键词： Social networks Influence maximization approximation algorithm Greedy strategy

来源：评论

学校读者我要写书评

暂无评论

Complexity of Roman {2}-domination and the double Roman domination in graphs

引用

AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS 2020年第3期17卷 1081-1086页

作者： Padamutham, Chakradhar Palagiri, Venkata Subba Reddy NIT Warangal Dept Comp Sci & Engn Warangal 506004 Telangana India

For a simple, undirected graph G=(V,E), a Roman {2}-dominating function (R2DF) f:V -> {0,1,2} has the property that for every vertex v is an element of V with f(v) = 0, either there exists a vertex u is an element of N(v), with f(u) = 2, or at least two vertices x,y is an element of N(v) with f(x)=f(y)=1. The weight of an R2DF is the sum f(V)=Sigma v is an element of Vf(v). The minimum weight of an R2DF is called the Roman {2}-domination number and is denoted by gamma {R2}(G). A double Roman dominating function (DRDF) on G is a function f:V -> {0,1,2,3} such that for every vertex v is an element of V if f(v) = 0, then v has at least two neighbors x,y is an element of N(v) with f(x)=f(y)=2 or one neighbor w with f(w) = 3, and if f(v) = 1, then v must have at least one neighbor w with f(w)>= 2. The weight of a DRDF is the value f(V)=Sigma v is an element of Vf(v). The minimum weight of a DRDF is called the double Roman domination number and is denoted by gamma dR(G). Given an graph G and a positive integer k, the R2DP (DRDP) problem is to check whether G has an R2DF (DRDF) of weight at most k. In this article, we first show that the R2DP problem is NP-complete for star convex bipartite graphs, comb convex bipartite graphs and bisplit graphs. We also show that the DRDP problem is NP-complete for star convex bipartite graphs and comb convex bipartite graphs. Next, we show that gamma {R2}(G),and gamma dR(G) are obtained in linear time for bounded tree-width graphs, chain graphs and threshold graphs, a subclass of split graphs. Finally, we propose a 2(1+ln(Delta +1))-approximation algorithm for the minimum Roman {2}-domination problem and 3(1+ln(Delta +1))-approximation algorithm for the minimum double Roman domination problem, where Delta is the maximum degree of G.

关键词： Roman {2}-domination double Roman domination tree convex bipartite graphs NP-complete approximation algorithm 05C69 68Q25

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：