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

Truthful Unsplittable Flow for Large Capacity Networks

ACM TRANSACTIONS ON algorithms 2010年第2期6卷 1–20页

作者： Azar, Yossi Gamzu, Iftah Gutner, Shai Microsoft Res Redmond WA 98052 USA Tel Aviv Univ Sch Comp Sci IL-69978 Tel Aviv Israel

The unsplittable flow problem is one of the most extensively studied optimization problems in the field of networking. Aninstance of it consists of an edge capacitated graph and a set of connection requests, each of which is associated with source and target vertices, a demand, and a value. The objective is to route a maximum value subset of requests subject to the edge capacities. It is a well known fact that as the capacities of the edges are larger with respect to the maximal demand among the requests, the problem can be approximated better. In particular, it is known that for sufficiently large capacities, the integrality gap of the corresponding integer linear program becomes 1 + epsilon, which can be matched by an algorithm that utilizes the randomized rounding technique. In this article, we focus our attention on the large capacities unsplittable flow problem in a game theoretic setting. In this setting, there are selfish agents, which control some of the requests characteristics, and may be dishonest about them. It is worth noting that in game theoretic settings many standard techniques, such as randomized rounding, violate certain monotonicity properties, which are imperative for truthfulness, and therefore cannot be employed. In light of this state of affairs, we design a monotone deterministic algorithm, which is based on a primal-dual machinery, which attains an approximation ratio of e/e-1, up to a disparity of epsilon away. This implies an improvement on the current best truthful mechanism, as well as an improvement on the current best combinatorial algorithm for the problem under consideration. Surprisingly, we demonstrate that any algorithm in the family of reasonable iterative path minimizing algorithms, cannot yield a better approximation ratio. Consequently, it follows that in order to achieve a monotone PTAS, if that exists, one would have to exert different techniques. We also consider the large capacities single-minded multi-unit combinatorial

关键词： algorithms Economics Theory Mechanism design approximation algorithms combinatorial and multi-unit auctions primal-dual method

来源：评论

学校读者我要写书评

暂无评论

Scheduling Frameworks for Cloud Container Services

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2018年第1期26卷 436-450页

作者： Zhou, Ruiting Li, Zongpeng Wu, Chuan Wuhan Univ Sch Comp Sci SKLSE Wuhan 430072 Peoples R China Univ Calgary Dept Comp Sci Calgary AB T2N 1N4 Canada Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

Compared with traditional virtual machines, cloud containers are more flexible and lightweight, emerging as the new norm of cloud resource provisioning. We exploit this new algorithm design space, and propose scheduling frameworks for cloud container services. Our offline and online schedulers permit partial execution, and allow a job to specify its job deadline, desired cloud containers, and inter-container dependence relations. We leverage the following classic and new techniques in our scheduling algorithm design. First, we apply the compact-exponential technique to express and handle nonconventional scheduling constraints. Second, we adopt the primal-dual framework that determines the primal solution based on its dual constraints in both the offline and online algorithms. The offline scheduling algorithm includes a new separation oracle to separate violated dual constraints, and works in concert with the randomized rounding technique to provide a near-optimal solution. The online scheduling algorithm leverages the online primaldual framework with a learning-based scheme for obtaining dual solutions. Both theoretical analysis and trace-driven simulations validate that our scheduling frameworks are computationally efficient and achieve close-to-optimal aggregate job valuation.

关键词： Cloud computing scheduling compact exponential optimization approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

On the maximum scatter traveling salesperson problem

引用

SIAM JOURNAL ON COMPUTING 1999年第2期29卷 515-544页

作者： Arkin, EM Chiang, YJ Mitchell, JSB Skiena, SS Yang, TC SUNY Stony Brook Dept Appl Math & Stat Stony Brook NY 11794 USA Polytech Univ Dept Comp & Informat Sci Brooklyn NY 11201 USA SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Kyungsung Univ Dept Comp Sci & Stat Pusan 608736 South Korea

We study the problem of computing a Hamiltonian tour (cycle) or path on a set of points in order to maximize the minimum edge length in the tour or path. This "maximum scatter" traveling salesperson problem (TSP) is closely related to the bottleneck TSP and is motivated by applications in manufacturing (e.g., sequencing of rivet operations) and medical imaging. In this paper, we give the first algorithmic study of these problems, including complexity results, approximation algorithms, and exact algorithms for special cases. In an attempt to model more accurately the real problems that arise in practice, we also generalize the basic problem to consider a more general measure of "scatter" in which points on a tour or path should be far not only from their immediate predecessor and successor, but also from other near-neighbors along the tour or path.

