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

Approximating Robust Bin Packing with Budgeted Uncertainty 1

16th International algorithms and Data Structures Symposium (WADS)

作者： Roy, Aniket Basu Bougeret, Marin Goldberg, Noam Poss, Michael Univ Montpellier CNRS LIRMM Montpellier France Bar Ilan Univ Dept Management IL-5290002 Ramat Gan Israel

ISBN: (数字)9783030247669

ISBN: (纸本)9783030247669;9783030247652

We consider robust variants of the bin-packing problem where the sizes of the items can take any value in a given uncertainty set U subset of xn(i=1)[(a) over bar (i), (a) over bar (i) + (a) over cap (i)], where (a) over bar is an element of [0, 1](n) represents the nominal sizes of the items and (a) over cap is an element of [0, 1](n) their possible deviations. We consider more specifically two uncertainty sets previously studied in the literature. The first set, denoted U-Gamma, contains scenarios in which at most Gamma is an element of N items deviate, each of them reaching its peak value (a) over bar (i) + (a) over cap (i), while each other item has its nominal value (a) over bar (i). The second set, denoted U-Omega, bounds by Omega is an element of [0, 1] the total amount of deviation in each scenario. We show that a variant of the next-fit algorithm provides a 2-approximation for model U-Omega, and a 2(Gamma + 1) approximation for model U-Gamma (which can be improved to 2 approximation for Gamma = 1). This motivates the question of the existence of a constant ratio approximation algorithm for the U-Gamma model. Our main result is to answer positively to this question by providing a 4.5 approximation for U-Gamma model based on dynamic programming.

关键词： Bin-packing Robust optimization approximation algorithm Next-fit Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

A Primal-Dual approximation algorithm for the Facility Location Problem with Submodular Penalties

引用

algorithmICA 2012年第1-2期63卷 191-200页

作者： Du, Donglei Lu, Ruixing Xu, Dachuan Beijing Univ Technol Dept Appl Math Beijing 100124 Peoples R China Univ New Brunswick Fac Business Adm Fredericton NB E3B 5A3 Canada

We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 933-942, 2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.

关键词： Facility location problem approximation algorithm Submodular function

来源：评论

学校读者我要写书评

暂无评论

Universal Facility Location in Generalized Metric Space 25th

Universal Facility Location in Generalized Metric Space

引用

25th International Computing and Combinatorics Conference (COCOON)

作者： Xu, Yicheng Xu, Dachuan Zhang, Yong Zou, Juan Chinese Acad Sci Shenzhen Inst Adv Technol Shenzhen 518055 Peoples R China Beijing Univ Technol Dept Operat Res & Sci Comp Beijing 100124 Peoples R China Qufu Normal Univ Sch Math Sci Qufu 273165 Shandong Peoples R China

ISBN: (纸本)9783030261764;9783030261757

We consider the universal facility location that extends several classical facility location problems like the incremental-cost facility location, concave-cost facility location, hard-capacitated facility location, soft-capacitated facility location, and of course, uncapacitated facility location. In this problem we are given a set of facilities F and clients C, as well as the distances between any pair of facility and client. Each facility i has its specific cost function f(i)(center dot) depending on the amount of clients assigned to that facility. The goal is to assign the clients to facilities such that the sum of facility and service costs is minimized. In metric facility location, the service cost is proportional to the distance between the client and its assigned facility. We study a cost measure known as l(2)(2) considered by Jain and Vazirani [J. ACM'01] and Fernandes et al. [Math. Program.'15] where the service cost is proportional to the squared distance. We extend their work to include the aforementioned variants of facility location. As our main contribution, a local search based (11.18 + epsilon)-approximation algorithm is proposed.

关键词： Universal facility location Capacitated facility location approximation algorithm Squared metric

来源：评论

学校读者我要写书评

暂无评论

The Seeding algorithm for Spherical k-Means Clustering with Penalties 1

引用

13th International Conference on algorithmic Aspects in Information and Management (AAIM)

作者： Ji, Sai Xu, Dachuan Guo, Longkun Li, Min Zhang, Dongmei Beijing Univ Technol Dept Operat Res & Sci Comp Beijing 100124 Peoples R China Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Fujian Peoples R China Shandong Normal Univ Sch Math & Stat Jinan 250014 Peoples R China Shandong Jianzhu Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

ISBN: (数字)9783030271954

