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

Randomized algorithms for Lexicographic Inference

OPERATIONS RESEARCH 2019年第2期67卷 357-375页

作者： Kohli, Rajeev Boughanmi, Khaled Kohli, Vikram Columbia Univ Grad Sch Business New York NY 10027 USA Northwestern Univ McCormick Sch Engn Dept Elect Engn & Comp Sci Evanston IL 60208 USA

The inference of a lexicographic rule from paired comparisons, ranking, or choice data is a discrete optimization problem that generalizes the linear ordering problem. We develop an approach to its solution using randomized algorithms. First, we show that maximizing the expected value of a randomized solution is equivalent to solving the lexicographic inference problem. As a result, the discrete problem is transformed into a continuous and unconstrained nonlinear program that can be solved, possibly only to a local optimum, using nonlinear optimization methods. Second, we show that a maximum likelihood procedure, which runs in polynomial time, can be used to implement the randomized algorithm. The maximum likelihood value determines a lower bound on the performance ratio of the randomized algorithm. We employ the proposed approach to infer lexicographic rules for individuals using data from a choice experiment for electronic tablets. These rules obtain substantially better fit and predictions than a previously described greedy algorithm, a local search algorithm, and a multinomial logit model.

关键词： lexicographic rules noncompensatory choice consumer search discrete optimization randomized algorithms analysis of algorithms maximum likelihood

来源：评论

学校读者我要写书评

暂无评论

Fast hyperbolic mapping based on the hierarchical community structure in complex networks

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2019年第12期2019卷

作者： Wang, Zuxi Sun, Lingjie Cai, Menglin Xie, Pengcheng Huazhong Univ Sci & Technol Sch Artificial Intelligence & Automat Wuhan 430074 Hubei Peoples R China Minist Educ Key Lab Image Proc & Intelligent Control Wuhan 430074 Hubei Peoples R China Natl Key Lab Sci & Technol Multispectral Informat Wuhan 430074 Hubei Peoples R China

The hyperbolic geometry of complex networks has recently emerged as a promising framework for the analysis of real and synthetic networks;one significant challenge of the hyperbolic geometry framework is the necessity to map large real networks to latent geometric spaces. Addressing this problem, we present a novel fast hyperbolic mapping algorithm called hyperbolic mapping based on the hierarchical community structure (HMCS), which is based on the network evolution model, the community-sector model in hyperbolic space and the hierarchical community structure (HCS) of complex networks. We present an index called community closeness (CC) to measure the adjacency relationship between the communities. Then we propose a ranking algorithm for first-level and second-level communities based on CC to determine the order of communities on the hyperbolic disc and map the network into hyperbolic space based on the order and the angular range of the corresponding sector of the second-level communities. We find that HMCS greatly reduces the mapping time complexity and achieves linearity () in sparse networks under the premise of ensuring better mapping accuracy compared with existing hyperbolic mapping algorithms. Experiments show that the HMCS algorithm occupies a unique attractive position in the space of tradeoffs between mapping accuracy and computational complexity.

关键词： network dynamics random graphs networks analysis of algorithms information processing

来源：评论

学校读者我要写书评

暂无评论

A limit field for orthogonal range searches in two-dimensional random point search trees

引用

STOCHASTIC PROCESSES AND THEIR APPLICATIONS 2019年第8期129卷 2912-2940页

作者： Broutin, Nicolas Sulzbach, Henning Sorbonne Univ Campus Pierre & Marie Curie Case Courrier 158 F-75252 Paris 05 France Univ Birmingham Sch Math Birmingham B15 2TT W Midlands England

We consider the cost of general orthogonal range queries in random quadtrees. The cost of a given query is encoded into a (random) function of four variables which characterize the coordinates of two opposite corners of the query rectangle. We prove that, when suitably shifted and rescaled, the random cost function converges uniformly in probability towards a random field that is characterized as the unique solution to a distributional fixed-point equation. We also state similar results for 2-d trees. Our results imply for instance that the worst case query satisfies the same asymptotic estimates as a typical query, and thereby resolve an open question of Chanzy et al. (2001). (C) 2018 Elsevier B.V. All rights reserved.

关键词： Quadtree Random partition Convergence in distribution Contraction method Range query Partial match analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

A note on the efficiency of position mechanisms with budget constraints

引用

INFORMATION PROCESSING LETTERS 2019年 143卷 28-33页

作者： Voudouris, Alexandros A. Univ Oxford Dept Comp Sci Oxford England