关键词： traveling salesperson problem traveling salesman problem maximum scatter TSP bottleneck TSP Hamiltonian cycle/path approximation algorithms matching optimization Posa conjecture Dirac's theorem

来源：评论

学校读者我要写书评

暂无评论

Joint transmission in cellular networks with CoMP-Stability and scheduling algorithms

引用

PERFORMANCE EVALUATION 2015年 91卷 38-55页

作者： Grebla, Guy Birand, Berk van de Ven, Peter Zussman, Gil Columbia Univ Dept Elect Engn New York NY 10027 USA CWI NL-1009 AB Amsterdam Netherlands

Due to the current trend towards smaller cells, an increasing number of users of cellular networks reside at the edge between two cells;these users typically receive poor service as a result of the relatively weak signal and strong interference. Coordinated Multi-Point (CoMP) with Joint Transmission UT) is a cellular networking technique allowing multiple Base Stations (BSs) to jointly transmit to a single user. This improves the users' reception quality and facilitates better service to cell-edge users. We consider a CoMP-enabled network, comprised of multiple BSs interconnected via a backhaul network. We formulate the OFDMA Joint Scheduling (OJS) problem of determining a subframe schedule and deciding if and how to use JT in order to maximize some utility function. We show that the OJS problem is NP-hard. We develop optimal and approximation algorithms for specific and general topologies, respectively. We consider a time dimension and study a queueing model with packet arrivals in which the service rates for each subframe are obtained by solving the OJS problem. We prove that when the problem is formulated with a specific utility function and solved optimally in each subframe, the resulting scheduling policy is throughput-optimal. Via extensive simulations we show that the bulk of the gains from CoMP with JT can be achieved with low capacity backhaul. Moreover, our algorithms distribute the network resources evenly, increasing the inter-cell users' throughput at only a slight cost to the intra-cell users. This is the first step towards a rigorous, network-level understanding of the impact of cross-layer scheduling algorithms on CoMP networks. (C) 2015 Published by Elsevier B.V.

关键词： Coordinated Multi-Point (CoMP) Joint transmission Cellular networks approximation algorithms Scheduling Queueing networks

来源：评论

学校读者我要写书评

暂无评论

Fast and High Accuracy 3D Point Cloud Registration for Automatic Reconstruction From Laser Scanning Data

引用

IEEE ACCESS 2023年 11卷 42497-42509页

作者： Xu, Anran Rao, Lei Fan, Guangyu Chen, Niansheng Shanghai Dianji Univ Lab Robot & Intelligent Technol Shanghai 201306 Peoples R China Shanghai Dianji Univ Coll Elect Informat Shanghai 201306 Peoples R China

Point cloud registration from laser scanning data is a technique to establish the mapping relationship between source and target point clouds, which has been widely used in automatic 3D reconstruction, pose estimation, localization, and navigation. While algorithms like Super4PCS and MSSF-4PCS can achieve registration without initial poses, they are relatively slow, less accurate, and require iterations. To address these issues, we propose a 3D point cloud registration algorithm based on interval segmentation and multi-dimensional feature. Firstly, the source and target point clouds are segmented internally and the point cloud curvature is designed to narrow down the search range for the registration between the segmented point clouds. Secondly, the corresponding four-point sets in the segmented areas of the source and target point clouds are determined using affine invariance constraints. Finally, a multi-dimensional feature vector based on curvature features and fast point feature histogram is established to determine the unique corresponding four-point set pairs, and the rigid body transformation matrix is solved accordingly. Our algorithm is tested on publicly available 3D point cloud data models Bunny, Dino, Dragon, and Horse from Stanford University. Results showed that our algorithm improved registration accuracy by 24.39% and registration efficiency by 46.21% compared to the MSSF-4PCS point cloud registration algorithm. Multiple sets of experimental results confirmed the effectiveness of our algorithm. The proposed 3D point cloud registration is proved to be fast with high accuracy, which can be utilized for automatic segmentation, reconstruction, and modelling from Laser Scanning Data.

关键词： Point cloud compression Three-dimensional displays Feature extraction Real-time systems approximation algorithms Matrix converters Histograms Point cloud registration point cloud curvature affine invariance multi-dimensional features

来源：评论

学校读者我要写书评

暂无评论

