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

Efficient Online Linear Optimization with approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Garber, Dan Technion - Israel Institute of Technology

We revisit the problem of online linear optimization in case the set of feasible actions is accessible through an approximated linear optimization oracle with a factor α multiplicative approximation guarantee. This setting is in particular interesting since it captures natural online extensions of well-studied offline linear optimization problems which are NP-hard, yet admit efficient approximation algorithms. The goal here is to minimize the α-regret which is the natural extension of the standard regret in online learning to this setting. We present new algorithms with significantly improved oracle complexity for both the full information and bandit variants of the problem. Mainly, for both variants, we present α-regret bounds of O(T −1/3), were T is the number of prediction rounds, using only O(log T) calls to the approximation oracle per iteration, on average. These are the first results to obtain both average oracle complexity of O(log T) (or even poly-logarithmic in T) and α-regret bound O(T −c) for a constant c > 0, for both variants. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

On practical accuracy of edit distance approximation algorithms

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Hanada, Hiroyuki Kudo, Mineichi Nakamura, Atsuyoshi Graduate School of Information Science and Technology Hokkaido University Kita 14 Nishi 9 Kita-ku Sapporo Hokkaido060-0814 Japan Department of Computer Science Nagoya Institute of Technology. Gokiso-cho Showa-ku Nagoya Aichi Japan

The edit distance is a basic string similarity measure used in many applications such as text mining, signal processing, bioinformatics, and so on. However, the computational cost can be a problem when we repeat many distance calculations as seen in real-life searching situations. A promising solution to cope with the problem is to approximate the edit distance by another distance with a lower computational cost. There are, indeed, many distances have been proposed for approximating the edit distance. However, their approximation accuracies are evaluated only theoretically: many of them are evaluated only with big-oh (asymptotic) notations, and without experimental analysis. Therefore, it is beneficial to know their actual performance in real applications. In this study we compared existing six approximation distances in two approaches: (i) we refined their theoretical approximation accuracy by calculating up to the constant coefficients, and (ii) we conducted some experiments, in one artificial and two real-life data sets, to reveal under which situations they perform best. As a result we obtained the following results: [Batu 2006] is the best theoretically and [Andoni 2010] experimentally. Theoretical considerations show that [Batu 2006] is the best if the string length n is large enough (n ≥ 300). [Andoni 2010] is experimentally the best for most data sets and theoretically the second best. [Bar-Yossef 2004], [Charikar 2006] and [Sokolov 2007], despite their middle-level theoretical performance, are Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Efficient approximation algorithms for string kernel based sequence classification

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Farhan, Muhammad Zaman, Arif Tariq, Juvaria Shabbir, Mudassir Khan, Imdad Ullah Department of Computer Science School of Science and Engineering Lahore University of Management Sciences Lahore Pakistan Department of Mathematics School of Science and Engineering Lahore University of Management Sciences Lahore Pakistan Department of Computer Science Information Technology University Lahore Pakistan

Sequence classification algorithms, such as SVM, require a definition of distance (similarity) measure between two sequences. A commonly used notion of similarity is the number of matches between k-mers (k-length subsequences) in the two sequences. Extending this definition, by considering two k-mers to match if their distance is at most m, yields better classification performance. This, however, makes the problem computationally much more complex. Known algorithms to compute this similarity have computational complexity that render them applicable only for small values of k and m. In this work, we develop novel techniques to efficiently and accurately estimate the pairwise similarity score, which enables us to use much larger values of k and m, and get higher predictive accuracy. This opens up a broad avenue of applying this classification approach to audio, images, and text sequences. Our algorithm achieves excellent approximation performance with theoretical guarantees. In the process we solve an open combinatorial problem, which was posed as a major hindrance to the scalability of existing solutions. We give analytical bounds on quality and runtime of our algorithm and report its empirical performance on real world biological and music sequences datasets. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Distributed approximation algorithms for the multiple knapsack problem

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Murthy, Ananth Yeshwanth, Chandan Rao, Shrisha

We consider the distributed version of the Multiple Knapsack Problem (MKP), where m items are to be distributed amongst n processors, each with a knapsack. We propose different distributed approximation algorithms with a tradeoff between time and message complexities. The algorithms are based on the greedy approach of assigning the best item to the knapsack with the largest capacity. These algorithms obtain a solution with a bound of n+11 times the optimum solution, with either O (m log n) time and O (mn) messages, or O (m) time and O (mn2) messages.68W15, 68W15 Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Altschuler, Jason Weed, Jonathan Rigollet, Philippe Massachusetts Institute of Technology

Computing optimal transport distances such as the earth mover's distance is a fundamental problem in machine learning, statistics, and computer vision. Despite the recent introduction of several algorithms with good empirical performance, it is unknown whether general optimal transport distances can be approximated in near-linear time. This paper demonstrates that this ambitious goal is in fact achieved by Cuturi's Sinkhorn Distances. This result relies on a new analysis of Sinkhorn iteration, which also directly suggests a new greedy coordinate descent algorithm, Greenkhorn, with the same theoretical guarantees. Numerical simulations illustrate that Greenkhorn significantly outperforms the classical Sinkhorn algorithm in practice. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

New subquadratic approximation algorithms for the girth

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Dahlgaard, Søren Bæk Tejs Knudsen, Mathias Stöckel, Morten University of Copenhagen Denmark

