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

Constant-Factor approximation algorithms for Parity-Constrained Facility Location and k-Center

ALGORITHMICA 2023年第7期85卷 1883-1911页

作者： Kim, Kangsan Shin, Yongho An, Hyung-Chan Devsisters Corp Seoul South Korea Yonsei Univ Dept Comp Sci Seoul South Korea

Facility location is a prominent optimization problem that has inspired a large quantity of both theoretical and practical studies in combinatorial optimization. Although the problem has been investigated under various settings reflecting typical structures within the optimization problems of practical interest, little is known on how the problem behaves in conjunction with parity constraints. This shortfall of understanding was rather discouraging when we consider the central role of parity in the field of combinatorics. In this paper, we present the first constant-factor approximation algorithm for the facility location problem with parity constraints. We are given as the input a metric on a set of facilities and clients, the opening cost of each facility, and the parity requirement-odd, even, or unconstrained-of every facility in this problem. The objective is to open a subset of facilities and assign every client to an open facility so as to minimize the sum of the total opening costs and the assignment distances, but subject to the condition that the number of clients assigned to each open facility must have the same parity as its requirement. Although the unconstrained facility location problem as a relaxation for this parity-constrained generalization has unbounded gap, we demonstrate that it yields a structured solution whose parity violation can be corrected at small cost. This correction is prescribed by a T-join on an auxiliary graph constructed by the algorithm. This auxiliary graph does not satisfy the triangle inequality, but we show that a carefully chosen set of shortcutting operations leads to a cheap and sparse T-join. Finally, we bound the correction cost by exhibiting a combinatorial multi-step construction of an upper bound. We also consider the parity-constrained k-center problem, the bottleneck optimization variant of parity-constrained facility location. We present the first constant-factor approximation algorithm also for this problem.

关键词： Facility location problems approximation algorithms k-center Parity constraints Clustering problems

来源：评论

学校读者我要写书评

暂无评论

Constant approximation algorithms for the one warehouse multiple retailers problem with backlog or lost-sales

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2016年第1期250卷 155-163页

作者： Gayon, J-P. Massonnet, G. Rapine, C. Stauffer, G. Lab G SCOP 46 Ave Felix Viallet F-38031 Grenoble 1 France INRIA Grenoble Rhone Alpes 655 Ave Europe F-38330 Montbonnot St Martin France Univ Lorraine Lab LGIPM F-57045 Metz 01 France

We consider the One Warehouse Multi-Retailer (OWMR) problem with deterministic time-varying demand in the case where shortages are allowed. Demand may be either backlogged or lost. We present a simple combinatorial algorithm to build an approximate solution from a decomposition of the system into single echelon subproblems. We establish that the algorithm has a performance guarantee of 3 for the OWMR with backlog under mild assumptions on the cost structure. In addition, we improve this guarantee to 2 in the special case of the Joint-Replenishment Problem (JRP) with backlog. As a by-product of our approach, we show that our decomposition provides a new lower bound of the optimal cost. A similar technique also leads to a 2-approximation for the OWMR problem with lost-sales. In all cases, the complexity of the algorithm is linear in the number of retailers and quadratic in the number of time periods, which makes it a valuable tool for practical applications. To the best of our knowledge, these are the first constant approximations for the OWMR with shortages. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.

关键词： approximation algorithms Lot-sizing Inventory control Distribution systems

来源：评论

学校读者我要写书评

暂无评论

Exact and approximation algorithms for Geometric and Capacitated Set Cover Problems

引用

ALGORITHMICA 2012年第2期64卷 295-310页

作者： Berman, Piotr Karpinski, Marek Lingas, Andrzej Lund Univ Dept Comp Sci S-22100 Lund Sweden Penn State Univ Dept Comp Sci & Engn University Pk PA 16802 USA Univ Bonn Dept Comp Sci Bonn Germany