ISBN: (纸本)9783030271954;9783030271947

Spherical k-means clustering is a generalization of k-means problem which is NP-hard and has widely applications in data mining. It aims to partition a collection of given data with unit length into k sets so as to minimize the within-cluster sum of cosine dissimilarity. In this paper, we introduce the spherical k-means clustering with penalties and give a 2 max{2, M}(1 + M)(ln k + 2)-approximate algorithm, where M is the ratio of the maximal and the minimal penalty values of the given data set.

关键词： approximation algorithm Spherical k-means clustering Penalty

来源：评论

学校读者我要写书评

暂无评论

Fast Fréchet Distance Between Curves with Long Edges

引用

International Journal of Computational Geometry and Applications 2019年第2期29卷 161-187页

作者： Gudmundsson, Joachim Mirzanezhad, Majid Mohades, Ali Wenk, Carola University of Sydney Australia Tulane University New Orleans United States Amirkabir University of Technology Iran

Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let P and Q be two polygonal curves in Rd with n and m vertices, respectively. We prove four results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in O((n + m)log(n + m)) time, (3) a linear-time d-approximation algorithm, and (4) a data structure that supports O(mlog2n)-time decision queries, where m is the number of vertices of the query curve and n the number of vertices of the preprocessed curve. © 2019 World Scientific Publishing Company.

关键词： approximation algorithm data structure The Fréchet distance

来源：评论

学校读者我要写书评

暂无评论

Service Function Chaining and Embedding with Spanning Closed Walk 20

Service Function Chaining and Embedding with Spanning Closed...

引用

IEEE 20th International Conference on High Performance Switching and Routing (HPSR)

作者： Zheng, Danyang Peng, Chengzong Liao, Xueting Luo, Guangchun Tian, Ling Cao, Xiaojun Georgia State Univ Dept Comp Sci Atlanta GA 30303 USA Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu Peoples R China

ISBN: (纸本)9781728116860

Network Function Virtualization (NFV) takes advantages of the emerging technologies in virtualization and automation to offer new ways in design, deployment, and management of networking services. In NFV, the proprietary hardware-based network functions are replaced by the software-based modules named as Virtual Network Functions (VNFs) or Service Functions (SFs). A network service request from the customer can be formed by multiple SFs. To satisfy a network service request, the service provider has to chain the SFs in the request into a Service Function Chain (SFC) and embed the constructed SFC onto the shared substrate network. In this paper, we comprehensively study how to composite and embed an SFC onto a shared substrate network with unique service function. We formulate this problem with the Integer Linear Programming (ILP) technique. We also propose an efficient heuristic algorithm with 2-approximation boundary, namely, Spanning Closed Walk based SFC Embedding (SCW-SFCE). Our extensive simulations and analysis show that the proposed approach can achieve near-optimal performance in a small network and outperform the Nearest Neighbour (NN) algorithm.

关键词： Network Function Virtualization Virtual Network Function Deployment approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

approximation and hardness results for the Max k-Uncut problem

引用

THEORETICAL COMPUTER SCIENCE 2018年 749卷 47-58页

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

