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

International Symposium on Soft Computing and Intelligent Systems (SCIS)

作者： Yuichi Asahiro Tomohiro Kubo Eiji Miyano Department of Information Science Kyushu Sangyo University Fukuoka Japan Department of Systems Design and Informatics Kyushu Institute of Technology Fukuoka Japan

ISBN: (纸本)9781509026791

In this paper we consider two distance-based relaxed variants of the maximum clique problem (MAX CLIQUE), named MAX d-CLIQUE and MAX d-CLUB: A d-clique in a graph G is a subset S ⊆ V(G) of vertices such that for pairs of vertices u, v ε S, the distance between u and v is at most d in G. A d-club in a graph G is a subset S' ⊆ V(G) of vertices that induces a subgraph of G of diameter at most d. MAX d-CLIQUE and MAX d-CLUB ask to find a maximum d-clique and a maximum d-club in a given unweighted graph, respectively. MAX 1-CLIQUE and MAX 1-CLUB cannot be efficiently approximated within a factor of n1-ε for any ε > 0 unless P = NP since they are identical to MAX CLIQUE [1], [2]. Also, it is known [3], [4] that it is NP-hard to approximate MAX d-CLIQUE and MAX d-CLUB to within a factor of n1/2-ε for any fixed d ≥ 2 and any ε > 0. As for approximability of MAX d-CLIQUE and MAX d-CLUB, [3] proposes a polynomial-time algorithm, called ByFindStard, and proves that its approximation ratio is O(n1/2) and O(n2/3) for any even d ≥ 2 and for any odd d ≥ 3, respectively. Very recently, a polynomial-time algorithm, called ByFindStar2d, achieving an optimal approximation ratio of O(n1/2) for MAX d-CLIQUE and MAX d-CLUB is designed for any odd d ≥ 3 in [4]. In this paper we implement those approximation algorithms and evaluate their quality empirically for random graphs Gn,p, which have n vertices and each edge appears with probability p. The experimental results show that (i) ByFindStar2d of approximation ratio O(n1/2) can find larger d-clubs (d-cliques) than ByFindStard of approximation ratio O(n2/3) for odd d, (ii) the size of d-clubs (d-cliques) output by ByFindStard is the same as ones by ByFindStar2d for even d, and (iii) ByFindStard can find the same size of d-clubs (d-cliques) much faster than ByFindStar2d.

关键词： approximation algorithms Algorithm design and analysis Intelligent systems Social network services Graph theory Image edge detection Computational modeling

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for k-Submodular Function Maximization 16

Improved Approximation Algorithms for k-Submodular Function ...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Satoru Iwata Shinichi Tanigawa Yuichi Yoshida Department of Mathematical Informatics University of Tokyo Research Institute for Mathematical Sciences Kyoto University and Centrum Wiskunde & Informatica National Institute of Informatics and Preferred Infrastructure Inc.

ISBN: (纸本)9781510819672

This paper presents a polynomial-time 1/2-approximation algorithm for maximizing nonnegative k-submodular functions. This improves upon the previous max{1/3, 1/(1 + a)}-approximation by Ward and Zivny [18], where a = max{1, {the square root of}((k - 1)/4)}. We also show that for monotone k-submodular functions there is a polynomial-time k/(2k - 1)-approximation algorithm while for any ε > 0 a ((k + 1)/2k + ε)-approximation algorithm for maximizing monotone k-submodular functions would require exponentially many queries. In particular, our hardness result implies that our algorithms are asymptotically tight. We also extend the approach to provide constant factor approximation algorithms for maximizing skewbisubmodular functions, which were recently introduced as generalizations of bisubmodular functions.

关键词： approximation algorithms algorithms Patients' Rooms Monotone Generalization

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for constrained fault-tolerant resource allocation

引用

THEORETICAL COMPUTER SCIENCE 2015年 590卷 118-128页

作者： Liao, Kewen Shen, Hong Guo, Longkun Univ Adelaide Sch Comp Sci Adelaide SA Australia Sun Yat Sen Univ Sch Comp & Informat Technol Guangzhou 510275 Guangdong Peoples R China Fuzhou Univ Sch Math & Comp Sci Fuzhou 350002 Peoples R China

In Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most R-i facilities with opening cost f(i). Each client j requires an allocation of r(j) open facilities and connecting j to any facility at site i incurs a connection cost c(ij). The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation (FTRA(infinity)) [1] and the classical Fault-Tolerant Facility Location (FTFL) [2] problems: for every site i, FTRA(infinity) does not have the constraint R-i, whereas FTFL sets R-i = 1. These problems are said to be uniform if all r(j)'s are the same, and general otherwise. For the general metric FTRA, we first give an LP-rounding algorithm achieving an approximation ratio of 4. Then we show the problem reduces to FTFL, implying the ratio of 1.7245 from [3]. For the uniform FTRA, we provide a 1.52-approximation primal-dual algorithm in O (n(4)) time, where n is the total number of sites and clients. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Resource allocation approximation algorithms LP-rounding Reduction Primal-dual Time complexity

来源：评论

学校读者我要写书评

暂无评论

Improved approximation algorithms for two variants of the stable marriage problem with ties

引用

MATHEMATICAL PROGRAMMING 2015年第1-2期154卷 353-380页

作者： Huang, Chien-Chung Kavitha, Telikepalli Chalmers Univ Technol S-41296 Gothenburg Sweden Tata Inst Fundamental Res Bombay 400005 Maharashtra India

We consider the problem of computing a large stable matching in a bipartite graph where each vertex ranks its neighbors in an order of preference, perhaps involving ties. Let the matched partner of u in a matching M be M(u). A matching M is said to be stable if there is no edge (a, b) such that a is unmatched or prefers b to M(a) and similarly, b is unmatched or prefers a to M(b). While a stable matching in G can be easily computed in linear time by the Gale-Shapley algorithm, it is known that computing a maximum size stable matching is APX-hard. In this paper we first consider the case when the preference lists of vertices in A are strict while the preference lists of vertices in B may include ties. This case is also APX-hard and the current best approximation ratio known here is 25/17 which relies on solving an LP. We improve this ratio to 22/15 by a simple linear time algorithm. Here we first compute a half-integral stable matching in and then round it to an integral stable matching M. The ratio is bounded via a payment scheme that charges other components in to cover the costs of length-5 augmenting paths. There will be no length-3 augmenting paths here. We next consider the following special case of two-sided ties, where every tie length is 2. This case is known to be UGC-hard to approximate to within 4/3. We show a 10/7 approximation algorithm here that runs in linear time.

关键词： Stable matching approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Running Errands in Time: approximation algorithms for Stochastic Orienteering

引用

MATHEMATICS OF OPERATIONS RESEARCH 2015年第1期40卷 56-79页

作者： Gupta, Anupam Krishnaswamy, Ravishankar Nagarajan, Viswanath Ravi, R. Carnegie Mellon Univ Dept Comp Sci Pittsburgh PA 15213 USA Princeton Univ Dept Comp Sci Princeton NJ 08540 USA IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Carnegie Mellon Univ Tepper Sch Business Pittsburgh PA 15213 USA

In the stochastic orienteering problem, we are given a finite metric space, where each node contains a job with some deterministic reward and a random processing time. The processing time distributions are known and independent across nodes. However the actual processing time of a job is not known until it is completely processed. The objective is to compute a nonanticipatory policy to visit nodes (and run the corresponding jobs) so as to maximize the total expected reward, subject to the total distance traveled plus the total processing time being at most a given budget of B. This problem combines aspects of the stochastic knapsack problem with uncertain item sizes as well as the deterministic orienteering problem. In this paper, we consider both nonadaptive and adaptive policies for Stochastic Orienteering. We present a constant-factor approximation algorithm for the nonadaptive version and an O(log log B)-approximation algorithm for the adaptive version. We extend both these results to directed metrics and a more general sequence orienteering problem. Finally, we address the stochastic orienteering problem when the node rewards are also random and possibly correlated with the processing time and obtain an O(log n log B)-approximation algorithm;here n is the number of nodes in the metric. All our results for adaptive policies also bound the corresponding "adaptivity gaps".

关键词： approximation algorithms adaptivity gap orienteering problem stochastic optimization

来源：评论

学校读者我要写书评

暂无评论