First, we study geometric variants of the standard set cover motivated by assignment of directional antenna and shipping with deadlines, providing the first known polynomial-time exact solutions. Next, we consider the following general (non-necessarily geometric) capacitated set cover problem. There is given a set of elements with real weights and a family of sets of the elements. One can use a set if it is a subset of one of the sets in the family and the sum of the weights of its elements is at most one. The goal is to cover all the elements with the allowed sets. We show that any polynomial-time algorithm that approximates the uncapacitated version of the set cover problem with ratio r can be converted to an approximation algorithm for the capacitated version with ratio r+1.357. In particular, the composition of these two results yields a polynomial-time approximation algorithm for the problem of covering a set of customers represented by a weighted n-point set with a minimum number of antennas of variable angular range and fixed capacity with ratio 2.357. This substantially improves on the best known approximation ratio for the latter antenna problem equal to 3. Furthermore, we provide a PTAS for the dual problem where the number of sets (e.g., antennas) to use is fixed and the task is to minimize the maximum set load, in case the sets correspond to line intervals or arcs. Finally, we discuss the approximability of the generalization of the antenna problem to include several base stations for antennas, and in particular show its APX-hardness already in the uncapacitated case.

关键词： Set cover Geometric set cover Capacitated set cover Assignment of directional antenna Shipping with deadlines approximation algorithms Polynomial-time approximation scheme APX-hardness Exact algorithms Time complexity

来源：评论

学校读者我要写书评

暂无评论

Simple approximation algorithms for MAXNAESP and hypergraph 2-colorability

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2001年第2期5卷 167-173页

作者： Gaur, DR Krishnamurti, R Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

Hypergraph 2-colorability, also known as set splitting, is a widely studied problem in graph theory. In this paper we study the maximization version of the same. We recast the problem as a special type of satisfiability problem and give approximation algorithms for it. Our results are valid for hypergraph 2-colorability, set splitting and MAX-CUT (which is a special case of hypergraph 2-colorability) because the reductions are approximation preserving. Here we study the MAXNAESP problem, the optimal solution to which is a truth assignment of the literals that maximizes the number of clauses satisfied. As a main result of the paper, we show that any locally optimal solution (a solution is locally optimal if its value cannot be increased by complementing assignments to literals and pairs of literals) is guaranteed a performance ratio of 1/2 + epsilon. This is an improvement over the ratio of 1/2 attributed to another local improvement heuristic for MAX-CUT (C. Papadimitriou, Computational Complexity, Addison Wesley, 1994). In fact we provide a bound of k/k+1 for this problem, where k greater than or equal to 3 is the minimum number of literals in a clause. Such locally optimal algorithms appear to subsume typical greedy algorithms that have been suggested for problems in the general domain of satisfiability. It should be noted that the NAESP problem where each clause has exactly two literals, is equivalent to MAX-CUT. However, obtaining good approximation ratios using semi-definite programming techniques (M. Goemans and D.P. Williamson, in Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994a, pp. 422-431) appears difficult. Also, the randomized rounding algorithm as well as the simple randomized algorithm both (M. Goemans and D.P. Williamson, SIAM J. Disc. Math, vol. 7, pp. 656-666, 1994b) yield a bound of 1/2 for the MAXNAESP problem. In contrast to this, the algorithm proposed in this paper obtains a bound of 1/2 + epsilon for this problem.

关键词： approximation algorithms hypergraph 2-colorability set splitting MAXNAESP MAX-CUT

来源：评论

学校读者我要写书评

暂无评论

Trajectory planning for robotic maintenance of pasture based on approximation algorithms

引用

BIOSYSTEMS ENGINEERING 2018年 174卷 219-230页

作者： Cariou, Christophe Gobor, Zoltan Irstea UR TSCF 9 Ave Blaise Pascal CS 20085 F-63178 Aubiere France Inst Agr Engn & Anim Husb LfL Bavarian State Res Ctr Agr Vottinger Str 36 D-85354 Freising Weihenstephan Germany

This paper addresses the problem of trajectory planning of a mobile robot for pasture maintenance comprising mulching weeds, reseeding patches without vegetation and spreading cowpats. Based on the sensor-based acquired data (points of interest), the proposed approach is to first use an approximation algorithm for data clustering in the form of non-convex and convex hulls. These hulls are then delimited by stair-shaped limits with respect to the working width of the robot, and their centres of gravity calculated. To minimise the travelled distance between the centres of gravity of the defined areas, the Travelling Salesman Problem is addressed via an evolutionary algorithm. Finally, kinematic and dynamic properties of the robot are considered in order to generate the final trajectory. The capabilities of the proposed approaches are highlighted through the processing of several datasets. (C) 2018 IAgrE. Published by Elsevier Ltd. All rights reserved.