Boosting Perturbation-Based Iterative algorithms to Compute the Median String

引用

IEEE ACCESS 2021年 9卷 169299-169308页

作者： Mirabal, Pedro Abreu, Jose Seco, Diego Pedreira, Oscar Chavez, Edgar Univ Catolica Temuco Dept Informat Engn Temuco 4813302 Chile Univ Alicante Inst Univ Invest Informat Alicante 03690 Spain Univ Concepcion Dept Comp Sci Concepcion 3349001 Chile Millennium Inst Fdn Res Data Santiago Chile Univ A Coruna Database Lab La Coruna 15001 Spain Ctr Invest Cientica & Educ Super Ensenada Ensenada 22860 Baja California Mexico

The most competitive heuristics for calculating the median string are those that use perturbation-based iterative algorithms. Given the complexity of this problem, which under many formulations is NP-hard, the computational cost involved in the exact solution is not affordable. In this work, the heuristic algorithms that solve this problem are addressed, emphasizing its initialization and the policy to order possible editing operations. Both factors have a significant weight in the solution of this problem. Initial string selection influences the algorithm's speed of convergence, as does the criterion chosen to select the modification to be made in each iteration of the algorithm. To obtain the initial string, we use the median of a subset of the original dataset;to obtain this subset, we employ the Half Space Proximal (HSP) test to the median of the dataset. This test provides sufficient diversity within the members of the subset while at the same time fulfilling the centrality criterion. Similarly, we provide an analysis of the stop condition of the algorithm, improving its performance without substantially damaging the quality of the solution. To analyze the results of our experiments, we computed the execution time of each proposed modification of the algorithms, the number of computed editing distances, and the quality of the solution obtained. With these experiments, we empirically validated our proposal.

关键词： Prototypes Costs Convergence approximation algorithms Proposals Perturbation methods Heuristic algorithms Approximate median string algorithm initialization half space proximal neighbors

来源：评论

学校读者我要写书评

暂无评论

A Novel Neuroevolutionary Paradigm for Solving Strongly Nonlinear Singular Boundary Value Problems in Physiology

引用

IEEE ACCESS 2022年 10卷 21979-22002页

作者： Guo, Jiayi Khan, Adnan Sulaiman, Muhammad Kumam, Poom Nanjing Univ Posts & Telecommun Sch Software & Cyberspace Secur Nanjing 210049 Peoples R China Abdul Wali Khan Univ Mardan Dept Math Mardan 23200 Khyber Pakhtunk Pakistan King Mongkuts Univ Technol Thonburi KMUTT Fac Sci Dept Math KMUTT Fixed Point Theory & Applicat Res GrpKMUTT Bangkok 10140 Thailand King Mongkuts Univ Technol Thonburi KMUTT Ctr Excellence Theoret & Computat Sci TaCS CoE Sci Lab Bldg Bangkok 10140 Thailand China Med Univ China Med Univ Hosp Dept Med Res Taichung 40402 Taiwan

In the present research work, we designed a hybrid stochastic numerical solver to investigate nonlinear singular two-point boundary value problems with Neumann and Robin boundary conditions arising in various physical models. In this method, we hybridized Harris Hawks Optimizer with Interior Point Algorithm named HHO-IPA. We construct artificial neural networks (ANNs) model for the problem, and this model is tuned with the proposed scheme. This scheme overcomes the singular behavior of problems. The accuracy and applicability of the method are illustrated by finding absolute errors in the solution. The outcomes are compared with the results present in the literature to demonstrate the effectiveness and robustness of the scheme by considering four different nonlinear singular boundary value problems. Further, the convergence of the scheme is proved by performing computational complexity analysis. Moreover, the graphical overview of statistical analysis is added to our investigation to elaborate further on the scheme's stability, accuracy, and consistency.

关键词： Mathematical models approximation algorithms Convergence Boundary conditions Numerical models Computational complexity Rabbits Harris Hawk's optimizer nonlinearity singular boundary value problems artificial neural networks statistical analysis interior point method ordinary differential equations error estimation heuristics bio-inspired algorithms

来源：评论

学校读者我要写书评

暂无评论

Compressive Rate Estimation With Applications to Device-to-Device Communications

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2018年第10期17卷 7001-7012页

作者： Schreck, Jan Jung, Peter Stanczak, Slawomir Fraunhofer Heinrich Hertz Inst Wireless Commun & Networks Dept D-10587 Berlin Germany Intel Corp Intel Labs Santa Clara CA 95054 USA Tech Univ Berlin D-10623 Berlin Germany