We study the social efficiency of several well-known mechanisms for the allocation of a set of available (advertising) positions to a set of competing budget-constrained users (advertisers). Specifically, we focus on the Generalized Second Price auction (GSP), the Vickrey-Clarke-Groves mechanism (VCG) and the Expressive Generalized First Price auction (EGFP). Using liquid welfare as our efficiency benchmark, we prove a tight bound of 2 on the liquid price of anarchy and stability of these mechanisms for pure Nash equilibria. (C) 2018 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms Position mechanisms Liquid welfare Budget constraints Liquid price of anarchy

来源：评论

学校读者我要写书评

暂无评论

A 52-approximation algorithm for coloring rooted subtrees of a degree 3 tree

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2020年第1期40卷 69-97页

作者： Rawat, Anuj Shayman, Mark Intel Corp Hillsboro OR 97124 USA Univ Maryland College Pk MD 20742 USA

A rooted tree R is a rooted subtree of a tree T if the tree obtained by replacing the directed edges of R by undirected edges is a subtree of T. We study the problem of assigning minimum number of colors to a given set of rooted subtrees R of a given tree T such that if any two rooted subtrees share a directed edge, then they are assigned different colors. The problem is NP hard even in the case when the degree of T is restricted to at most 3 (Erlebach and Jansen, in: Proceedings of the 30th Hawaii international conference on system sciences, p 221, 1997). We present a 52-approximation algorithm for this problem. The motivation for studying this problem stems from the problem of assigning wavelengths to multicast traffic requests in all-optical WDM tree networks.

关键词： Approximation algorithms analysis of algorithms Graph coloring Trees

来源：评论

学校读者我要写书评

暂无评论

A note on the integrality gap of the configuration LP for restricted Santa Claus

引用

INFORMATION PROCESSING LETTERS 2020年 164卷 106025-106025页

作者： Jansen, Klaus Rohwedder, Lars Univ Kiel Christian Albrechts Pl 4 D-24118 Kiel Germany Ecole Polytech Fed Lausanne Stn 14 CH-1015 Lausanne Switzerland

In the restricted Santa Claus problem we are given resources R and players P. Every resource j is an element of R. has a value v(j) and every player i is an element of P desires a set of resources R(i). We are interested in distributing the resources to players that desire them. The quality of a solution is measured by the least happy player, i.e., the lowest sum of resource values. This value should be maximized. The local search algorithm by Asadpour et al. [1] and its connection to the configuration LP has proved itself to be a very influential technique for this and related problems. Asadpour et al. used a local search to obtain a bound of 4 for the ratio of the fractional to the integral optimum of the configuration LP (the integrality gap). This bound is non-constructive, since the local search has not been shown to terminate in polynomial time. On the negative side, the worst instance known has an integrality gap of 2. Although much progress was made in this area, neither bound has been improved since. We present a better analysis that shows the integrality gap is not worse than 3 + 5/6 approximate to 3.8333. (C) 2020 Elsevier B.V. All rights reserved.

关键词： analysis of algorithms Configuration LP Fair allocation

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm to find minimum k-hop dominating set of interval graphs

引用

DISCRETE MATHEMATICS algorithms AND APPLICATIONS 2019年第2期11卷

作者： Barman, Sambhu Charan Pal, Madhumangal Mondal, Sukumar Shahid Matangini Hazra Govt Coll Women Dept Math Tamluk 721649 Purba Medinipur India Vidyasagar Univ Dept Appl Math Oceanol & Comp Programming Midnapore 721102 India Raja NL Khan Womens Coll Dept Math Midnapore 721102 India

For a fixed positive integer k, a k-hop dominating set D of a graph G = (V, E) is a subset of V such that every vertex x is an element of V is within k-steps from at least one vertex y is an element of D, i. e., d(x, y) <= k. A k-hop dominating set D is said to be minimal if there does not exist any D' subset of D such that D' is a k-hop dominating set of G. A dominating set D is said to be minimum k-hop dominating set, if it is minimal as well as it is k-hop dominating set. In this paper, we present an optimal algorithm to find a minimum k-hop dominating set of interval graphs with n vertices which runs in O(n) time.

关键词： Design of algorithms analysis of algorithms k-hop domination interval graphs

来源：评论

学校读者我要写书评

暂无评论

Community enhancement network embedding based on edge reweighting preprocessing

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2020年第10期2020卷

