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

An approximation algorithm for Optimal Piecewise Linear Interpolations of Bounded Variable Products

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2023年第2期199卷 569-599页

作者： Baermann, Andreas Burlacu, Robert Hager, Lukas Kutzer, Katja Friedrich Alexander Univ Erlangen Nurnberg Discrete Optimizat Cauerstr 11 D-91058 Erlangen Germany

We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as building blocks, we construct a triangulation scheme called crossing swords that requires at most - times the number of simplices in any optimal triangulation. In other words, we derive an approximation algorithm for the optimal triangulation problem. We also show that crossing swords yields optimal triangulations in the case that each simplex has at least one axis-parallel edge. Furthermore, we present approximation guarantees for other well-known triangulation schemes, namely for the red refinement and longest-edge bisection strategies as well as for a generalized version of K1-triangulations. Thereby, we are able to show that our novel approach dominates previous triangulation schemes from the literature, which is underlined by illustrative numerical examples.

关键词： Nonconvex quadratic programming Piecewise linear approximations Triangulations approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Smart sewing work measurement system using IoT-based power monitoring device and approximation algorithm

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2020年第20期58卷 6202-6216页

作者： Jung, Woo-Kyun Kim, Hyungjung Park, Young-Chul Lee, Jae-Won Ahn, Sung-Hoon Seoul Natl Univ Dept Mech & Aerosp Engn Seoul South Korea Hojeon Ltd Seoul South Korea Seoul Natl Univ Inst Adv Machines & Design Seoul South Korea

To enable Small and Medium-sized Enterprises (SMEs) level garment manufacturers to measure and monitor the work of individual workers without incurring a large financial burden, a smart sewing work measurement system was developed using an IoT-based power monitoring device and an approximation algorithm. The amount of electric current used in the sewing work was measured, and the measured data was transmitted to a server using Wi-Fi communication. The analysis of the data was conducted through the Symbolic Aggregate approximation (SAX) and Dynamic Time Warping (DTW) methods. The daily workload of each worker derived from the system developed through this study showed an error rate of 8% compared to the actual workload, and the time measured by the sensor was different from the time measured by a manager using a stopwatch. These differences are considered to be due to measurement errors in the stopwatch, human noise from the measurer and the operator, and the relatively few samples relative to the total workload. The IoT-based power monitoring and work measurement system for sewing work developed through this study can be applied to smart garment manufacturing factories at an acceptable cost level, while SMEs can realise high recognition rates and semi-real-time monitoring.

关键词： work measurement IoT-based power monitoring sewing machine approximation algorithm time series analysis

来源：评论

学校读者我要写书评

暂无评论

A randomized approximation algorithm for metric triangle packing

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2021年第1期41卷 12-27页

作者： Chen, Yong Chen, Zhi-Zhong Lin, Guohui Wang, Lusheng Zhang, An Hangzhou Dianzi Univ Dept Math Hangzhou Peoples R China Tokyo Denki Univ Div Informat Syst Design Saitama Japan Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China

Given an edge-weighted complete graph G on 3n vertices, the maximum-weight triangle packing problem asks for a collection of n vertex-disjoint triangles in G such that the total weight of edges in these n triangles is maximized. Although the problem has been extensively studied in the literature, it is surprising that prior to this work, no nontrivial approximation algorithm had been designed and analyzed for its metric case, where the edge weights in the input graph satisfy the triangle inequality. In this paper, we design the first nontrivial polynomial-time approximation algorithm for the maximum-weight metric triangle packing problem. Our algorithm is randomized and achieves an expected approximation ratio of 0.66768 - epsilon for any constant epsilon > 0.

关键词： Triangle packing Metric approximation algorithm Randomized algorithm Maximum cycle cover

来源：评论

学校读者我要写书评

暂无评论

An improved approximation algorithm for the complementary maximal strip recovery problem

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第3期78卷 720-730页

作者： Lin, Guohui Goebel, Randy Li, Zhong Wang, Lusheng Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada City Univ Hong Kong Dept Comp Sci Kowloon Hong Kong Peoples R China

Given two genomic maps G(1) and G(2) each represented as a sequence of n gene markers, the maximal strip recovery (MSR) problem is to retain the maximum number of markers in both G(1) and G(2) such that the resultant subsequences, denoted as G(1)* and G(2)* can be partitioned into the same set of maximal strips, which are common substrings of length greater than or equal to two. The complementary maximal strip recovery (CMSR) problem has the complementary goal to delete the minimum number of markers. Both MSR and CMSR have been shown to be NP-hard and APX-complete, and they admit a 4-approximation and a 3-approximation respectively. In this paper, we present an improved 7/3-approximation algorithm for the CMSR problem, with its worst-case performance analysis done through a local amortization with a re-weighting scheme. (C) 2011 Elsevier Inc. All rights reserved.

关键词： Maximal strip recovery approximation algorithm Local amortized analysis Re-weighting scheme

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for vehicle routing with compatibility constraints

引用

OPERATIONS RESEARCH LETTERS 2018年第6期46卷 579-584页

作者： Yu, Miao Nagarajan, Viswanath Shen, Siqian Univ Michigan Dept Ind & Operat Engn Ann Arbor MI 48109 USA

We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor. (ii) runs in a short amount of time and (iii) produces solutions comparable to the best feasible solutions found by a direct integer program formulation. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Vehicle routing Minimum makespan approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A simple approximation algorithm for minimum weight partial connected set cover

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第3期34卷 956-963页

作者： Zhang, Yubai Ran, Yingli Zhang, Zhao Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China

