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

approximation algorithms for the robust/soft-capacitated 2-level facility location problems

JOURNAL OF GLOBAL OPTIMIZATION 2018年第1期70卷 207-222页

作者： Wu, Chenchen Xu, Dachuan Zhang, Dongmei Zhang, Peng Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China Beijing Univ Technol Coll Appl Sci Dept Informat & Operat Res Beijing 100124 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China Shandong Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

In this work, we consider the robust/soft-capacitated 2-level facility location problems. For the robust version, we propose a primal-dual based -approximation algorithm via construction of an adapted instance which explores some open facilities in the optimal solution. For the soft-capacitated version, we propose a -approximation algorithm via construction of the associated uncapacitated version whose connection cost is re-defined appropriately.

关键词： Facility location problem approximation algorithm Primal-dual

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for precedence-constrained identical machine scheduling with rejection

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第1期35卷 318-330页

作者： Zhang, Xianzhao Xu, Dachuan Du, Donglei Wu, Chenchen Linyi Univ Coll Sci Linyi 276005 Peoples R China Beijing Univ Technol Dept Informat & Operat Res Coll Appl Sci Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China

We study a precedence-constrained identical parallel machine scheduling problem with rejection. There is a communication delay between any two jobs connected in the precedence network where jobs may be rejected with penalty. The goal is to minimize the sum of the makespan and the rejection cost. We propose two 3-approximation algorithms for this problem under linear and submodular rejection costs respectively. These two algorithms are both based on linear programming rounding technique.

关键词： Scheduling Rejection approximation algorithm Linear programming Rounding

来源：评论

学校读者我要写书评

暂无评论

Accelerating the 2+2+1 method for estimating local traveltime operators in nonlinear beamforming using GPU graphics cards

引用

JOURNAL OF GEOPHYSICS AND ENGINEERING 2022年第3期19卷 389-402页

作者： Sun, Yimin Silvestrov, Ilya Bakulin, Andrey Aramco Europe Aramco Res Ctr Delft NL-2628 ZD Delft Netherlands Saudi Aramco EXPEC Adv Res Ctr Dhahran 31311 Saudi Arabia

Local traveltime operators are an effective way to describe local kinematic wavefronts. They are useful for many applications. One of them is nonlinear beamforming for enhancing the signal-to-noise ratio of challenging seismic data. The so-called 2+2+1 method is a pragmatic approach to estimate unknown local traveltime operators from input data. However, its efficiency still has much room for improvement when the solution space is big. We accelerate the 2+2+1 method using graphics processing unit (GPU) computing with the Compute Unified Device Architecture (CUDA) programming language. We detail the CPU- and GPU-based 2+2+1 search algorithms and demonstrate the efficiency improvement using synthetic and field data examples. Compared to a standard multi-core CPU implementation, our new GPU implementation achieves almost the same quality results at only similar to 10% run-time cost.

关键词： GPU signal restoration geophysical signal processing approximation algorithm parallelization

来源：评论

学校读者我要写书评

暂无评论

Using approximation algorithms to Build Evidence Factors and Related Designs for Observational Studies

引用

JOURNAL OF COMPUTATIONAL AND GRAPHICAL STATISTICS 2019年第3期28卷 698-709页

作者： Karmakar, Bikram Small, Dylan S. Rosenbaum, Paul R. Univ Penn Wharton Sch Dept Stat Philadelphia PA 19104 USA

Observational or nonrandomized studies of treatment effects are often constructed with the aid of polynomial-time algorithms that optimally form matched treatment-control pairs or matched sets. Because each observational comparison may potentially be affected by bias, investigators often reinforce a single comparison with an additional comparison that is unlikely to be affected by the same biases, for instance using multiple control groups or evidence factors or control + instrument designs. Use of two comparisons affected by different biases may detect bias if the two comparisons disagree, or may show that two comparisons with different weakness concur in their conclusions. Even this simplest addition-a second comparison-creates design problems without polynomial-time solutions. Faced with a problem that no polynomial-time algorithm can solve, a so-called approximation algorithm is a type of compromise: it provides a solution in polynomial time that is provably not much worse than the unattainable optimal solution. Building upon existing techniques for related problems in operations research, we develop an approximation algorithm for minimum distance matching with near-fine balance for three comparison groups. This algorithm is a practical approach to most observational designs that add a second comparison. The method is applied to an observational study of the effects of side airbags on injury severity in the U.S. Fatality Analysis Reporting System. For many car makes and models, side airbags were initially unavailable, then later available as optional equipment for an additional fee, then still later provided as standard equipment. Within sets matched for make and model of car, for safety belt use, for direction of impact, and other covariates, we compare crashes in these three periods, where each comparison has different limitations. The method is implemented in the R package approxmatch, whose example reproduces some of the calculations. for this article are av