作者： Lv, Shaoqing Xiang, Ju Feng, Jingyu Wang, Honggang Lu, Guangyue Li, Min Xian Univ Posts & Telecommun Shaanxi Key Lab Informat Commun Network & Secur Xian Peoples R China Cent South Univ Sch Comp Sci & Engn Changsha Peoples R China Changsha Med Univ Neurosci Res Ctr Changsha Peoples R China Changsha Med Univ Dept Basic Med Sci Changsha Peoples R China

Network embedding has attracted considerable attention in recent years. It represents nodes in a network into a low-dimensional vector space while keeping the properties of the network. Some methods (e.g. ComE, MNMF, and CARE) have been proposed to preserve the community property in network embedding, and they have obtained good results in some downstream network analysis tasks. However, there still exists a significant challenge because nodes may lose important structural information following embedding. To address this problem, we propose a community structure enhancement framework for network embedding, based on edge reweighting. Through edge reweighting, the weight of intra-community edges is increased while the weight of inter-community edges is decreased. Therefore, after embedding, nodes in the same community are closer to each other than nodes in different communities in the embedding space. We apply the edge reweighting as a preprocessing stage in network embedding, and construct an enhanced network by incorporating enhanced community structures into the original network. By doing this, the embedded vectors from the enhanced network can better perform all downstream network analysis tasks. Extensive experiments are conducted on two network analysis tasks (community detection and node classification) with synthetic and real-world datasets. The results show that our method outperforms state-of-the-art network embedding methods.

关键词： random graphs networks clustering techniques analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Quantitative Convergence analysis of Iterated Expansive, Set-Valued Mappings

引用

MATHEMATICS OF OPERATIONS RESEARCH 2018年第4期43卷 1143-1176页

作者： Luke, D. Russell Thao, Nguyen H. Tama, Matthew K. Univ Gottingen Inst Numer & Angew Math D-37083 Gottingen Germany Delft Univ Technol Delft Ctr Syst & Control NL-2628 CD Delft Netherlands

We develop a framework for quantitative convergence analysis of Picard iterations of expansive set-valued fixed point mappings. There are two key components of the analysis. The first is a natural generalization of single-valued averaged mappings to expansive set-valued mappings that characterizes a type of strong calmness of the fixed point mapping. The second component to this analysis is an extension of the well-established notion of metric subregularity-or inverse calmness-of the mapping at fixed points. Convergence of expansive fixed point iterations is proved using these two properties, and quantitative estimates are a natural by-product of the framework. To demonstrate the application of the theory, we prove, for the first time, a number of results showing local linear convergence of nonconvex cyclic projections for inconsistent (and consistent) feasibility problems, local linear convergence of the forward-backward algorithm for structured optimization without convexity, strong or otherwise, and local linear convergence of the Douglas-Rachford algorithm for structured nonconvex minimization. This theory includes earlier approaches for known results, convex and nonconvex, as special cases.

关键词： analysis of algorithms feasibility fixed points Kurdyka-Lojasiewicz inequality linear convergence metric regularity nonconvex nonsmooth proximal algorithms subtransversality transversality

来源：评论

学校读者我要写书评

暂无评论

Worst-Case Efficient Sorting with QuickMergesort 21

Worst-Case Efficient Sorting with QuickMergesort

引用

Meeting on Algorithm Engineering and Experiments (ALENEX)

作者： Edelkamp, Stefan Weiss, Armin Kings Coll London London England Univ Stuttgart Stuttgart Germany

ISBN: (纸本)9781611975499

The two most prominent solutions for the sorting problem are Quicksort and Mergesort. While Quicksort is very fast on average, Mergesort additionally gives worst-case guarantees, but needs extra space for a linear number of elements. Worst-case efficient in-place sorting, however, remains a challenge: the standard solution, Heapsort, suffers from a bad cache behavior and is also not overly fast for in-cache instances. In this work we present median-of-medians Quick-Mergesort (MoMQuickMergesort), a new variant of QuickMergesort, which combines Quicksort with Mergesort allowing the latter to be implemented in place. Our new variant applies the median-of-medians algorithm for selecting pivots in order to circumvent the quadratic worst case. Indeed, we show that it uses at most n log n + 1:6n comparisons for n large enough. We experimentally confirm the theoretical estimates and show that the new algorithm outperforms Heapsort by far and is only around 10% slower than Introsort (std::sort implementation of stdlibc++), which has a rather poor guarantee for the worst case. We also simulate the worst case, which is only around 10% slower than the average case. In particular, the new algorithm is a natural candidate to replace Heapsort as a worst-case stopper in Introsort.

关键词： in-place sorting quicksort mergesort analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：