关键词： Mobile robot Trajectory planning approximation algorithms TSP

来源：评论

学校读者我要写书评

暂无评论

Deterministic approximation algorithms for the maximum traveling salesman and maximum triangle packing problems

引用

DISCRETE APPLIED MATHEMATICS 2013年第13-14期161卷 2142-2157页

作者： van Zuylen, Anke Coll William & Mary Dept Math Williamsburg VA 23185 USA

We give derandomizations of known randomized approximation algorithms for the maximum traveling salesman problem and the maximum triangle packing problem: we show how to define pessimistic estimators for certain probabilities, based on the analysis of the randomized algorithms, and show that we can multiply the estimators to obtain pessimistic estimators for the expected weight of the solution. The method of pessimistic estimators (Raghavan (1988) 1141) then immediately implies that the randomized algorithms can be derandomized. For the maximum triangle packing problem, this gives deterministic algorithms with better approximation guarantees than what was previously known. The key idea in our analysis is the specification of conditions on pessimistic estimators of two expectations E [Y] and E [Z], under which the product of the pessimistic estimators is a pessimistic estimator of E [YZ], where Y and Z are two random variables. This approach can be useful when derandomizing algorithms for which one needs to bound the probability of some event that can be expressed as an intersection of multiple events;using our method, one can define pessimistic estimators for the probabilities of the individual events, and then multiply them to obtain a pessimistic estimator for the probability of the intersection of the events. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Maximum traveling salesman problem Maximum triangle packing approximation algorithms Derandomization Pessimistic estimators

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for inscribing or circumscribing an axially symmetric polygon to a convex polygon

Approximation algorithms for inscribing or circumscribing an...

引用

10th Annual International Conference on Computing and Combinatorics, COCOON 2004

作者： Ahn, Hee-Kap Brass, Peter Cheong, Otfried Na, Hyeon-Suk Shin, Chan-Su Vigneron, Antoine Korea Advanced Institute of Science and Technology Daejeon Korea Republic of Department of Computer Science City College of New York United States Department of Mathematics and Computer Science TU Eindhoven Eindhoven Netherlands School of Computing Soongsil University Seoul Korea Republic of School of Electr. and Inform. Engineering Hankuk University of Foreign Studies Yongin Korea Republic of Department of Computer Science National University of Singapore Singapore

ISBN: (纸本)354022856X

Given a convex polygon P with n vertices, we present algorithms to determine approximations of the largest axially symmetric convex polygon S contained in P, and the smallest such polygon S' that contains P. More precisely, for any Ε > 0, we can find an axially symmetric convex polygon Q ⊂ P with area |Q| > (1 − Ε)|S| in time O(n+1/Ε3/2), and we can find an axially symmetric convex polygon Q' containing P with area |Q'| 2) log(1/Ε)). If the vertices of P are given in a sorted array, we can obtain the same results in time (formula presented) log n+1/Ε3/2) and O((1/Ε) log n+(1/Ε2) log(1/Ε)) respectively. © Springer-Verlag Berlin Heidelberg 2004.

关键词： approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Successive Galerkin approximation algorithms for nonlinear optimal and robust control

引用

INTERNATIONAL JOURNAL OF CONTROL 1998年第5期71卷 717-743页

作者： Beard, RW McLain, TW Brigham Young Univ Dept Elect & Comp Engn Provo UT 84602 USA Brigham Young Univ Dept Mech Engn Provo UT 84602 USA

Nonlinear optimal control and nonlinear H(infinity) control are two of the most significant paradigms in nonlinear systems theory. Unfortunately, these problems require the solution of Hamilton-Jacobi equations, which are extremely difficult to solve in practice. To make matters worse, approximation techniques for these equations are inherently prone to the so-called 'curse of dimensionality'. While there have been many attempts to approximate these equations, solutions resulting in closed-loop control with well-defined stability and robustness have remained elusive. This paper describes a recent breakthrough in approximating the Hamilton-Jacobi-Bellman and Hamilton-Jacobi-Isaacs equations. Successive approximation and Galerkin approximation methods are combined to derive a novel algorithm that produces stabilizing, closed-loop control laws with well-defined stability regions. In addition, we show how the structure of the algorithm can be exploited to reduce the amount of computation from exponential to polynomial growth in the dimension of the state space. The algorithms are illustrated with several examples.