Capacitated Domination: Problem Complexity and approximation algorithms

引用

ALGORITHMICA 2015年第1期72卷 1-43页

作者： Kao, Mong-Jen Chen, Han-Lin Lee, D. T. Acad Sinica Inst Informat Sci Taipei Taiwan Natl Taiwan Univ Dept Comp Sci & Informat Engn Taipei 10764 Taiwan

We consider a local service-requirement assignment problem named capacitated domination from an algorithmic point of view. In this problem, we are given a graph with three parameters defined on each vertex, which are the cost, the capacity, and the demand, of a vertex, respectively. A vertex can be chosen multiple times in order to generate sufficient capacity for the demands of the vertices in its closed neighborhood. The objective of this problem is to compute a demand assignment of minimum cost such that the demand of each vertex is fully-served by some of its closed neighbors without exceeding the amount of capacity they provide. In this paper, we provide complexity results as well as several approximation algorithms to compose a comprehensive study for this problem. First, we provide logarithmic approximations for general graphs which are asymptotically optimal. From the perspective of parameterized complexity, we show that this problem is W[1]-hard with respect to treewidth and solution size. Moreover, we show that this problem is fixed-parameter tractable with respect to treewidth and the maximum capacity of the vertices. The latter result implies a pseudo-polynomial time approximation scheme for planar graphs under a standard framework. In order to drop the pseudo-polynomial factor, we develop a constant-factor approximation for planar graphs, based on a new perspective which we call general ladders on the hierarchical structure of outer-planar graphs. We believe that the approach we use can be applicable to other capacitated covering problems.

关键词： Capacitated domination approximation algorithms Dominating set Graph theory

来源：评论

学校读者我要写书评

暂无评论

Tractable approximation algorithms for the NP-hard problem of growing linear consensus networks

Tractable approximation algorithms for the NP-hard problem o...

引用

American Control Conference

作者： Milad Siami Nader Motee Department of Mechanical Engineering and Mechanics Packard Laboratory Lehigh University Bethlehem PA USA

ISBN: (纸本)9781467386838

In this paper, we investigate a network synthesis problem that aims to improve the performance of noisy linear consensus networks by establishing a few new interconnection links throughout the network. This network synthesis problem can be equivalently formulated as an optimization problem over a set of candidate graphs, which is inherently combinatorial and NP-hard. We propose an exact solution for this problem when only one new link needs to be established. In this case, a closed form expression is calculated for the optimal value of the systemic performance measure of the augmented network. When it is required to establish more than one interconnection link, we propose two tractable approximate methods with computable performance bounds. Moreover, in order to be able to calculate sub-optimality gaps of our proposed approximate algorithms, we quantify the best achievable performance bounds for the network synthesis problem.

关键词： Laplace equations Network synthesis Eigenvalues and eigenfunctions Couplings Noise measurement approximation algorithms Optimization network synthesis approximation algorithms Laplace's equation Noise measurement Eigenfunctions Nondeterministic polynomial-time hard Couplings

来源：评论

学校读者我要写书评

暂无评论

Integrality Gaps and approximation algorithms for Dispersers and Bipartite Expanders 16

Integrality Gaps and Approximation Algorithms for Dispersers...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Xue Chen Department of Computer Science University of Texas at Austin

ISBN: (纸本)9781510819672

We study the problem of approximating the quality of a disperser. A bipartite graph G on ([N], [M]) is a (ρN, (1 - δ)M)-disperser if for any subset S {is contained in} [N] of size ρN, the neighbor set Γ(S) contains at least (1-δ)M distinct vertices. Our main results are strong integrality gaps in the Lasserre hierarchy and an approximation algorithm for dispersers. 1. For any α > 0, δ > 0, and a random bipartite graph G with left degree D = O(logN), we prove that the Lasserre hierarchy cannot distinguish whether G is an (N~α, (1 - δ)M)-disperser or not an (N~(1-α), δM)-disperser. 2. For any ρ > 0, we prove that there exist infinitely many constants d such that the Lasserre hierarchy cannot distinguish whether a random bipartite graph G with right degree d is a (ρN, (1 - (1 - ρ)~d)M)-disperser or not a (ρN, (1 - Ω((1-ρ)/(ρd+1-ρ)))M)-disperser. We also provide an efficient algorithm to find a subset of size exact ρN that has an approximation ratio matching the integrality gap within an extra loss of (min{ρ/(10ρ),(1-ρ)/ρ})/(log d). Our method gives an integrality gap in the Lasserre hierarchy for bipartite expanders with left degree D. G on ([N], [M]) is a (ρN, a)-expander if for any subset S {is contained in} [N] of size ρN, the neighbor set Γ(S) contains at least a · ρN distinct vertices. We prove that for any constant ε > 0, there exist constants ε' < ε, ρ, and D such that the Lasserre hierarchy cannot distinguish whether a bipartite graph on ([N], [M]) with left degree D is a (ρN, (1 - ε')D)-expander or not a (ρN, (1 - ε)D)-expander.