关键词： approximation algorithm Causal inference Control groups Evidence factors Matching Multiple observational study

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the bus evacuation problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2018年第1期36卷 131-141页

作者： Pedrosa, Lehilton L. C. Schouery, Rafael C. S. Univ Estadual Campinas Inst Comp Av Albert Einstein1251Cidade Univ BR-13083852 Campinas SP Brazil

We consider the bus evacuation problem. Given a positive integer B, a bipartite graph G with parts S and in a metric space and functions and , one wishes to find a set of B walks in G. Every walk in B should start at r and finish in T and r must be visited only once. Also, among all walks, each vertex i of S must be visited at least times and each vertex j of T must be visited at most times. The objective is to find a solution that minimizes the length of the longest walk. This problem arises in emergency planning situations where the walks correspond to the routes of B buses that must transport each group of people in S to a shelter in T, and the objective is to evacuate the entire population in the minimum amount of time. In this paper, we prove that approximating this problem by less than a constant is -hard and present a 10.2-approximation algorithm. Further, for the uncapacitated BEP, in which is infinity for each j, we give a 4.2-approximation algorithm.

关键词： Bus evacuation Emergency planning approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Constant approximation of Fréchet Distance in Strongly Subquadratic Time 25

Constant Approximation of Fréchet Distance in Strongly Subq...

引用

Proceedings of the 57th Annual ACM Symposium on Theory of Computing

作者： Siu-Wing Cheng Haoqiang Huang Shuo Zhang Hong Kong University of Science and Technology Hong Kong Hong Kong Renmin University of China Beijing China

ISBN: (纸本)9798400715105

Let τ and σ be two polygonal curves in ℝd for any fixed d. Suppose that τ and σ have n and m vertices, respectively, and m≤ n. While conditional lower bounds prevent approximating the Fréchet distance between τ and σ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of nc in strongly subquadratic time, for some constant c∈(0,1). We present a randomized algorithm with running time O(nm0.99log(n/ε)) that approximates the Fréchet distance within a factor of 7+ε, with a success probability at least 1−1/n6. We also adapt our techniques to develop a randomized algorithm that approximates the discrete Fréchet distance within a factor of 7+ε in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.

关键词： approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Highly Connected Multi-dominating Sets in Unit Disk Graphs

引用

algorithmICA 2018年第11期80卷 3270-3292页

作者： Fukunaga, Takuro Natl Inst Informat Tokyo Japan JST ERATO Kawarabayashi Large Graph Project Tokyo Japan

Given an undirected graph on a node set V and positive integers k and m, a k-connected m-dominating set ((k, m)-CDS) is defined as a subset S of V such that each node in has at least m neighbors in S, and a k-connected subgraph is induced by S. The weighted (k, m)-CDS problem is to find a minimum weight (k, m)-CDS in a given node-weighted graph. The problem is called the unweighted (k, m)-CDS problem if the objective is to minimize the cardinality of a (k, m)-CDS. These problems have been actively studied for unit disk graphs, motivated by the application of constructing a virtual backbone in a wireless ad hoc network. In this paper, we consider the case in which , and we present a simple -approximation algorithm for the unweighted (k, m)-CDS problem, and a primal-dual -approximation algorithm for the weighted (k, m)-CDS problem.

关键词： Connected dominating set Unit disk graph approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for optimization of real-valued general conjugate complex forms

引用

JOURNAL OF GLOBAL OPTIMIZATION 2018年第1期70卷 99-130页

作者： Fu, Taoran Jiang, Bo Li, Zhening Shanghai Jiao Tong Univ Sch Math Sci Shanghai 200240 Peoples R China Shanghai Univ Finance & Econ Sch Informat Management & Engn Res Ctr Management Sci & Data Analyt Shanghai 200433 Peoples R China Univ Portsmouth Dept Math Portsmouth PO1 3HF Hants England

