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

Itinerary planning for cooperative truck platooning

TRANSPORTATION RESEARCH PART B-METHODOLOGICAL 2021年 153卷 91-110页

作者： Abdolmaleki, Mojtaba Shahabi, Mehrdad Yin, Yafeng Masoud, Neda Univ Michigan Dept Civil & Environm Engn Ann Arbor MI 48109 USA

A cooperative truck platoon is a set of virtually linked trucks driving with a small intravehicle headway enabled by connected and automated vehicle technologies. One of the primary benefits of truck platooning is energy savings due to the reduction of aerodynamic drag on the platooned vehicles. The focus of this paper is on scheduling travel itineraries of a given set of trucks to facilitate the formation of platoons to maximize energy savings. By constructing a time-expanded network, we formulate the problem as a minimum concave-cost network flow problem, and devise a few solution methods to find the optimal or high-quality solutions. The solution methods include an outer approximation algorithm for solving a mixed-integer convex minimization reformulation of the problem, a dynamic-programming-based heuristic scalable to large-scale instances, and a fast approximation algorithm with guaranteed performance for a restrictive version of the problem. All the proposed algorithms are examined and benchmarked on medium to large networks under various test scenarios. The numerical results demonstrate the efficiency of the proposed methods and their applicability in real-world settings.

关键词： Truck platooning Itinerary planning Concave minimum cost flow Outer approximation approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Correlation Clustering with Local and Global Objectives

Correlation Clustering with Local and Global Objectives

引用

作者： Jafarov, Jafar The University of Chicago

学位级别：Ph.D., Doctor of Philosophy

In the Correlation Clustering problem, we are given a graph with its edges labeled as "similar" and "dissimilar" by a noisy binary classifier, and the goal is to produce a clustering of the vertices that matches with the edge labels as much as possible. For a clustering C of graph G, a similar edge is in disagreement with C, if its endpoints belong to distinct clusters; and a dissimilar edge is in disagreement with C if its endpoints belong to the same cluster. The disagreements vector, dis, is a vector indexed by the vertices of G such that the v-th coordinate disv equals the weight of all disagreeing edges incident on v. The goal is to produce a clustering that minimizes the ℓp norm of the disagreements vector for p ≥ 1. Correlation Clustering has been mainly studied under two models where the input graph is (i) complete and unweighted, and (ii) arbitrary and weighted. In this thesis, we introduce a new model of Correlation Clustering that better captures real life instances. In this model the input graph is complete with bounded edge weights. More specifically, every similar edge has weight in the range of [αw,w] and every dissimilar edge has weight at least αw (where α ≤ 1 and w > 0 is a scaling parameter). In the first part of the thesis, we study the ℓ1 objective (MinDisagree) under this model. We give 3 + 2 ln 1/α approximation algorithm and an asymptotically matching integrity gap. In the second part of the thesis, we give an O(1/α)1/2−1/2p · log 1/α approximation algorithm for the ℓp objective. Furthermore, we show an almost matching integrality gap.

关键词： approximation algorithm Clustering Convex relaxation Machine learning Metric space partitioning Theory

来源：评论

学校读者我要写书评

暂无评论

2-Approximating Feedback Vertex Set in Tournaments

引用

ACM TRANSACTIONS ON algorithmS 2021年第2期17卷 1–14页

作者： Lokshtanov, Daniel Misra, Pranabendu Mukherjee, Joydeep Panolan, Fahad Philip, Geevarghese Saurabh, Saket Univ Calif Santa Barbara Dept Comp Sci 2104 Harold Frank Hall Santa Barbara CA 93106 USA Saarland Univ Max Planck Inst Informat Campus E1-4 D-66123 Saarbrucken Germany Ramakrishna Mission Vivekananda Educ & Res Inst PO Belur Math Howrah 711202 W Bengal India Indian Inst Technol Hyderabad Dept Comp Sci & Engn Sangareddy 502285 Telangana India Chennai Math Inst H1SIPCOT IT Pk Siruseri 603103 Kelambakkam India Inst Math Sci 4 Cross RdCIT Campus Chennai 600113 Tamil Nadu India