This paper studies the minimum weight partial connected set cover problem (PCSC). Given an element set U, a collection of subsets of U, a weight function c : , a connected graph on vertex set , and a positive integer , the goal is to find a minimum weight subcollection such that the subgraph of G induced by is connected, , and the weight of is minimum. If the graph has the property that any two sets with a common element has hop distance at most r in , then the problem is called r-hop PCSC. We presented an -approximation algorithm for the minimum weight 1-hop PCSC problem and an -approximation algorithm for the minimum cardinality r-hop PCSC problem. Our performance ratio improves previous results and our method is much simpler than previous methods.

关键词： Partial connected set cover Budgeted connected set cover approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Deterministic approximation algorithm for submodular maximization subject to a matroid constraint

引用

INTERNATIONAL JOURNAL OF CARDIOLOGY 2021年 343卷 1-15页

作者： Sun, Xin Xu, Dachuan Guo, Longkun Li, Min Beijing Univ Technol Dept Operat Res & Informat Engn Beijing 100124 Peoples R China Qilu Univ Technol Shandong Comp Sci Ctr Sch Comp Sci & Technol Shandong Key Lab Comp NetworksShandong Acad Sci Jinan 250353 Peoples R China Fuzhou Univ Sch Comp & Data Sci Fuzhou 350116 Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China

In this paper, we study the generalized submodular maximization problem with a nonnegative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter alpha is an element of [0, 1] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for alpha = 1. For general value of the curvature parameter alpha is an element of [0, 1], we present an approximation algorithm with a factor of 1+h(alpha)(y)+Delta.[3+alpha-(2+alpha)y-(1+alpha)h(alpha)(y)]/2+alpha+(1+alpha)(1-y), where y is an element of [0, 1] is a predefined parameter for tuning the ratio. In particular, when alpha = 1 we obtain a ratio 0.5008 when setting y = 0.9, coinciding with the renowned state-of-art approximate ratio; when alpha = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions. (C) 2021 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Submodular maximization Total curvature Matroid constraint Deterministic algorithm ADAPTIVE COMPLEXITY SET OPTIMIZATION

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the Noah's Ark Problem with Random Feature Loss

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2011年第2期8卷 551-556页

作者： Hickey, Glenn Blanchette, Mathieu Carmi, Paz Maheshwari, Anil Zeh, Norbert McGill Univ Sch Comp Sci Montreal PQ H3A 2A7 Canada Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Dalhousie Univ Fac Comp Sci Halifax NS B3H 1W5 Canada

The phylogenetic diversity (PD) of a set of species is a measure of their evolutionary distinctness based on a phylogenetic tree. PD is increasingly being adopted as an index of biodiversity in ecological conservation projects. The Noah's Ark Problem (NAP) is an NP-Hard optimization problem that abstracts a fundamental conservation challenge in asking to maximize the expected PD of a set of taxa given a fixed budget, where each taxon is associated with a cost of conservation and a probability of extinction. Only simplified instances of the problem, where one or more parameters are fixed as constants, have as of yet been addressed in the literature. Furthermore, it has been argued that PD is not an appropriate metric for models that allow information to be lost along paths in the tree. We therefore generalize the NAP to incorporate a proposed model of feature loss according to an exponential distribution and term this problem NAP with Loss (NAPL). In this paper, we present a pseudopolynomial time approximation scheme for NAPL.

关键词： Noah's ark problem phylogenetic diversity approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

SEPARATED CONTINUOUS CONIC PROGRAMMING: STRONG DUALITY AND AN approximation algorithm

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2009年第4期48卷 2118-2138页

作者： Wang, Xiaoqing Zhang, Shuzhong Yao, David D. Sun Yat Sen Univ Lingnan Univ Coll Guangzhou 510275 Guangdong Peoples R China Chinese Univ Hong Kong Dept Syst Engn & Engn Management Shatin Hong Kong Peoples R China Columbia Univ Dept Ind Engn & Operat Res New York NY 10027 USA

Motivated by recent applications in robust optimization and in sign-constrained linear-quadratic control, we study in this paper a new class of optimization problems called separated continuous conic programming (SCCP). Focusing on a symmetric primal-dual pair, we develop a strong duality theory for the SCCP. Our idea is to use discretization to connect the SCCP and its dual to two ordinary conic programs. We show if the latter are strongly feasible and with finite optimal values, a condition that is readily veri. able, then the strong duality holds for the SCCP. This approach also leads to a polynomial-time approximation algorithm that solves the SCCP to any required accuracy.

关键词： continuous optimization conic programming duality approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Novel approximation algorithm for the Shortest Vector Problem

引用

IEEE ACCESS 2024年 12卷 141026-141031页

作者： Ajitha Shenoy, K. B. Manipal Acad Higher Educ Manipal Inst Technol Dept Informat & Commun Technol Manipal 576104 Karnataka India

Finding the shortest vector in a lattice is a NP-hard problem. The best known approximation alpha(n-1/2), alpha >= 4/3, which is not algorithm for this problem is LLL algorithm with the approximation factor of alpha a good approximation factor. This work proposes a new polynomial time approximation algorithm for the shortest lattice vector problem. The proposed method makes use of only integer arithmetic and does not require Gram-Schmidt orthogonal basis for generating reduced basis. The proposed method is able to obtain an approximation factor of 1/(1-delta), where 0 <= delta < 1.

关键词： Vectors approximation algorithms Lattices Polynomials Numerical analysis NP-hard problem Object recognition Integer linear programming Indexes Computational complexity Lattice reduced basis shortest vector problem approximation algorithm computational complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：