We consider the pairing problem in network-assisted device-to-device communications. The pairing problem is stated as a rate estimation problem. To this end, we develop a framework that we call compressive rate estimation. We assume that the composite channel gain matrix (i.e., the matrix of all channel gains between all network nodes) is compressible and develop a novel sensing and reconstruction protocol for the estimation of achievable rates. The proposed sensing protocol exploits the superposition principle of the wireless channel and enables the receiving nodes to obtain non-adaptive random measurements of columns of the composite channel matrix. The random measurements are fed back to a central controller who decodes the composite channel gain matrix (or parts of it) and estimates individual user rates. We analyze the rate loss gap for a linear and a non-linear decoder and find the scaling laws according to the number of non-adaptive measurements.

关键词： Compressed sensing approximation algorithms device-to-device (D2D) communication channel state information (CSI) 5G mobile communication

来源：评论

学校读者我要写书评

暂无评论

Minimizing average completion time in the presence of release dates

引用

MATHEMATICAL PROGRAMMING 1998年第1-2期82卷 199-223页

作者： Phillips, C Stein, C Wein, J Polytech Univ Dept Comp Sci Brooklyn NY 11201 USA Sandia Natl Labs Albuquerque NM 87185 USA Sudikoff Lab Dept Comp Sci Hanover NH USA

A natural and basic problem in scheduling theory is to provide good average quality of service to a stream of jobs that arrive over time. In this paper we consider the problem of scheduling n jobs that are released over time in order to minimize the average completion time of the set of jobs. In contrast to the problem of minimizing average completion time when all jobs are available at time 0, all the problems that we consider are NP-hard, and essentially nothing was known about constructing good approximations ill polynomial time. We give the first constant-factor approximation algorithms for several variants of the single and parallel machine models. Many of the algorithms are based on interesting algorithmic and structural relationships between preemptive and nonpreemptive schedules and linear programming relaxations of both, Many of the algorithms generalize to the minimization of average weighted completion time as well. (C) 1998 The Mathematical Programming Society, *** by Elsevier Science B.V.

关键词： scheduling preemptive scheduling average weighted completion time approximation algorithms relaxations linear programming

来源：评论

学校读者我要写书评

暂无评论

Variance-Reduced Stochastic Quasi-Newton Methods for Decentralized Learning

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2023年 71卷 311-326页

作者： Zhang, Jiaojiao Liu, Huikang So, Anthony Man-Cho Ling, Qing KTH Royal Inst Technol Div Decis & Control Syst S-11428 Stockholm Sweden Shanghai Univ Finance & Econ Sch Informat Management & Engn Shanghai 200437 Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Sun Yat Sen Univ Sch Comp Sci & Engn Guangdong Prov Key Lab Computat Sci Guangzhou 510006 Guangdong Peoples R China Pazhou Lab Guangzhou 510300 Guangdong Peoples R China

In this work, we investigate stochastic quasi-Newton methods for minimizing a finite sum of cost functions over a decentralized network. We first develop a general algorithmic framework, in which each node constructs a local, inexact quasi-Newton direction that asymptotically approaches the global, exact one at each time step. To do so, a local gradient approximation is constructed using dynamic average consensus to track the average of variance-reduced local stochastic gradients over the entire network, followed by a proper local Hessian inverse approximation. We show that under standard convexity and smoothness assumptions on the cost functions, the methods obtained from our framework converge linearly to the optimal solution if the local Hessian inverse approximations used have uniformly bounded positive eigenvalues. To construct the Hessian inverse approximations with the said boundedness property, we design two fully decentralized stochastic quasi-Newton methods-namely, the damped regularized limited-memory DFP (Davidon-Fletcher-Powell) and the damped limited-memory BFGS (Broyden-Fletcher-Goldfarb-Shanno)-which use a fixed moving window of past local gradient approximations and local decision variables to adaptively construct Hessian inverse approximations. A noteworthy feature of these methods is that they do not require extra sampling or communication. Numerical results show that the proposed decentralized stochastic quasi-Newton methods are much faster than the existing decentralized stochastic first-order algorithms.

关键词： Costs Convergence Signal processing algorithms approximation algorithms Cost function Newton method Computational complexity Decentralized optimization stochastic quasi-Newton methods variance reduction damped limited-memory DFP damped limited-memory BFGS

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：