A tournament is a directed graph T such that every pair of vertices is connected by an arc. A feedback vertex set is a set S of vertices in T such that T - S is acyclic. We consider the Feedback Vertex Set problem in tournaments. Here, the input is a tournament T and a weight function w : V (T) -> N, and the task is to find a feedback vertex set S in T minimizing w(S) = Sigma(v is an element of S) w(v). Rounding optimal solutions to the natural LP-relaxation of this problem yields a simple 3-approximation algorithm. This has been improved to 2.5 by Cai et al. [SICOMP 2000], and subsequently to 7/3 by Mnich et al. [ESA 2016]. In this article, we give the first polynomial time factor 2-approximation algorithm for this problem. Assuming the Unique Games Conjecture, this is the best possible approximation ratio achievable in polynomial time.

关键词： approximation algorithm local ratio feedback vertex set tournament branching

来源：评论

学校读者我要写书评

暂无评论

Hardness and algorithms of equitable tree-coloring problem in chordal graphs

引用

THEORETICAL COMPUTER SCIENCE 2021年 857卷 8-15页

作者： Niu, Bei Li, Bi Zhang, Xin Xidian Univ Sch Math & Stat Xian 710071 Peoples R China

An equitable tree-k-coloring of a graph is a vertex k-coloring such that each color class induces a forest and the size of any two color classes differs by at most one. In this work, we show that every interval graph G has an equitable tree-k-coloring for any integer k >= (Delta(G) + 1)/2, solving a conjecture of Wu, Zhang and Li (2013) for interval graphs, and furthermore, give a linear-time algorithm for determining whether a proper interval graph admits an equitable tree -k-coloring for a given integer k. For disjoint union of split graphs, or K-1,K-r-free interval graphs with r >= 4, we prove that it is W[1]-hard to decide whether there is an equitable tree -k-coloring when parameterized by number of colors, or by treewidth, number of colors and maximum degree, respectively. On the positive side, we propose a quadratic 2-approximation algorithm for the equitable tree-coloring problem in chordal graphs. Moreover, it is proved that there is no alpha-approximation algorithm for any alpha < 3/2 . (c) 2020 Elsevier B.V. All rights reserved.

关键词： W[1]-hardness Linear-time algorithm approximation algorithm Equitable tree-coloring Chordal graphs

来源：评论

学校读者我要写书评

暂无评论

Scheduling coflows of multi-stage jobs under network resource constraints

引用

COMPUTER NETWORKS 2021年 184卷 107686-107686页

作者： Zeng, Yue Ye, Baoliu Tang, Bin Guo, Songtao Qu, Zhihao Nanjing Univ Natl Key Lab Novel Software Technol Nanjing 210023 Peoples R China Hohai Univ Sch Comp & Informat Nanjing 211100 Peoples R China Chongqing Univ Sch Comp Sci Chongqing 400044 Peoples R China

As an emerging network abstraction, coflow greatly improves the communication performance of data-parallel computing jobs. Many existing studies have focused on the design of coflow scheduling to minimize the completion time of jobs. However, they treat the underlying network as a large non-blocking switch without considering the constraints of network resources, which may increase network bottlenecks, reduce link capacity utilization, and extend job completion time. In this paper, we take network resource constraints into account and study how to schedule coflows in multi-stage jobs with the objective of minimizing the total weighted job completion time. We first formalize this multi-stage job scheduling problem as nonlinear programming and prove its NP-hardness. By introducing a priority order of jobs using a linear programming relaxation based approach, we propose a polynomial-time algorithm with a performance guarantee, which can achieve a constant approximation ratio in many typical scenarios. Simulation results based on a Facebook trace show that, compared with a state-of-the-art approach, our algorithm can shorten the average weighted job completion time by up to 48.46% and run faster by up to 19.12x.

关键词： Coflow Multi-stage job Network resource Scheduling algorithm approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Hardware implementation of radial-basis neural networks with Gaussian activation functions on FPGA

