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

作者： Shen, Xiangkun University of Michigan

学位级别：Ph.D.

This thesis presents linear and convex programming based algorithms for NP-hard discrete optimization problems, mainly with applications in network design. Network design problems aim to find a minimal/maximal weighted subgraph satisfying given properties. The problems studied include maximum cut, buy-at-bulk network design, throughput maximization, and unrelated machine scheduling. This thesis considers different models of input uncertainty: the traditional deterministic setting, the online setting where inputs arrive over time and the stochastic setting where inputs are drawn from some probability distribution. Our approach to these problems involves solving suitable convex relaxations and then using rounding procedures to convert the fractional solutions to integer solutions. The specific contributions of this thesis include (1) approximation algorithms for a constrained variant of the maximum cut problem using the Sherali-Adams LP hierarchy; (2) online primal-dual algorithms for covering and packing with Lq norm objectives; (3) approximation algorithms for stochastic unrelated machine scheduling.

关键词： approximation algorithm Linear programming Stochastic optimization Online algorithm Network design Thesis

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms on consistent dynamic map labeling

引用

THEORETICAL COMPUTER SCIENCE 2016年 640卷 84-93页

作者： Liao, Chung-Shou Liang, Chih-Wei Poon, Sheung Hung Natl Tsing Hua Univ Dept Ind Engn & Engn Management Hsinchu 30013 Taiwan Univ Teknol Brunei Sch Comp & Informat BE-1410 Gadong Brunei

We consider the dynamic map labeling problem: given a set of rectangular labels on the map, the goal is to appropriately select visible ranges for all the labels such that no two consistent labels overlap at every scale and the sum of total visible ranges is maximized. This is also called the active range optimization (ARO) problem defined by Been et al. (2006) [2]. We propose approximation algorithms for several variants of this problem. For the simple ARO problem, we provide a 3c logn-approximation algorithm for unit-width rectangular labels if there is a c-approximation algorithm for the unit-width label placement problem in the plane;and a randomized polynomial-time O(logn log logn)-approximation algorithm for arbitrary rectangular labels. For the general ARO problem, we prove that it remains NP-complete even for congruent square labels with equal selectable scale range. Moreover, we contribute 12-approximation algorithms for both arbitrary square labels and unit-width rectangular labels, and a 6-approximation algorithm for congruent square labels, and show that the bounds are tight. (C) 2016 Elsevier B.V. All rights reserved.

关键词： approximation algorithm Active range optimization Dynamic map labeling NP-complete

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: approximation algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale 17

Brief Announcement: Approximation Algorithms for Unsplittabl...

引用

29th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Bjelde, Antje Klimm, Max Schmand, Daniel Humboldt Univ Sch Business & Econ Spandauer Str 1 D-10789 Berlin Germany Rhein Westfal TH Aachen Sch Business & Econ Kackertstr 7 D-52072 Aachen Germany

ISBN: (纸本)9781450345934

We study general resource allocation problems with a diseconomy of scale. Given a finite set of commodities that request certain resources, the cost of each resource grows superlinearly with the demand for it, and our goal is to minimize the total cost of the resources. In large systems with limited coordination, it is natural to consider local dynamics where in each step a single commodity switches its allocated resources whenever the new solution after the switch has smaller total cost over all commodities. This yields a deterministic and polynomial time algorithm with approximation factor arbitrarily close to the locality gap, i.e., the worst case ratio of the cost of a local optimal and a global optimal solution. For costs that are polynomials with non-negative coefficients and maximal degree d, we provide a locality gap for weighted problems that is tight for all values of d. For unweighted problems, the locality gap asymptotically matches the approximation guarantee of the currently best known centralized algorithm [Makarychev, Srividenko FOCS14] but only requires local knowledge of the commodities.

关键词： approximation algorithm Distributed algorithm Locality Gap Energy Efficiency Congestion Games

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for the Weighted t-Uniform Sparsest Cut and some other graph partitioning problems

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2016年第6期82卷 1044-1063页

