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

WEIGHTED FRACTIONAL AND INTEGRAL KAPPA-MATCHING IN HYPERGRAPHS

DISCRETE APPLIED MATHEMATICS 1995年第2-3期57卷 255-269页

作者： SRIVASTAV, A STANGIER, P UNIV COLOGNE INST INFORMATD-50969 COLOGNEGERMANY

We consider the problem of finding polynomial-time approximations of maximal weighted k-matchings in a hypergraph and investigate the relationship between the integral and fractional maxima of the corresponding 0-1 integer linear program and its LP-relaxation. We extend results of Raghavan, who gave a deterministic approximation algorithm for unweighted k-matching, to the weighted case and compare the so obtained lower bound for the ratio of the integer and fractional maximum with a lower bound of Aharoni et al. (1985) and Alon et al. (1992).

关键词： HYPERGRAPH MATCHING INTEGER AND LINEAR PROGRAMMING randomized algorithm DERANDOMIZATION

来源：评论

学校读者我要写书评

暂无评论

Connected facility location via random facility sampling and core detouring

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2010年第8期76卷 709-726页

作者： Eisenbrand, Friedrich Grandoni, Fabrizio Rothvoss, Thomas Schafer, Guido Ecole Polytech Fed Lausanne Inst Math CH-1015 Lausanne Switzerland Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Ctr Wiskunde & Informat NL-1090 GB Amsterdam Netherlands

We present a simple randomized algorithmic framework for connected facility location problems. The basic idea is as follows: We run a black-box approximation algorithm for the unconnected facility location problem, randomly sample the clients, and open the facilities serving sampled clients in the approximate solution. Via a novel analytical tool, which we term core detouring, we show that this approach significantly improves over the previously best known approximation ratios for several NP-hard network design problems. For example, we reduce the approximation ratio for the connected facility location problem from 8.55 to 4.00 and for the single-sink rent-or-buy problem from 3.55 to 2.92. The mentioned results can be derandomized at the expense of a slightly worse approximation ratio. The versatility of our framework is demonstrated by devising improved approximation algorithms also for other related problems. (C) 2010 Elsevier Inc. All rights reserved.

关键词： Connected facility location Approximation algorithm randomized algorithm Network design

来源：评论

学校读者我要写书评

暂无评论

Distributed and on-line routing on tori

引用

algorithmICA 2002年第4期32卷 562-593页

作者： Yeh, TH Kuo, CM Lei, CL Yen, HC Natl Taiwan Univ Dept Elect Engn Taipei 10764 Taiwan

In this paper we study tire problem of assigning paths to packets oil N x N tori in an on-line and distributed fashion. By on-line we mean that the routing decisions must be made without any knowledge of future requests. Being distributed is an equally important feature of our design. for Such algorithms need knot know the global configuration of the network in the process of routing packets. We use the technique of competitive analysis to measure the performance of our design, In addition to showing an Omega(log N) lower bound on the competitive ratio, we present both deterministic and randomized algorithms which are O(log N) competitive with respect to the maximum load (i.e., congestion) on communication links.

关键词： routing on-line algorithm competitive analysis distributed algorithm randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Streaming Histogram Publication over Weighted Sliding Windows Under Differential Privacy

引用

Tsinghua Science and Technology 2024年第6期29卷 1674-1693页

作者： Xiujun Wang Lei Mo Xiao Zheng Zhe Dang School of Computer Science and Technology Anhui University of TechnologyMa’anshan 243032China Institute for Artificial Intelligence Hefei Comprehensive National Science CenterHefei 230088China Baosight Software(Anhui)Co.Ltd. Ma’anshan 243000China School of Electrical Engineering and Computer Science Washington State UniversityPullman 99164WAUSA

Continuously publishing histograms in data streams is crucial to many real-time applications,as it provides not only critical statistical information,but also reduces privacy leaking *** the importance of elements usually decreases over time in data streams,in this paper we model a data stream by a sequence of weighted sliding windows,and then study how to publish histograms over these windows *** existing literature can hardly solve this problem in a real-time way,because they need to buffer all elements in each sliding window,resulting in high computational overhead and prohibitive storage *** this paper,we overcome this drawback by proposing an online algorithm denoted by Efficient Streaming Histogram Publishing(ESHP)to continuously publish histograms over weighted sliding ***,our method first creates a novel sketching structure,called Approximate-Estimate Sketch(AESketch),to maintain the counting information of each histogram interval at every time instance;then,it creates histograms that satisfy the differential privacy requirement by smartly adding appropriate noise values into the sketching *** experimental results and rigorous theoretical analysis demonstrate that the ESHP method can offer equivalent data utility with significantly lower computational overhead and storage costs when compared to other existing methods.

