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

IEEE INFOCOM Conference

作者： Wan, Peng-Jun Ma, Chao Wang, Zhu Xu, Boliu Li, Minming Jia, Xiaohua IIT Dept Comp Sci Chicago IL 60616 USA City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781424499212

Link scheduling is a fundamental design issue in multihop wireless networks. All existing link scheduling algorithms require the precise information of the positions, and/or communication/interference radii of all nodes. For practical networks, it is not only difficult or expensive to obtain these parameters, but also often impossible to get their precise values. The link scheduling determined by the imprecise values of these parameters may fail to guarantee the same approximation bounds of the link scheduling determined by precise values. Therefore, the existing link scheduling algorithms lack performance robustness. In this paper, we propose a robust link scheduling, which can be easily computed with only the information on whether a given pair of links have conflict or not and therefore is robust. In addition, our link scheduling does not compromise the approximation bound and indeed sometimes can achieve better approximation bound. Particularly, under the 802.11 interference model, its approximation bound is 16 in general and 6 with uniform interference radii, an improvement over the respective best-known approximation bounds 23 and 7.

关键词： Link scheduling interference robustness latency approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Covering Cubes and the Closest Vector Problem 11

Covering Cubes and the Closest Vector Problem

引用

27th Annual ACM Symposium on Computational Geometry

作者： Eisenbrand, Friedrich Haehnle, Nicolai Niemeier, Martin Ecole Polytech Fed Lausanne Stn 8 CH-1015 Lausanne Switzerland

ISBN: (纸本)9781450306829

We provide the currently fastest randomized (1+epsilon)-approximation algorithm for the closest lattice vector problem in the l(infinity)-norm. The running time of our method depends on the dimension n and the approximation guarantee epsilon by 2(O(n))(log 1/epsilon)(O(n)) which improves upon the (2 + 1/epsilon)(O(n)) running time of the previously best algorithm by Blomer and Naewe. Our algorithm is based on a solution of the following geometric covering problem that is of interest of its own: Given epsilon is an element of (0, 1), how many ellipsoids are necessary to cover the cube [-1 + epsilon, 1 - epsilon](n) such that all ellipsoids are contained in the standard unit cube [-1, 1](n)? We provide an almost optirnal bound for the case where the ellipsoids are restricted to be axis-parallel. We then apply our covering scheme to a variation of this covering problem where one wants to cover [-1 + epsilon, 1 - epsilon](n) with parallelepipeds that, if scaled by two, are still contained in the unit cube. Thereby, we obtain a method to boost any 2-approximation algorithm for closest-vector in the l(infinity)-norm to a (1 + epsilon)-approximation algorithm that has the desired running time.

关键词： closest lattice vector problem approximation algorithm ellipsoid cover box cover covering convex bodies

来源：评论

学校读者我要写书评

暂无评论

Convex recoloring of paths

引用

Electronic Notes in Discrete Mathematics 2011年第C期37卷 165-170页

作者： Lima, Karla Roberta Wakabayashi, Yoshiko Instituto de Matemática e Estatística Universidade de São Paulo Brazil

Let (T,C) be a pair consisting of a tree T and a coloring C of its vertices. We say that C is a convex coloring if, for each color, the vertices in T with the same color induces a subtree of T. The convex recoloring problem (of trees) is defined as follows. Given a pair (T,C), find a recoloring of a minimum number of vertices of T such that the resulting coloring is convex. This problem is known to be NP-hard. It was motivated by problems on phylogenetic trees. We investigate here the convex recoloring problem on paths, denoted here CRP. We present an integer programming formulation for CRP and show some computational results obtained by exploring this formulation. We also present some preliminary results of a heuristic that is based on this formulation. Furthermore, we investigate a special case of CRP, denoted here 2-CRP, restricted to paths in which the number of vertices of each color is at most 2, a problem known to be NP-hard. The best approximation result for CRP was obtained by Moran and Snir, who showed a 2-approximation algorithm. We show in this paper a 3/2-approximation algorithm for 2-CRP. © 2011 Elsevier B.V.

关键词： approximation algorithm Convex coloring Integer linear formulation

来源：评论

学校读者我要写书评

暂无评论

Wireless Link Scheduling under Physical Interference Model

Wireless Link Scheduling under Physical Interference Model

引用

IEEE INFOCOM Conference

