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

proceedings of the 28th Annual acm symposium on applied computing

作者： Umesh Bellur Rajiv Ramnath S. D. Madhu Kumar Indian Institute of Technology Bombay India Ohio State University National Institute of Technology Calicut India

No abstract available.

ISBN: (纸本)9781450316569

No abstract available.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Segmentation of Trajectories on Non-Monotone Criteria 13

Segmentation of Trajectories on Non-Monotone Criteria

引用

Annual acm-Society for Industrial and applied Mathmatics symposium on Discrete Algorithms

作者： Boris Aronov Anne Driemel Marc van Kreveld Maarten Loeffler Frank Staalsy Dept. of Computer Science and Engineering Polytechnic Institute of NYU Dept. of Information and Computing Sciences Utrecht University

ISBN: (纸本)9781611972511

In the trajectory segmentation problem we are given a polygonal trajectory with n vertices that we have to subdivide into a minimum number of disjoint segments (subtrajectories) that all satisfy a given criterion. The problem is known to be solvable efficiently for monotone criteria: criteria with the property that if they hold on a certain segment, they also hold on every subsegment of that segment. To the best of our knowledge, no theoretical results are known for non-monotone criteria.

关键词：

来源：评论

学校读者我要写书评

暂无评论

Efficient Algorithms for computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree 13

Efficient Algorithms for Computing the Triplet and Quartet D...

引用

Annual acm-Society for Industrial and applied Mathmatics symposium on Discrete Algorithms

作者： Gerth Stolting Brodal Rolf Fagerberg Thomas Mailund Christian N. S. Pedersen Andreas Sand Department of Computer Science Aarhus University Department of Mathematics and Computer Science University of Southern Denmark Bioinformatics Research Center Aarhus University

ISBN: (纸本)9781611972511

The triplet and quartet distances are distance measures to compare two rooted and two unrooted trees, respectively. The leaves of the two trees should have the same set of n labels. The distances are defined by enumerating all subsets of three labels (triplets) and four labels (quartets), respectively, and counting how often the induced topologies in the two input trees are different. In this paper we present efficient algorithms for computing these distances. We show how to compute the triplet distance in time O(n log n) and the quartet distance in time O(dn log n), where d is the maximal degree of any node in the two trees. Within the same time bounds, our framework also allows us to compute the parameterized triplet and quartet distances, where a parameter is introduced to weight resolved (binary) topologies against unresolved (non-binary) topologies. The previous best algorithm for computing the triplet and parameterized triplet distances have O(n~2) running time, while the previous best algorithms for computing the quartet distance include an O(d~9n log n) time algorithm and an O(n~(2.688)) time algorithm, where the latter can also compute the parameterized quartet distance. Since d ≤ n, our algorithms improve on all these algorithms.

关键词：

来源：评论

学校读者我要写书评

暂无评论

The Power of Non-Uniform Wireless Power 13

The Power of Non-Uniform Wireless Power

引用

Annual acm-Society for Industrial and applied Mathmatics symposium on Discrete Algorithms

作者： Magnus M. Halldorsson Stephan Holzer Pradipta Mitra Roger Wattenhofer ICE-TCS School of Computer Science Reykjavik University Distributed Computing Group

ISBN: (纸本)9781611972511

We study a fundamental measure for wireless interference in the SINR model known as (weighted) inductive independence. This measure characterizes the electiveness of using oblivious power - when the power used by a transmitter only depends on the distance to the receiver - as a mechanism for improving wireless capacity. We prove optimal bounds for inductive independence, implying a number of algorithmic applications. An algorithm is provided that achieves - due to existing lower bounds - capacity that is asymptotically best possible using oblivious power assignments. Improved approximation algorithms are provided for a number of problems for oblivious power and for power control, including distributed scheduling, connectivity, secondary spectrum auctions, and dynamic packet scheduling.

关键词： Wireless Power power assignments packet scheduling power Power Energy sources Power (Psychology) Power packet schedule wireless Approximation algorithms Power control secondary spectrum

来源：评论

学校读者我要写书评

暂无评论

Using the crowd to understand and adapt user interfaces 13

Using the crowd to understand and adapt user interfaces

引用

proceedings of the 5th acm SIGCHI symposium on Engineering interactive computing systems

作者： Jeffrey Nichols IBM Research - Almaden San Jose CA USA