作者： Hasan, Mohammad Khairul Chwa, Kyung-Yong Korea Adv Inst Sci & Technol Div Comp Sci Taejon 305701 South Korea

We study the Weighted t-Uniform Sparsest Cut (Weighted t-USC) and other related problems. In an instance of the Weighted t-USC problem, a parameter t and an undirected graph G = (V, E) with edge-weights w : E -> 1R(>=)0 and vertex-weights : V -> R+ are given. The goal is to find a vertex set S subset of V with vertical bar S vertical bar <= t while minimizing w(S, V\S)/eta(S), where w(S, V \ S) is the total weight of the edges with exactly one endpoint in S and eta(S) = Sigma(v is an element of S) eta(v) For this problem, we present a (0 (log t), 1 + is an element of) factor bicriteria approximation lgorithm. Our algorithm outperforms the current best algorithm when t = n(o(1)). We also present better approximation algorithms for Weighted rho-Unbalanced Cut and Min-Max k-Partitioning problems. (C) 2016 Elsevier Inc. All rights reserved.

关键词： approximation algorithm Sparsest cut Graph partitioning Linear programming Clustering

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique

引用

THEORETICAL COMPUTER SCIENCE 2016年 630卷 117-125页

作者： Xu, Dachuan Wang, Fengmin Du, Donglei Wu, Chenchen Beijing Univ Technol Coll Appl Sci 100 Pingleyuan Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm POB 4400 Fredericton NB E3B 5A3 Canada Tianjin Univ Technol Coll Sci Tianjin 300384 Peoples R China

The notion of penalty has been introduced into many combinatorial optimization models. In this paper, we consider the submodular vertex cover problems with linear and submodular penalties, which are two variants of the submodular vertex cover problem where not all the edges are required to be covered by a vertex cover, and the uncovered edges are penalized. The problem is to determine a vertex subset to cover some edges and penalize the uncovered edges such that the total cost including covering and penalty is minimized. To overcome the difficulty of implementing the primal-dual framework directly, we relax the two dual programs to slightly weaker versions. We then present two primal dual approximation algorithms with approximation ratios of 2 and 4, respectively. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Penalty Submodular Vertex cover Primal-dual approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation AND KERNELIZATION FOR CHORDAL VERTEX DELETION

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2018年第3期32卷 2258-2301页

作者： Jansen, Bart M. P. Pilipczuk, Marcin Eindhoven Univ Technol Dept Math & Comp Sci NL-5600 MB Eindhoven Netherlands Univ Warsaw Inst Informat PL-02097 Warsaw Poland

The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size. Using a new Erdos-Posa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of ChVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [ D. Marx, "Chordal Deletion Is Fixed-Parameter Tractable," in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37-48]. To obtain the kernelization, we develop the first poly(opt)-approximation algorithm for ChVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k(4) log(2) k).

关键词： kernelization algorithm approximation algorithm chordal vertex deletion

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for minimum weight partial connected set cover problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第2期31卷 696-712页

作者： Liang, Dongyue Zhang, Zhao Liu, Xianliang Wang, Wei Jiang, Yaolin Xi An Jiao Tong Univ Sch Math & Stat Xian 710049 Peoples R China Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Peoples R China

In the Minimum Weight Partial Connected Set Cover problem, we are given a finite ground set , an integer , a collection of subsets of , and a connected graph on vertex set , the goal is to find a minimum weight subcollection of which covers at least elements of and induces a connected subgraph in . In this paper, we derive a "partial cover property" for the greedy solution of the Minimum Weight Set Cover problem, based on which we present (a) for the weighted version under the assumption that any pair of sets in with nonempty intersection are adjacent in (the Minimum Weight Partial Connected Vertex Cover problem falls into this range), an approximation algorithm with performance ratio , and (b) for the cardinality version under the assumption that any pair of sets in with nonempty intersection are at most -hops away from each other (the Minimum Partial Connected -Hop Dominating Set problem falls into this range), an approximation algorithm with performance ratio , where , is the Harmonic number, and is the performance ratio for the Minimum Quota Node-Weighted Steiner Tree problem.