作者： Wan, Peng-Jun Frieder, Ophir Jia, Xiaohua Yao, Frances Xu, Xiaohua Tang, Shaojie IIT Dept Comp Sci Chicago IL 60616 USA Georgetown Univ Dept Comp Sci Washington DC USA City Univ Hong Kong Dept Comp Sci Kowloon Peoples R China

ISBN: (纸本)9781424499212

Link scheduling is a fundamental problem in multihop wireless networks because the capacities of the communication links in multihop wireless networks, rather than being fixed, vary with the underlying link schedule subject to the wireless interference constraint. The majority of algorithmic works on link scheduling in multihop wireless networks assume binary interference models such as the 802.11 interference model and the protocol interference model, which often put severe restrictions on interference constraints for practical applicability of the link schedules. On the other hand, while the physical interference model is much more realistic, the link scheduling problem under physical interference model is notoriously hard to resolve and been studied only recently by a few works. This paper conducts a full-scale algorithmic study of link scheduling for maximizing throughput capacity or minimizing the communication latency in multihop wireless networks under the physical interference model. We build a unified algorithmic framework and develop approximation algorithms for link scheduling with or without power control.

关键词： Link scheduling physical interference model maximum (concurrent) multiflow approximation algorithm maximum independent set

来源：评论

学校读者我要写书评

暂无评论

Outlier Detection on Uncertain Data: Objects, Instances, and Inferences

Outlier Detection on Uncertain Data: Objects, Instances, and...

引用

IEEE 27th International Conference on Data Engineering (ICDE 2011)

作者： Jiang, Bin Pei, Jian Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

ISBN: (纸本)9781424489589

This paper studies the problem of outlier detection on uncertain data. We start with a comprehensive model considering both uncertain objects and their instances. An uncertain object has some inherent attributes and consists of a set of instances which are modeled by a probability density distribution. We detect outliers at both the instance level and the object level. To detect outlier instances, it is a prerequisite to know normal instances. By assuming that uncertain objects with similar properties tend to have similar instances, we learn the normal instances for each uncertain object using the instances of objects with similar properties. Consequently, outlier instances can be detected by comparing against normal ones. Furthermore, we can detect outlier objects most of whose instances are outliers. Technically, we use a Bayesian inference algorithm to solve the problem, and develop an approximation algorithm and a filtering algorithm to speed up the computation. An extensive empirical study on both real data and synthetic data verifies the effectiveness and efficiency of our algorithms.

关键词： approximation algorithms approximation methods Bayes methods Bayesian inference algorithm Equations Inference algorithms Kernel Mathematical model Temperature measurement approximation algorithm data handling filtering algorithm inference mechanisms instance level object level outlier detection probability density distribution statistical distributions uncertain data uncertain objects

来源：评论

学校读者我要写书评

暂无评论

Visibility Testing and Counting

Visibility Testing and Counting

引用

Joint 5th International Frontiers in algorithmics Workshop (FAW) / 7th International Conference on algorithmic Aspects in Information and Management (AAIM)

作者： Alipour, Sharareh Zarei, Alireza Sharif Univ Technol Dept Math Sci Tehran Iran

ISBN: (纸本)9783642212048

For a set of n disjoint line segments S in R-2, the visibility counting problem (VCP) is to preprocess S such that the number of visible segments in S from a query point p can be computed quickly. For this configuration, the visibility testing problem (VTP) is to test whether p sees a fixed segment s. These problems can be solved in logarithmic query time by using O(n(4)) preprocessing time and space. In this paper, we approximately solve this problem using quadratic preprocessing time and space. Our methods are superior to current approximation algorithms in terms of both approximation factor and preprocessing cost. In this paper, we propose a 2-approximation algorithm for the VCP using at most quadratic preprocessing time and space. The query time of this method is O-epsilon(n(2)/root k) where k is the preprocessing time and O-epsilon(f(n)) = O(f(n)n(epsilon)). We also solve the VTP in expected logarithmic query time using quadratic time and space.

关键词： Computational geometry visibility approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

A Theoretical Probabilistic Simulation Framework for Dynamic Power Estimation

A Theoretical Probabilistic Simulation Framework for Dynamic...

引用

IEEE/ACM International Conference on Computer-Aided Design (ICCAD)

作者： Wang, L. Olbrich, M. Barke, E. Buechner, T. Buehler, M. Panitz, P. Leibniz Univ Hannover Inst Microelect Syst Hannover Germany IBM Deutschland Res & Dev Boblingen Germany

ISBN: (纸本)9781457713989