ISBN: (纸本)9781450321389

Engineering user interfaces has long implied careful design carried out using formal methods applied by human experts and automated systems. While these methods have advantages, especially for creating interfaces that have the flexibility to adapt to users and situations, they can also be time consuming, expensive, and there are relatively few experts able to apply them effectively. In particular, many engineering methods require the construction of one or more models, each of which can only be created through many hours of work by an expert. In this keynote, I will explore how social and human computation methods can be applied to reduce the barriers to achieving user interface flexibility and ultimately to using engineering methods. In a first example, I will illustrate how groups of users can work together to modify and improve user interfaces through end-user programming examples from the CoScripter and Highlight projects. I will then discuss some initial work on using a crowd of novice workers to create models of existing user interfaces. I hope this keynote will inspire the engineering community to consider alternate approaches that creatively combine formal methods with the power of crowds.

关键词： highlight model-based user interfaces coscripter social media qcrowd human computation end-user programming crowd computing

来源：评论

学校读者我要写书评

暂无评论

Finding Endogenously Formed Communities 13

Finding Endogenously Formed Communities

引用

Annual acm-Society for Industrial and applied Mathmatics symposium on Discrete Algorithms

作者： Maria-Florina Balcan Christian Borgs Mark Braverman Jennifer Chayes Shang-Hua Teng School of Computer Science College of Computing Georgia Institute of Technology Microsoft Research Princeton University Microsoft Research Computer Science Department University of Southern California

ISBN: (纸本)9781611972511

A central problem in data mining and social network analysis is determining overlapping communities (clusters) among individuals or objects in the absence of external identification or tagging. We address this problem by introducing a framework that captures the notion of communities or clusters determined by the relative affinities among their members. To this end we define what we call an affinity system, which is a set of elements, each with a vector characterizing its preference for all other elements in the set. We define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are endogenously formed in the affinity system and are "self-determined" or "self-certified" by its members.

关键词： data mining elements ize of the network data mining Social Networks Elements Social Interaction Communities affinity Affine transformation Social Capital Kinship

来源：评论

学校读者我要写书评

暂无评论

Nonlinear discrete-time algorithm for fractional derivatives computation with application to PIλDμ controller implementation

Nonlinear discrete-time algorithm for fractional derivatives...

引用

6th Workshop on Fractional Differentiation and Its Applications, FDA 2013

作者： Pisano, Alessandro Nessi, Davide Usai, Elio Rapaic, Milan R. Univ. of Cagliari Cagliari Italy Faculty of Technical Sciences Computing and Control Dept. University of Novi Sad Novi Sad Serbia

ISBN: (纸本)9783902823274

This paper presents a novel algorithm for the numerical computation of fractional-order derivatives, based on a suitable generalization of a sliding-mode based robust and exact first-order differentiator (see Levant (1998)). The method inherits the robustness properties against the measurement noise of the original scheme. The algorithm is first devised in the continuous time setting, leading to a block scheme where conventional and fractional order integrators are suitably combined in a closed loop configuration containing certain "stabilizing" static non-linearities as well. All integrators are discretized by an algorithm of the Adams-Bashforth-Moulton type (cfr. Diethelm et al, (2004)) yielding an overall discrete time form of the proposed fractional differentiator. The algorithm is then applied to derive a discretized implementation formula for the PIλDμ controller. Simulation and experimental tests are carried out to verify the performance of the proposed algorithm and to compare it with other existing approaches. © 2013 IFAC.

关键词： Sliding mode control

来源：评论

学校读者我要写书评

暂无评论

Online Mixed Packing and Covering 13

Online Mixed Packing and Covering

引用

Annual acm-Society for Industrial and applied Mathmatics symposium on Discrete Algorithms

作者： Yossi Azar Umang Bhaskar Lisa Fleischer Debmalya Panigrahi Blavatnik School of Computer Science Tel-Aviv University Department of Computing and Mathematical Sciences California Institute of Technology Microsoft Research

ISBN: (纸本)9781611972511

