In this article we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read-only input) is sublinear in the number of edges to and the access to inpu...
详细信息
In this article we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read-only input) is sublinear in the number of edges to and the access to input is constrained. These questions arise in many natural settings, and in particular in the analysis of streaming algorithms, MapReduce or similar algorithms, or message passing distributed computing that model con- strained parallelism with sublinear central processing. We focus on weighted nonbipartite maximum matching in this article. For any constant p > 1, we provide an iterative sampling-based algorithm for computing a (1 - epsilon)-approximation of the weighted nonbipartite maximum matching that uses O(p /epsilon) rounds of sampling, and O(n(1+1/P)) space. The results extend to b-Matching with small changes. This article combines adaptive sketching literature and fast primal-dualalgorithms based on relaxed Dantzig-Wolfe decision procedures. Each round of sampling is implemented through linear sketches and can be executed in a single round of streaming or two rounds of MapReduce. The article also proves that nonstandard linear relaxations of a problem, in particular penalty-based formulations, are helpful in reducing the adaptive dependence of the iterations.
In this paper we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read only input) is sublinear in the number of edges m and the access to input d...
详细信息
ISBN:
(纸本)9781450335881
In this paper we consider graph algorithms in models of computation where the space usage (random accessible storage, in addition to the read only input) is sublinear in the number of edges m and the access to input data is constrained. These questions arises in many natural settings, and in particular in the analysis of MapReduce or similar algorithms that model constrained parallelism with sublinear central processing. In SPAA 2011, Lattanzi etal. provided a O(1) approximation of maximum matching using O(p) rounds of iterative filtering via mapreduce and O(n(1+1/)p) space of central processing for a graph with n nodes and m edges. We focus on weighted nonbipartite maximum matching in this paper. For any constant p > 1, we provide an iterative sampling based algorithm for computing a (1 - is an element of)-approximation of the weighted nonbipartite maximum matching that uses O( p/is an element of) rounds of sampling, and O(n(1+1/p)) space. The results extends to b-Matching with small changes. This paper combines adaptive sketching literature and fast primal-dualalgorithms based on relaxed Dantzig-Wolfe decision procedures. Each round of sampling is implemented through linear sketches and executed in a single round of MapReduce. The paper also proves that nonstandard linear relaxations of a problem, in particular penalty based formulations, are helpful in mapreduce and similar settings in reducing the adaptive dependence of the iterations.
We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods...
详细信息
We consider online optimization problems in which certain goods have to be acquired in order to provide a service or infrastructure. Classically, decisions for such problems are considered as final: one buys the goods. However, in many real world applications, there is a shift away from the idea of buying goods. Instead, leasing is often a more flexible and lucrative business model. Research has realized this shift and recently initiated the theoretical study of leasing models (Anthony and Gupta in Proceedings of the integer programming and combinatorial optimization: 12th International IPCO Conference, Ithaca, NY, USA, June 25-27, 2007;Meyerson in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 Oct 2005, Pittsburgh, PA, USA, 2005;Nagarajan and Williamson in Discret Optim 10(4):361-370, 2013) We extend this line of work and suggest a more systematic study of leasing aspects for a class of online optimization problems. We provide two major technical results. We introduce the leasing variant of online set multicover and give an -competitive algorithm (with n, m, and K being the number of elements, sets, and leases, respectively). Our results also imply improvements for the non-leasing variant of online set cover. Moreover, we extend results for the leasing variant of online facility location. Nagarajan and Williamson (Discret Optim 10(4):361-370, 2013) gave an -competitive algorithm for this problem (with n and K being the number of clients and leases, respectively). We remove the dependency on n (and, thereby, on time). In general, this leads to a bound of (with the maximal lease length ). For many natural problem instances, the bound improves to .
Random monotone operators are stochastic versions of maximal monotone operators which play an important role in stochastic nonsmooth optimization. Several stochastic nonsmooth optimization algorithms have been shown t...
详细信息
Random monotone operators are stochastic versions of maximal monotone operators which play an important role in stochastic nonsmooth optimization. Several stochastic nonsmooth optimization algorithms have been shown to converge to a zero of a mean operator defined as the expectation, in the sense of the Aumann integral, of a random monotone *** this note, we prove a strong law of large numbers for random monotone operators where the limit is the mean operator. We apply this result to the empirical risk minimization problem appearing in machine learning. We show that if the empirical risk minimizers converge as the number of data points goes to infinity, then they converge to an expected risk minimizer.
Texture segmentation still constitutes an on-going challenge, especially when processing large-size images. Recently, procedures integrating a scale-free (or fractal) wavelet-leader model allowed the problem to be ref...
详细信息
ISBN:
(纸本)9781538646588
Texture segmentation still constitutes an on-going challenge, especially when processing large-size images. Recently, procedures integrating a scale-free (or fractal) wavelet-leader model allowed the problem to be reformulated in a convex optimization framework by including a TV penalization. In this case, the TV penalty plays a prominent role with respect to the data fidelity term, which makes the approach costly in terms of memory and computation cost. The present contribution aims to investigate the potential of recent block-coordinate dual and primal-dual proximal algorithms for overcoming this numerical issue. Our study shows that a key ingredient in the success of the proposed block-coordinate approaches lies in the design of the blocks of variables which are updated at each iteration. Numerical experiments conducted over synthetic textures having piece-wise constant fractal properties confirm our theoretical analysis. The proposed lattice block design strategy is shown to yield significantly lower memory and computational requirements.
Texture segmentation still constitutes an on-going challenge, especially when processing large-size images. Recently, procedures integrating a scale-free (or fractal) wavelet-leader model allowed the problem to be ref...
详细信息
ISBN:
(纸本)9781538646595
Texture segmentation still constitutes an on-going challenge, especially when processing large-size images. Recently, procedures integrating a scale-free (or fractal) wavelet-leader model allowed the problem to be reformulated in a convex optimization framework by including a TV penalization. In this case, the TV penalty plays a prominent role with respect to the data fidelity term, which makes the approach costly in terms of memory and computation cost. The present contribution aims to investigate the potential of recent block-coordinate dual and primal-dual proximal algorithms for overcoming this numerical issue. Our study shows that a key ingredient in the success of the proposed block-coordinate approaches lies in the design of the blocks of variables which are updated at each iteration. Numerical experiments conducted over synthetic textures having piece-wise constant fractal properties confirm our theoretical analysis. The proposed lattice block design strategy is shown to yield significantly lower memory and computational requirements.
暂无评论