As fast non-simulation-based power estimation techniques, probabilistic simulation techniques were widely researched in the 1990s. Spatial and temporal correlations are commonly known as two fundamental challenges of these kinds of techniques. Previous work showed that spatial correlation could be coped with by means of bit-parallel simulation. For temporal correlation that has great impact on estimating glitches, previous work only showed that it could be considered by means of a glitch-filtering scheme which is an approximation algorithm, but did not answer the question whether temporal correlation could be overcome without any approximation. Our work extends conventional probabilistic simulation techniques and puts the essentials and extensions of probabilistic simulation into a theoretical framework. Based on the framework, this paper shows that modeling temporal correlation in probabilistic simulation without any approximation is only possible in theory. Therefore, an improved approximation of the exact method is proposed. Compared to the conventional probabilistic simulation, our prominently improved results prove the effectiveness of our approximation algorithm. At the end of this paper, the advantages and the bottlenecks of probabilistic simulation are concluded in general.

关键词： Correlation Delay Estimation Integrated circuit modeling Logic gates Monte Carlo methods Monte Carlo simulation Probabilistic logic Switches approximation algorithm approximation theory bit-parallel simulation combinational circuits dynamic power estimati

来源：评论

学校读者我要写书评

暂无评论

Toward Combinatorial Auction-based Better Electric Power Allocation on Sustainable Electric Power Systems

Toward Combinatorial Auction-based Better Electric Power All...

引用

13th IEEE International Conference on Commerce and Enterprise Computing (CEC)

作者： Fukuta, Naoki Ito, Takayuki Shizuoka Univ Fac Informat 3 5 1 Johoku Hamamatsu Shizuoka Japan Nagoya Inst Technol Sch Technobusiness Adm Showa Ku Nagoya Aichi Japan

ISBN: (纸本)9780769545356

Multi-unit combinatorial auction is a combinatorial auction that has some items that can bee seen as indistinguishable. Some approximation mechanisms have been proposed to be applied for a large-scale auction problem regardless of its computational intractability. Although theoretically such mechanisms could be applied for dynamic electricity auctions, there is little empirical analysis about how such a fast approximation mechanism can be applied to the actual electric power allocation problem when we consider the situation that there are sustainable electric power sources and the consumers have preferences for them. In this paper, we present a preliminary analysis about applying a fast approximation mechanism for multi-unit combinatorial auctions to an electric power allocation problem when it includes sustainable power sources. Also in this paper we discuss how such a mechanism can be implemented in a practical way.

关键词： auctions mechanism design approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Fault-tolerant routing: k-inconnected many-to-one routing in wireless networks

Fault-tolerant routing: <i>k</i>-inconnected many-to-one rou...

引用

3rd International Conference on Combinatorial Optimization and Applications (COCOA 2009)

作者： Li, Deying Wang, Yuexuan Zhu, Qinghua Yang, Huiqiang Renmin Univ China Key Lab Data Engn & Knowledge Engn MOE Beijing Peoples R China Renmin Univ China Sch Informat Beijing Peoples R China Tsinghua Univ Inst Theoret Comp Sci Beijing 100084 Peoples R China

This paper addresses the problem of fault-tolerant many-to-one routing in static wireless networks with asymmetric links, which is important in both theoretical and practical aspects. The problem is to find a minimum energy subgraph for a given subset and a destination node such that there are k node-disjoint paths from each node in the subset to the destination node in the subgraph. Firstly, we prove that the problem is NP-hard, and then propose two approximation algorithms: the minimum weight k node-disjoint paths based (MWkNDPB) algorithm and the minimum energy k node-disjoint paths based (MEkNDPB) algorithm. Extensive simulations have been conducted to show that proposed algorithms are efficient. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Wireless networks Fault-tolerant k-inconnected many-to-one routing approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

On the Maximum Locally Clustered Subgraph and Some Related Problems

On the Maximum Locally Clustered Subgraph and Some Related P...

引用

5th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2011)

作者： Wu, Bang Ye Natl Chung Cheng Univ Chiayi 621 Taiwan

ISBN: (纸本)9783642226151

Motivated by detecting false friend links in online social networks, we define two optimization problems based on the balance theory for structural transitivity in social networks. We give a polynomial time algorithm for one problem and show the NP-hardness of the other. For the NP-hard problem, we show some polynomial time solvable cases and give a 2-approximation algorithm for a restricted version. We also propose a heuristic algorithm for a more general version of the problem.

关键词： algorithm social network analysis time complexity NP-hard approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：