Complex polynomial optimization has recently gained more attention in both theory and practice. In this paper, we study optimization of a real-valued general conjugate complex form over various popular constraint sets including the m-th roots of complex unity, the complex unit circle, and the complex unit sphere. A real-valued general conjugate complex form is a homogenous polynomial function of complex variables as well as their conjugates, and always takes real values. General conjugate form optimization is a wide class of complex polynomial optimization models, which include many homogenous polynomial optimization in the real domain with either discrete or continuous variables, and Hermitian quadratic form optimization as well as its higher degree extensions. All the problems under consideration are NP-hard in general and we focus on polynomial-time approximation algorithms with worst-case performance ratios. These approximation ratios improve previous results when restricting our problems to some special classes of complex polynomial optimization, and improve or equate previous results when restricting our problems to some special classes of polynomial optimization in the real domain. The algorithms are based on tensor relaxation and random sampling. Our novel technical contributions are to establish the first set of probability lower bounds for random sampling over the m-th root of unity, the complex unit circle, and the complex unit sphere, and to propose the first polarization formula linking general conjugate forms and complex multilinear forms. Some preliminary numerical experiments are conducted to show good performance of the proposed algorithms.

关键词： General conjugate form Complex polynomial optimization approximation algorithm Complex tensor Tensor relaxation Random sampling Probability bound

来源：评论

学校读者我要写书评

暂无评论

Resource Configuration for Cross-Server Deployment of Application-Oriented Microservices in Cloud-Edge Continuum with SLO Constraints 29

Resource Configuration for Cross-Server Deployment of Applic...

引用

29th IEEE International Conference on Parallel and Distributed Systems, ICPADS 2023

作者： Wang, Dong Shen, Hong Tian, Hui Central Queensland University School of Engineering and Technology Australia Sun Yat-sen University School of Computer Science and Engineering China Griffith University School of Information and Communication Technology Australia

ISBN: (纸本)9798350330717

To adapt to the emerging microservice-based architectures, user application requests are transformed from the traditional service-based monolithic configuration to that of multi-stage inner-dependent microservices. However, in a cloud-edge continuum, the distribution of microservices introduces extra communication overhead that could violate the Service Level Objectives (SLOs). Existing microservice-based resource allocation techniques have either considered only the case that instances belonging to the same microservice are deployed on the same server, or have not considered the case with SLO constraints. In this paper, we consider the case where instances belonging to the same microservice can be deployed across servers with SLO constraints. We propose a novel linear program (LP) based resource configurator to determine the desired number of instances of each microservice that edge servers should resource based on performance estimation for application requests such that the total cost of allocated resources of all needed microservices is minimized under the constraint that the maximum microservice completion time satisfies the given service level objective (SLO). We prove that our resource configurator achieves the worst-case performance guarantee (√2 + 1)2 by rigorous derivation. In comparison with the state-of-the-art microservice allocation methods, experimental results show that our proposed resource configurator reduces the computational resource usage by 7.6%, and the memory resources by 11.3% while guaranteeing the SLOs. © 2023 IEEE.

关键词： approximation algorithm Microservices task scheduling

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the robust facility leasing problem

引用

OPTIMIZATION LETTERS 2018年第3期12卷 625-637页

作者： Han, Lu Xu, Dachuan Li, Min Zhang, Dongmei Beijing Univ Technol Dept Informat & Operat Res Coll Appl Sci 100 Pingleyuan Beijing 100124 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Shandong Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Shandong Peoples R China

In this paper, we consider the robust facility leasing problem (RFLE), which is a variant of the well-known facility leasing problem. In this problem, we are given a facility location set, a client location set of cardinality n, time periods {1, 2, ..., T} and a nonnegative integer q < n. At each time period t, a subset of clients Dt arrives. There are K lease types for all facilities. Leasing a facility i of a type k at any time period s incurs a leasing cost f(i)(k) such that facility i is opened at time period s with a lease length lk. Each client in D-t can only be assigned to a facility whose open interval contains t. Assigning a client j to a facility i incurs a serving cost c(ij). We want to lease some facilities to serve at least n - q clients such that the total cost including leasing and serving cost is minimized. Using the standard primal-dual technique, we present a 6-approximation algorithm for the RFLE. We further offer a refined 3-approximation algorithm by modifying the phase of constructing an integer primal feasible solution with a careful recognition on the leasing facilities.

关键词： Facility leasing problem Robust approximation algorithm Primal-dual

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：