关键词： H-infinity-control Optimal feedback-control Optimal-regulators Bilinear-systems State feedback Curse of Dimensionality Equation H-infinity control nonlinear optimal control approximation algorithms State feedback Robust control control law state space

来源：评论

学校读者我要写书评

暂无评论

Sums of squares based approximation algorithms for MAX-SAT

引用

DISCRETE APPLIED MATHEMATICS 2008年第10期156卷 1754-1779页

作者： van Maaren, H. van Norden, L. Heule, M. J. H. Delft Univ Technol Fac Elect Engn Math & Comp Sci NL-2628 CD Delft Netherlands

We investigate the Semidefinite Programming based sums of squares (SOS) decomposition method, designed for global optimization of polynomials, in the context of the (Maximum) Satisfiability problem. To be specific, we examine the potential of this theory for providing tests for unsatisfiability and providing MAX-SAT upper bounds. We compare the SOS approach with existing upper bound and rounding techniques for the MAX-2-SAT case of Goemans and Williamson [Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. Assoc. Comput. Mach. 42(6) (1995) 1115-1145] and Feige and Goemans [Approximating the value of two prover proof systems, with applications to MAX2SAT and MAXDICUT, in: Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995, pp. 182-189] and the MAX-3-SAT case of Karloff and Zwick [A 7/8-approximation algorithm for MAX 3SAT? in: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, USA, IEEE Press, New York, 1997], which are based on Semidefinite Programming as well. We prove that for each of these algorithms there is an SOS-based counterpart which provides upper bounds at least as tight, but observably tighter in particular cases. Also, we propose a new randomized rounding technique based on the optimal solution of the SOS Semidefinite Program (SDP) which we experimentally compare with the appropriate existing rounding techniques. Further we investigate the implications to the decision variant SAT and compare experimental results with those yielded from the higher lifting approach of Anjos [On semidefinite programming relaxations for the satisfiability problem, Math. Methods Oper. Res. 60(3) (2004) 349-367;An improved semidefinite programming relaxation for the satisfiability problem, Math. Programming 102(3) (2005) 589-608;Semidefinite optimization approaches for satisfiability and maximum-satisfiability problems, J. Satisfiability

关键词： (Maximum) Satisfiability Semidefinite Programming sums of squares approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Generalized p-Center problems: Complexity results and approximation algorithms

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 1997年第3期100卷 594-607页

作者： Hochbaum, DS Pathria, A UNIV CALIF BERKELEY DEPT IND ENGN & OPERAT RES BERKELEY CA 94720 USA UNIV CALIF BERKELEY WALTER A HAAS SCH BUSINESS BERKELEY CA 94720 USA

In an earlier paper, two alternative p-Center problems, where the centers serving customers must be chosen so that exactly one node from each of p prespecified disjoint pairs of nodes is selected, were shown to be NP-complete. This paper considers a generalized version of these problems, in which the nodes from which the p servers are to be selected are partitioned into k sets and the number of servers selected from each set must be within a prespecified range. We refer to these problems as the 'Set' p-Center problems. We establish that the triangle inequality (Delta-inequality) versions of these problems, in which the edge weights are assumed to satisfy the triangle inequality, are also NP-complete. We also provide a polynomial time approximation algorithm for the two Delta-inequality Set p-Center problems that is optimal for one of the problems in the sense that no algorithm with polynomial running time can provide a better constant factor performance guarantee, unless P = NP. For the special case 'alternative' p-Center problems, which we refer to as the 'Pair' p-Center problems, we extend the previous results in several ways. For example, the results mentioned above for the Set p-Center problems also apply to the Pair p-Center problems. Furthermore, we establish and exploit a correspondence between satisfiability and the dominating set type of problems that naturally arise when considering the decision versions of the Pair p-Center problems. (C) 1997 Elsevier Science B.V.

关键词： p-Center approximation algorithms bottleneck optimization problems location of facilities

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：