引用

NEURAL COMPUTING & APPLICATIONS 2021年第15期33卷 9467-9479页

作者： Shymkovych, Volodymyr Telenyk, Sergii Kravets, Petro Natl Tech Univ Ukraine Dept Automat & Control Tech Syst Igor Sikorsky Kyiv Polytech Inst 37 Prosp Peremohy UA-03056 Kiev Ukraine Cracow Univ Technol Dept Theoret Elect Engn & Comp Sci Warszawska 24 PL-31155 Krakow Poland

This article introduces a method for realizing the Gaussian activation function of radial-basis (RBF) neural networks with their hardware implementation on field-programmable gaits area (FPGAs). The results of modeling of the Gaussian function on FPGA chips of different families have been presented. RBF neural networks of various topologies have been synthesized and investigated. The hardware component implemented by this algorithm is an RBF neural network with four neurons of the latent layer and one neuron with a sigmoid activation function on an FPGA using 16-bit numbers with a fixed point, which took 1193 logic matrix gate (LUTs-LookUpTable). Each hidden layer neuron of the RBF network is designed on an FPGA as a separate computing unit. The speed as a total delay of the combination scheme of the block RBF network was 101.579 ns. The implementation of the Gaussian activation functions of the hidden layer of the RBF network occupies 106 LUTs, and the speed of the Gaussian activation functions is 29.33 ns. The absolute error is +/- 0.005. The Spartan 3 family of chips for modeling has been used to get these results. Modeling on chips of other series has been also introduced in the article. RBF neural networks of various topologies have been synthesized and investigated. Hardware implementation of RBF neural networks with such speed allows them to be used in real-time control systems for high-speed objects.

关键词： approximation algorithm RBF neural network Gaussian activation functions FPGA

来源：评论

学校读者我要写书评

暂无评论

The Euclidean k-supplier problem in IR²

引用

OPERATIONS RESEARCH LETTERS 2021年第1期49卷 48-54页

作者： Basappa, Manjanna Jallu, Ramesh K. Das, Gautam K. Nandy, Subhas C. Birla Inst Technol & Sci Pilani Hyderabad Campus Hyderabad India Czech Acad Sci Prague Czech Republic Indian Inst Technol Guwahati Gauhati 781039 India Indian Stat Inst Kolkata India

Here we propose a fixed-parameter tractable (FPT) algorithm for the k-supplier problem with n clients and m facilities in R-2. The algorithm produces a (1 + epsilon)-factor approximation result in O((max{8 epsilon(-2),1})(k)(n+m) log(mn)) time. The running time is an exponential function of the parameter k for 0 < epsilon < 2 root 2. Next we propose Voronoi diagram based heuristic algorithm for the same problem. We also produce experimental results of the heuristic algorithm, and compare with the available best known result [Nagarajan et al., 2020]. (c) 2020 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Fixed parameter tractability k-supplier Voronoi diagram Local search

来源：评论

学校读者我要写书评

暂无评论

On-Demand Dynamic Controller Placement in Software Defined Satellite-Terrestrial Networking

引用

IEEE TRANSACTIONS ON NETWORK AND SERVICE MANAGEMENT 2021年第3期18卷 2915-2928页

作者： Han, Zhenzhen Xu, Chuan Xiong, Zhengying Zhao, Guofeng Yu, Shui Chongqing Univ Posts & Telecommun Sch Commun & Informat Engn Chongqing 400065 Peoples R China Univ Technol Sydney Sch Comp Sci Sydney NSW 2007 Australia