关键词： Bipartite graph approximation algorithms Dispersers Social Hierarchy Expander Device Component DISPERSANT deuterium ABSORBED DOSE nitrogen Subset TWO-COMPONENT

来源：评论

学校读者我要写书评

暂无评论

Delay-Constrained Shortest Paths: approximation algorithms and Second-Order Cone Models

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2015年第3期164卷 1051-1077页

作者： Frangioni, Antonio Galli, Laura Scutella, Maria Grazia Univ Pisa Dipartimento Informat Largo B Pontecorvo 3 I-56127 Pisa Italy

Routing real-time traffic with maximum packet delay in contemporary telecommunication networks requires not only choosing a path but also reserving transmission capacity along its arcs, as the delay is a nonlinear function of both components. The problem is known to be solvable in polynomial time under quite restrictive assumptions, i.e., equal rate allocations (all arcs are reserved the same capacity) and identical reservation costs, whereas the general problem is -hard. We first extend the approaches to the equal rate allocation (ERA) version to a pseudo-polynomial Dynamic Programming one for integer arc costs and a FPTAS for the case of general arc costs. We then show that the general problem can be formulated as a mixed-integer Second-Order Cone (SOCP) program and therefore solved with off-the-shelf technology. We compare two formulations: one based on standard big-M constraints and one where Perspective Reformulation techniques are used to tighten the continuous relaxation. Extensive computational experiments on both real-world networks and randomly generated realistic ones show that the ERA approach is fast and provides an effective heuristic for the general problem whenever it manages to find a solution at all, but it fails for a significant fraction of the instances that the SOCP models can solve. We therefore propose a three-pronged approach that combines the fast running time of the ERA algorithm and the effectiveness of the SOCP models, and show that it is capable of solving realistic-sized instances with high accuracy at different levels of network load in a time compatible with real-time usage in an operating environment.

关键词： Delay-constrained routing approximation algorithms Mixed-integer nonlinear programming Second-order cone model Perspective reformulation

来源：评论

学校读者我要写书评

暂无评论

approximation algorithms for Maximum Link Scheduling under SINR-Based Interference Model

引用

INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS 2015年第7期11卷 1-10页

作者： Zhou, Zi-Ao Li, Chang-Geng Cent S Univ Sch Phys & Elect Changsha 410083 Hunan Peoples R China

A fundamental problem in wireless networks is the maximum link scheduling (MLS) problem. In this problem, interference is a key issue and past researchers have shown that determining reception using Signal-to-Interference plus Noise Ratio (SINR) is more realistic than graph-based interference models. Unfortunately, the MLS problem has been proven to be NP-hard for SINR interference models. To date, several approximation algorithms have been proposed to solve MLS under the SINR-based interference model. However, most of these works do not have either an approximation bound or a distributed version. To this end, we present a novel scheduling method with a constant approximation ratio which is much simpler and only 1/28 of it in past research. The improvement of constant phi also offers a better MLS set. In addition, based on our centralized method, we present a polynomial time, randomized, distributed algorithm, which only requires estimates of the number of links, and maximum and minimum link lengths. We prove its correctness and show that it can compute a MLS with time complexity of O(log(2) n), where n is an estimate of the number of links.

关键词： approximation algorithms COMPUTER scheduling SIGNAL-to-noise ratio PROBLEM solving NP-hard problems DISTRIBUTED algorithms POLYNOMIAL time algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：