关键词： differential privacy randomized algorithm streaming data publication weighted sliding window approximate statistics data usability computational complexity

来源：评论

学校读者我要写书评

暂无评论

Practical algorithm Substitution Attacks on Real-World Public-Key Cryptosystems

引用

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY 2023年 18卷 5069-5081页

作者： Jiang, Haodong Han, Jiang Zhang, Zhenfeng Ma, Zhi Wang, Hong Henan Key Lab Network Cryptog Technol Zhengzhou 450001 Henan Peoples R China Chinese Acad Sci Inst Software Beijing 100190 Peoples R China

The revelations about massive surveillance have created significant interest in algorithm substitution attack (ASA), where an honest implementation of a cryptographic primitive is replaced by a subverted one which can help "big brother" to break cryptographic security while generating output indistinguishable from the honest output. The current known ASAs on public-key cryptography are either dedicated for a type of concrete constructions with specific internal, or restrictive when applying to the real-word cryptographic standards (Ateniese et al., ACM CCS'15;Russell et al., ACM CCS'17;Chen et al., ASIACRYPT'20). In this paper, we first present a practical undetectable substitution for a general randomized algorithm with certain structure such that the randomness can be revealed to the big brother. Then, instantiating this randomized algorithm, we present a series of ASAs on core primitives in public-key cryptography including public-key encryption, key encapsulation mechanism, key exchange, and digital signature. In particular, our ASAs are universal in the sense that they do not rely on the internal description of the underlying cryptographic algorithm. Moreover, our ASAs are also practical since they can affect not only the widely deployed cryptographic standards, but also the ongoing NIST post-quantum standards.

关键词： algorithm substitution attack randomized algorithm public-key cryptography

来源：评论

学校读者我要写书评

暂无评论

Time-optimal construction of overlay networks

引用

DISTRIBUTED COMPUTING 2023年第3期36卷 313-347页

作者： Goette, Thorsten Hinnenthal, Kristian Scheideler, Christian Werthmann, Julian Paderborn Univ Dept Comp Sci Warburger Str 100 D-33098 Paderborn Germany

This article shows how to construct an overlay network of constant degree and diameter O(log n) in O(log n) time starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. Suppose the initial network's graph is weakly connected and has constant degree. In that case, our algorithm constructs the desired topology with each node sending and receiving only O(log n) messages in each round in O(log n) time w.h.p., which beats the currently best O(log3/2 n) time algorithm of Gotte et al. (International colloquium on structural information and communication complexity (SIROCCO), Springer, 2019). Since the problem cannot be solved faster than by using pointer jumping for O(log n) rounds (which would even require each node to communicate Q(n) bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of Kwok and Lau (Approximation, randomization, and combinatorial optimization. algorithms and techniques (APPROX/RANDOM 2014), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014). Additionally, we show how our algorithm can be used to efficiently solve graph problems in hybrid networks (Augustine et al. in Proceedings of the fourteenth annual ACM-SIAM symposium on discrete algorithms, SIAM, 2020). Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the initial edges is unrestricted, whereas only polylogarithmically many messages can be sent over edges that have been established throughout an algorithm's execution. For an (undirected) graph G with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in O(log n) time w.h.p.

关键词： Distributed protocol Peer-to-peer network randomized algorithm Expander

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for Cell Association and Scheduling in Femtocell Networks

引用

IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTING 2015年第3期3卷 432-443页

作者： Zhou, Hui Mao, Shiwen Agrawal, Prathima Auburn Univ Dept Elect & Comp Engn Auburn AL 36849 USA

Femtocells are recognized as effective for improving network coverage and capacity and for reducing power consumption due to the reduced range of wireless transmissions. Although highly appealing, a plethora of challenging problems need to be addressed for fully harvesting its potential. In this paper, we investigate the problem of cell association and service scheduling in femtocell networks. In addition to the general goal of offloading traffic from the macrobase station (BS), we also aim at minimizing the latency of service requested by the users, while considering both open and closed access strategies. We show that the cell association problem is NP-hard, and propose several near-optimal solution algorithms for assigning users to BS s, including a sequential fixing algorithm, a rounding approximation algorithm, a greedy approximation algorithm, and a randomized algorithm. For service scheduling, we develop an optimal algorithm to minimize the average waiting time for the users associated with the same BS. The proposed algorithms are analyzed with respect to performance bounds, approximation ratios, and optimality, and are evaluated with simulations.

关键词： Approximation algorithm cell association femtocell load balancing randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A general method for geometric feature matching and model extraction

引用

INTERNATIONAL JOURNAL OF COMPUTER VISION 2001年第1期45卷 39-54页

作者： Olson, CF Univ Washington Dept Comp & Software Syst Bothell WA 98011 USA

Popular algorithms for feature matching and model extraction fall into two broad categories: generate-and-test and Hough transform variations. However, both methods suffer from problems in practical implementations. Generate-and-test methods are sensitive to noise in the data. They often fail when the generated model fit is poor due to error in the data used to generate the model position. Hough transform variations are less sensitive to noise, but implementations for complex problems suffer from large time and space requirements and from the detection of false positives. This paper describes a general method for solving problems where a model is extracted from, or fit to, data that draws benefits from both generate-and-test methods and those based on the Hough transform, yielding a method superior to both. An important component of the method is the subdivision of the problem into many subproblems. This allows efficient generate-and-test techniques to be used, including the use of randomization to limit the number of subproblems that must be examined. Each subproblem is solved using pose space analysis techniques similar to the Hough transform, which lowers the sensitivity of the method to noise. This strategy is easy to implement and results in practical algorithms that are efficient and robust. We describe case studies of the application of this method to object recognition, geometric primitive extraction, robust regression, and motion segmentation.

关键词： divide-and-conquer feature matching generate-and-test geometric primitive extraction Hough transform model extraction motion segmentation object recognition randomized algorithm robust regression

来源：评论

学校读者我要写书评

暂无评论

Estimation of horizontal and vertical translations of large images based on columns and rows mean energy matching

引用

MULTIDIMENSIONAL SYSTEMS AND SIGNAL PROCESSING 2014年第2期25卷 273-294页

作者： Skubalska-Rafajlowicz, Ewa Wroclaw Univ Technol Inst Comp Engn Automat & Robot PL-50370 Wroclaw Poland

In this paper mean energy lateral histograms have been developed and used for the translation of frames detection and for the estimation of a shift vector in large image frames. 2-D translation problem is solved by two almost independent 1-D problems based on the mean energy lateral histograms. We formulate a simple optimization for estimating vertical or horizontal translations of the frame. The optimization goal is to find the best match between energies (squared norms) of rows (columns) of the image and the reference frame. The shift estimate is calculated as the minimizer of the least squares, maximum deviation or the sum of absolute deviations criterion. However, the first criterion is preferred, the last two almost always gave the same results when the noise level is low. The proposed method is faster than the FFT based phase-correlation approach. An iterative version of the algorithm is presented which is very reliable and usually converges in at most two iterations. A randomized version of the method which reduce further the computational cost for large images problems is also proposed. Experimental results are provided and discussed.

关键词： Image stabilization Shift estimation randomized algorithm Lateral energy histograms

来源：评论

学校读者我要写书评

暂无评论

Abrasive waterjet machining simulation by SPH method

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2010年第1-4期50卷 227-234页

作者： Wang Jianming Gao Na Gong Wenjun Shandong Univ Sch Mech Engn Jinan 250061 Peoples R China

Abrasive waterjet machining (AWJM) is a non-conventional process. The mechanism of material removing in AWJM for ductile materials and existing erosion models are reviewed in this paper. To overcome the difficulties of fluid-solid interaction and extra-large deformation problem using finite element method (FEM), the SPH-coupled FEM modeling for abrasive waterjet machining simulation is presented, in which the abrasive waterjet is modeled by SPH particles and the target material is modeled by FE. The two parts interact through contact algorithm. The creativity of this model is multi-materials SPH particles, which contain abrasive and water and mix together uniformly. To build the model, a randomized algorithm is proposed. The material model for the abrasive is first presented. Utilizing this model, abrasive waterjet penetrating the target materials with high velocity is simulated and the mechanism of erosion is depicted. The relationship between the depth of penetration and jet parameters, including water pressure and traverse speed, etc., are analyzed based on the simulation. The results agree with the experimental data well. It will be a benefit to understand the abrasive waterjet cutting mechanism and optimize the operating parameters.

关键词： Abrasive waterjet machining (AWJM) randomized algorithm Coupling SPH/FEM Abrasive material models

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：