关键词： Set cover Greedy algorithm approximation algorithm Submodular function

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for scheduling on multi-core processor with shared speedup resources

引用

DISCRETE OPTIMIZATION 2016年 20卷 11-22页

作者： Chen, Xufeng Ye, Deshi Hangzhou Dianzi Univ Sch Sci Dept Math Hangzhou 310018 Zhejiang Peoples R China Zhejiang Univ Coll Comp Sci Hangzhou 310027 Zhejiang Peoples R China

We consider a joint resource partition and scheduling problem. We are given m identical cores and discrete resources of total size k. We need to partition the resources among these cores. A set of jobs must be processed non-preemptively on these cores after the resource partition. The processing time of a job on a core depends on the size of resources allocated to that corresponding core. The resource allocation scheme is static, i.e., we cannot change the amount of resources that was allocated to a core during the whole scheduling. Hassidim et al. (2013) investigated this problem with a general processing time function, i.e., the processing time of a job is an arbitrary function of the level of resources allocated to that core. They provided an algorithm with approximation ratio of 36. In this paper, we improve the approximation ratio to 8 by presenting a new resource partition scheme. Next, we consider a special model where the core's speed is proportional to its allocated resource, then we present two algorithms with improved approximation ratios. (C) 2016 Elsevier B.V. All rights reserved.

关键词： Multi-core scheduling approximation algorithm Resource allocation

来源：评论

学校读者我要写书评

暂无评论

High Multiplicity Strip Packing Problem With Three Rectangle Types

High Multiplicity Strip Packing Problem With Three Rectangle...

引用

作者： Andy Yu University of Western Ontario

学位级别：硕士

The two-dimensional strip packing problem (2D-SPP) involves packing a set R = { r 1,..., r n } of n rectangular items into a strip of width 1 and unbounded height, where each rectangular item r i has width 0 < w i ≤ 1 and height 0 < h i ≤ 1. The objective is to find a packing for all these items, without overlaps or rotations, that minimizes the total height of the strip used. 2D-SPP is strongly NP -hard and has practical applications including stock cutting, scheduling, and reducing peak power demand in smart-grids. This thesis considers a special case of 2D-SPP in which the set of rectangular items R has three distinct rectangle sizes or types. We present a new OPT + 5/3 polynomial-time approximation algorithm, where OPT is the value of an optimum solution. This algorithm is an improvement over the previously best OPT + 2 polynomial-time approximation algorithm for the problem.

关键词： high multiplicity strip packing approximation algorithm optimization

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for minimum (weight) connected k-path vertex cover

引用

DISCRETE APPLIED MATHEMATICS 2016年 205卷 101-108页

作者： Li, Xiaosong Zhang, Zhao Huang, Xiaohui Xinjiang Univ Coll Math & Syst Sci Urumqi 830046 Xinjiang Peoples R China Zhejiang Normal Univ Coll Math Phys & Informat Engn Jinhua 321004 Zhejiang Peoples R China

A vertex subset C of a connected graph G is called a connected k-path vertex cover (CVCPk) if every path on k vertices contains at least one vertex from C, and the subgraph of G induced by C is connected. This concept originated in the field of security and supervisory control. This paper studies the minimum (weight) CVCPk problem. We first show that the minimum weight CVCPk problem can be solved in time O(n) when the graph is a tree, and can be solved in time O(m) when the graph is a uni-cyclic graph whose unique cycle has length r, where n is the number of vertices. Making use of the algorithm on trees, we present a k-approximation algorithm for the minimum (cardinality) CVCPk problem under the assumption that the graph has girth at least k. An example is given showing that performance ratio k is asymptotically tight for our algorithm. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Connected k-path vertex cover Weight Tree Girth approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：