Recent work has shown that the classical framework of solving optimization problems by obtaining a fractional solution to a linear program (LP) and rounding it to an integer solution can be extended to the online setting using primal-dual techniques. The success of this new framework for online optimization can be gauged from the fact that it has led to progress in several longstanding open questions. However, to the best of our knowledge, this framework has previously been applied to LPs containing only packing or only covering constraints, or minor variants of these. We extend this framework in a fundamental way by demonstrating that it can be used to solve mixed packing and covering LPs online, where packing constraints are given of-fine and covering constraints are received online. The objective is to minimize the maximum multiplicative factor by which any packing constraint is violated, while satisfying the covering constraints. Our results represent the first algorithm that obtains a polylogarithmic competitive ratio for solving mixed LPs online. We then consider two canonical examples of mixed LPs: unrelated machine scheduling with startup costs, and capacity constrained facility location. We use ideas generated from our result for mixed packing and covering to obtain polylogarithmic-competitive algorithms for these problems. We also give lower bounds to show that the competitive ratios of our algorithms are nearly tight.

关键词： Online Mixed Packing objective is first algorithm

来源：评论

学校读者我要写书评

暂无评论

An Almost Optimal Algorithm for computing Nonnegative Rank 13

An Almost Optimal Algorithm for Computing Nonnegative Rank

引用

Annual acm-Society for Industrial and applied Mathmatics symposium on Discrete Algorithms

作者： Ankur Moitra Institute for Advanced Study

ISBN: (纸本)9781611972511

Here, we give an algorithm for deciding if the nonnegative rank of a matrix M of dimension m × n is at most r which runs in time (nm)~(O(r~2)). This is the first exact algorithm that runs in time singly-exponential in r. This algorithm (and earlier algorithms) are built on methods for finding a solution to a system of polynomial inequalities (if one exists). Notably, the best algorithms for this task run in time exponential in the number of variables but polynomial in all of the other parameters (the number of inequalities and the maximum degree). Hence these algorithms motivate natural algebraic questions whose solution have immediate algorithmic implications: How many variables do we need to represent the decision problem, does M have nonnegative rank at most r? A naive formulation uses nr + mr variables and yields an algorithm that is exponential in n and m even for constant r. (Arora, Ge, Kannan, Moitra, STOC 2012) recently reduced the number of variables to 2r~2 2~r, and here we exponentially reduce the number of variables to 2r~2 and this yields our main algorithm. In fact, the algorithm that we obtain is nearly-optimal (under the Exponential Time Hypothesis) since an algorithm that runs in time (nm)~(o(r)) would yield a subexponential algorithm for 3-SAT. Our main result is based on establishing a normal form for nonnegative matrix factorization - which in turn allows us to exploit algebraic dependence among a large collection of linear transformations with variable entries. Additionally, we also demonstrate that nonnegative rank cannot be certified by even a very large submatrix of M, and this property also follows from the intuition gained from viewing nonnegative rank through the lens of systems of polynomial inequalities.

关键词： Almost Optimal Algorithm computing Nonnegative algorithms Nonnegative Decision problem matrix decomposition Rank of data inequalities Polynomial linear transformations Optimization algorithms

来源：评论

学校读者我要写书评

暂无评论

Nonlinear Discrete-Time Algorithm for Fractional Derivatives Computation with Application to PI λ D μ Controller Implementation

引用

IFAC proceedings Volumes 2013年第1期46卷 887-892页

作者： Alessandro Pisano Davide Nessi Elio Usai Milan R. Rapaic Dept. of Electrical and Electronic Engineering (DIEE) Univ. of Cagliari Cagliari Italy Faculty of Technical Sciences Computing and Control Dept. University of Novi Sad Novi Sad Serbia

This paper presents a novel algorithm for the numerical computation of fractional-order derivatives, based on a suitable generalization of a sliding-mode based robust and exact first-order differentiator (see Levant (1998)). The method inherits the robustness properties against the measurement noise of the original scheme. The algorithm is first devised in the continuous time setting, leading to a block scheme where conventional and fractional order integrators are suitably combined in a closed loop configuration containing certain “stabilizing” static non-linearities as well. All integrators are discretized by an algorithm of the Adams-Bashforth-Moulton type (cfr. Diethelm et al, (2004)) yielding an overall discrete time form of the proposed fractional differentiator. The algorithm is then applied to derive a discretized implementation formula for the PI λ D μ controller. Simulation and experimental tests are carried out to verify the performance of the proposed algorithm and to compare it with other existing approaches.

关键词： Fractional derivative estimation Sliding mode control Discretized fractional controllers

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：