Software defined satellite-terrestrial networking has been identified as a promising approach to support the diversity of network services. As the fundamental issue to improve the flexibility of network management, the controller placement problem has been attracted increasing attentions for the integration of satellite and terrestrial networking. However, the impact of the dynamic coverage demands on the controller placement have not been well investigated in existed works, which makes them fail to adjust the coverage dynamically according to the actual demands, and leads to an obvious increase of networking response latency to the terminals. Aiming to address this issue, we propose a novel on-demand dynamic controller placement scheme, which can optimize the placement of controllers to improve networking response latency while meeting the dynamic coverage demands. Firstly, to optimize the number of controllers and meet the dynamic coverage demands, we define the coverage redundancy and propose the redundancy-based satellite subnet division method to establish the reliable satellite subnets. Secondly, we quantify the networking response latency of the distributed satellite subnet, and build an optimization mathematical model to optimize the number and location of controllers. Then, we formulate the controller placement problem into the capacitated facility location problem and build the mathematical model for it. Moreover, the on-demand dynamic approximation algorithm is proposed to obtain the approximation solution. Finally, the simulation results demonstrate that the proposed algorithm can effectively optimize the network latency compared with related algorithms.

关键词： Satellites Control systems Heuristic algorithms approximation algorithms Reliability Low earth orbit satellites Software Software defined satellite-terrestrial networking controller placement problem satellite subnet division networking response latency approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Randomized rounding algorithms for large scale unsplittable flow problems

引用

JOURNAL OF HEURISTICS 2021年第6期27卷 1081-1110页

作者： Lamothe, Francois Rachelson, Emmanuel Hait, Alain Baudoin, Cedric Dupe, Jean-Baptiste Univ Toulouse ISAE SUPAERO Toulouse France Thales Alenia Space Toulouse France Ctr Natl Etud Spatiales CNES Toulouse France

Unsplittable flow problems cover a wide range of telecommunication and transportation problems and their efficient resolution is key to a number of applications. In this work, we study algorithms that can scale up to large graphs and important numbers of commodities. We present and analyze in detail a heuristic based on the linear relaxation of the problem and randomized rounding. We provide empirical evidence that this approach is competitive with state-of-the-art resolution methods either by its scaling performance or by the quality of its solutions. We provide a variation of the heuristic which has the same approximation factor as the state-of-the-art approximation algorithm. We also derive a tighter analysis for the approximation factor of both the variation and the state-of-the-art algorithm. We introduce a new objective function for the unsplittable flow problem and discuss its differences with the classical congestion objective function. Finally, we discuss the gap in practical performance and theoretical guarantees between all the aforementioned algorithms.

关键词： Unsplittable flows Randomized rounding Heuristic approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximating Edit Distance in Truly Subquadratic Time: Quantum and MapReduce

引用

JOURNAL OF THE ACM 2021年第3期68卷 1–41页

作者： Boroujeni, Mahdi Ehsani, Soheil Ghodsi, Mohammad Hajiaghayi, Mohammadtaghi Seddighin, Saeed Sharif Univ Technol Azadi St Tehran Iran Univ Maryland College Pk MD 20742 USA Toyota Technol Inst Chicago Chicago IL USA Inst Res Fundamental Sci IPM Tehran Iran

The edit distance between two strings is defined as the smallest number of insertions, deletions, and substitutions that need to be made to transform one of the strings to another one. Approximating edit distance in subquadratic time is "one of the biggest unsolved problems in the field of combinatorial pattern matching" [37]. Our main result is a quantum constant approximation algorithm for computing the edit distance in truly subquadratic time. More precisely, we give an O(n(1.810)) quantum algorithm that approximates the edit distance within a factor of 3. We further extend this result to an O(n(1.708)) quantum algorithm that approximates the edit distance within a larger constant factor. Our solutions are based on a framework for approximating edit distance in parallel settings. This framework requires as black box an algorithm that computes the distances of several smaller strings all at once. For a quantum algorithm, we reduce the black box to metric estimation and provide efficient algorithms for approximating it. We further show that this framework enables us to approximate edit distance in distributed settings. To this end, we provide a MapReduce algorithm to approximate edit distance within a factor of 1 + epsilon, with sublinearly many machines and sublinear memory. Also, our algorithm runs in a logarithmic number of rounds.

关键词： Edit distance approximation algorithm subquadratic time algorithm quantum algorithm parallel algorithm MapReduce

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：