In the study of the homophily law of large scale complex networks, we get a combinatorial optimization problem which we call the Max k-Uncut problem. Given an n-vertex undirected graph G = (V, E) with nonnegative weights {we vertical bar e is an element of E} defined on edges, and a positive integer k, the Max k-Uncut problem asks to find a partition (V-1, V-2, ..., V-k} of V such that the total weight of edges that are not cut is maximized. Intuitively, an edge that is not cut connects two vertices with the same or similar attributes since they are in the same part of the partition. Interestingly, the Max k-Uncut problem is just the complement of the classic Min k-Cut problem. For Max k-Uncut, we present a randomized (1 - k/n)(2)-approximation algorithm, a greedy (1 - 2(k - 1/n) approximation algorithm, and an Omega(1/2 alpha)-approximation algorithm by reducing it to Densest k-Subgraph, where alpha is the approximation ratio of the Densest k-Subgraph problem. More importantly, we show that Max k-Uncut and Densest k-Subgraph are in fact equivalent in approximability up to a factor of 2. We also prove an approximation hardness result for Max k-Uncut under the assumption P not equal NP. (C) 2017 Elsevier B.V. All rights reserved.

关键词： Max k-Uncut Densest k-Subgraph Homophily approximation algorithm Computational complexity

来源：评论

学校读者我要写书评

暂无评论

An approximation algorithm for the Generalized k-Multicut problem

引用

DISCRETE APPLIED MATHEMATICS 2012年第7-8期160卷 1240-1247页

作者： Zhang, Peng Zhu, Daming Luan, Junfeng Shandong Univ Sch Comp Sci & Technol Jinan 250101 Peoples R China

Given a graph G = (V, E) with nonnegative costs defined on edges, a positive integer k, and a collection of q terminal sets D = {S-1, S-2, . . . , S-q}, where each S-i is a subset of V(G), the Generalized k-Multicut problem asks to find a set of edges C subset of E(G) at the minimum cost such that its removal from G cuts at least k terminal sets in D. A terminal subset S-i is cut by C if all terminals in S-i are disconnected from one another by removing C from G. This problem is a generalization of the k-Multicut problem and the Multiway Cut problem. The famous Densest k-Subgraph problem can be reduced to the Generalized k-Multicut problem in trees via an approximation preserving reduction. In this paper, we first give an O(root q)-approximation algorithm for the Generalized k-Multicut problem when the input graph is a tree. The algorithm is based on a mixed strategy of LP-rounding and greedy approach. Moreover, the algorithm is applicable to deal with a class of NP-hard partial optimization problems. As its extensions, we then show that the algorithm can be used to give O(root q log n)-approximation for the Generalized k-Multicut problem in undirected graphs and O(root q)-approximation for the k-Forest problem. (C) 2012 Elsevier B.V. All rights reserved.

关键词： k-Multicut k-Forest LP-rounding approximation algorithm Combinatorial optimization

来源：评论

学校读者我要写书评

暂无评论

Optimizing Peer Learning in Online Groups with Affinities 19

Optimizing Peer Learning in Online Groups with Affinities

引用

25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD)

作者： Esfandiari, Mohammadreza Wei, Dong Amer-Yahia, Sihem Roy, Senjuti Basu New Jersey Inst Technol Newark NJ 07102 USA Univ Grenoble Alpes CNRS Grenoble France

ISBN: (纸本)9781450362016

We investigate online group formation where members seek to increase their learning potential via collaboration. We capture two common learning models: LPA where each member learns from all higher skilled ones, and LPD where the least skilled member learns from the most skilled one. We formulate the problem of forming groups with the purpose of optimizing peer learning under different affinity structures: AFFD where group affinity is the smallest between all members, and AFFC where group affinity is the smallest between a designated member (e.g., the least skilled or the most skilled) and all others. This gives rise to multiple variants of a multi-objective optimization problem. We propose principled modeling of these problems and investigate theoretical and algorithmic challenges. We first present hardness results, and then develop computationally efficient algorithms with constant approximation factors. Our real-data experiments demonstrate with statistical significance that forming groups considering affinity improves learning. Our extensive synthetic experiments demonstrate the qualitative and scalability aspects of our solutions.

关键词： multi-objective optimization online network approximation algorithm peer learning

来源：评论

学校读者我要写书评

暂无评论

Approximating Minimum Dominating Set on String Graphs 1

引用

45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)

作者： Chakraborty, Dibyayan Das, Sandip Mukherjee, Joydeep Indian Stat Inst Kolkata India

ISBN: (数字)9783030307868

ISBN: (纸本)9783030307868;9783030307851

A string graph is an intersection graph of simple curves on the plane. For k >= 0, B-k-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends). It is well-known that any string graph is a B-k-VPG graph for some value of k. For k >= 0, unit B-k-VPG graphs are intersection graphs of simple rectilinear curves having at most k cusps (bends) and each segment of the curve being unit length. Any string graph is a unit-B-k-VPG graph for some value of k. In this article, we show that the Minimum Dominating Set (MDS) problem for unit B-k-VPG graphs is NP-Hard for all k >= 1 and provide an O(k(4))-approximation algorithm for all k >= 0. Furthermore, we also provide an 8-approximation for the MDS problem for the vertically-stabbed L-graphs, intersection graphs of L-paths intersecting a common vertical line. The same problem is known to be APX-Hard (MFCS, 2018). As a by-product of our proof, we obtained a 2-approximation algorithm for the stabbing segment with rays (SSR) problem introduced and studied by Katz et al. (Comput. Geom. 2005).

关键词： String graph Dominating set approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：