We consider the problem of approximating the girth, g, of an unweighted and undirected graph G "pV, Eq with n nodes and m edges. A seminal result of Itai and Rodeh [SICOMP’78] gave an additive 1-approximation in Opn2q time, and the main open question is thus how well we can do in subquadratic time. In this paper we present two main results. The first is a p1 ` Ε, Op1qq-approximation in truly subquadratic time. Specifically, for any k ě 2 our algorithm returns a cycle of length 2 rg{2s ` 2 Q2pkg´1qU in Õpn2´1{kq time. This generalizes the results of Lingas and Lundell [IPL’09] who showed it for the special case of k "2 and Roditty and Vassilevska Williams [SODA’12] who showed it for k "3. Our second result is to present an Op1q-approximation running in Opn1`Εq time for any Ε ą 0. Prior to this work the fastest constant-factor approximation was the Õpn3{2q time 8{3-approximation of Lingas and Lundell [IPL’09] using the algorithm corresponding to the special case k "2 of our first result. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Interpolating between k-median and k-center: approximation algorithms for ordered k-median

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Chakrabarty, Deeparnab Swamy, Chaitanya Dept. of Computer Science Dartmouth College HanoverNH03755-3510 United States Dept. of Combinatorics and Optimization Univ. Waterloo WaterlooONN2L 3G1 Canada

We consider a generalization of k-median and k-center, called the ordered k-median problem. In this problem, we are given a metric space (D, {cij}) with n = |D| points, and a non-increasing weight vector w ∈ Rn+, and the goal is to open k centers and assign each point each point j ∈ D to a center so as to minimize w1 · (largest assignment cost) + w2 · (second-largest assignment cost) +... + wn · (n-th largest assignment cost). We give an (18 + ǫ)-approximation algorithm for this problem. Our algorithms utilize Lagrangian relaxation and the primal-dual schema, combined with an enumeration procedure of Aouad and Segev. For the special case of {0, 1}-weights, which models the problem of minimizing the largest assignment costs that is interesting in and of by itself, we provide a novel reduction to the (standard) k-median problem, showing that LP-relative guarantees for k-median translate to guarantees for the ordered k-median problem;this yields a nice and clean (8.5 + ǫ)-approximation algorithm for {0, 1} weights. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Parameterized approximation algorithms for some location problems in graphs

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Leitert, Arne Dragan, Feodor F. Department of Computer Science Kent State University KentOH United States

We develop efficient parameterized, with additive error, approximation algorithms for the (Connected) r-Domination problem and the (Connected) p-Center problem for unweighted and undirected graphs. Given a graph G, we show how to construct a (connected) (r + O(μ)- dominating set D with |D| ≤ |D∗| efficiently. Here, D∗ is a minimum (connected) r-dominating set of G and μ is our graph parameter, which is the tree-breadth or the cluster diameter in a layering partition of G. Additionally, we show that a +O(μ)-approximation for the (Connected) p-Center problem on G can be computed in polynomial time. Our interest in these parameters stems from the fact that in many real-world networks, including Internet application networks, web networks, collaboration networks, social networks, biological networks, and others, and in many structured classes of graphs these parameters are small constants. Copyright © 2017, The Authors. All rights reserved.

关键词： approximation algorithms

Polylogarithmic approximation algorithms for weighted-F-deletion problems

学校读者我要写书评

暂无评论

arXiv 2017年

作者： Agrawal, Akanksha Lokshtanov, Daniel Misra, Pranabendu Saurabh, Saket Zehavi, Meirav University of Bergen Bergen Norway University of Bergen Bergen Norway Institute of Mathematical Sciences Chennai India University of Bergen Bergen Norway Institute of Mathematical Sciences HBNI Chennai India University of Bergen Bergen Norway

Let F be a family of graphs. A canonical vertex deletion problem corresponding to F is defined as follows: given an n-vertex undirected graph G and a weight function w: V (G) → R, find a minimum weight subset S ⊆ V (G) such that G − S belongs to F. This is known as Weighted F Vertex Deletion problem. In this paper we devise a recursive scheme to obtain O(logO(1) n)-approximation algorithms for such problems, building upon the classic technique of finding balanced separators in a graph. Roughly speaking, our scheme applies to those problems, where an optimum solution S together with a well-structured set X, form a balanced separator of the input graph. In this paper, we obtain the first O(logO(1) n)approximation algorithms for the following vertex deletion problems. • We give an O(log2 n)-factor approximation algorithm for Weighted Chordal Vertex Deletion (WCVD), the vertex deletion problem to the family of chordal graphs. On the way to this algorithm, we also obtain a constant factor approximation algorithm for Multicut on chordal graphs. • We give an O(log3 n)-factor approximation algorithm for Weighted Distance Hereditary Vertex Deletion (WDHVD), also known as Weighted Rankwidth-1 Vertex Deletion (WR-1VD). This is the vertex deletion problem to the family of distance hereditary graphs, or equivalently, the family of graphs of rankwidth 1. Our methods also allow us to obtain in a clean fashion a O(log1.5 n)-approximation algorithm for the Weighted F Vertex Deletion problem when F is a minor closed family excluding at least one planar graph. For the unweighted version of the problem constant factor approximation algorithms are were known [Fomin et al., FOCS 2012], while for the weighted version considered here an O(log n log log n)-approximation algorithm follows from [Bansal et al. SODA 2017]. We believe that our recursive scheme can be applied to obtain O(logO(1) n)-approximation algorithms for many other problems as well. Copyright © 2017, The Authors. All rights

关键词： approximation algorithms