Zobrazeno 1 - 10
of 457
pro vyhledávání: '"Ward, Justin"'
Autor:
Thiery, Theophile, Ward, Justin
We consider the weighted $k$-set packing problem, in which we are given a collection of weighted sets, each with at most $k$ elements and must return a collection of pairwise disjoint sets with maximum total weight. For $k = 3$, this problem generali
Externí odkaz:
http://arxiv.org/abs/2301.07537
We give improved multi-pass streaming algorithms for the problem of maximizing a monotone or arbitrary non-negative submodular function subject to a general $p$-matchoid constraint in the model in which elements of the ground set arrive one at a time
Externí odkaz:
http://arxiv.org/abs/2102.09679
Autor:
Thiery, Theophile, Ward, Justin
We study the following problem: Given a variable of interest, we would like to find a best linear predictor for it by choosing a subset of $k$ relevant variables obeying a matroid constraint. This problem is a natural generalization of subset selecti
Externí odkaz:
http://arxiv.org/abs/2102.09644
Autor:
Huang, Chien-Chung, Ward, Justin
We consider the problem of optimizing a coverage function under a $\ell$-matchoid of rank $k$. We design fixed-parameter algorithms as well as streaming algorithms to compute an exact solution. Unlike previous work that presumes linear representativi
Externí odkaz:
http://arxiv.org/abs/2011.06268
It is generally believed that submodular functions -- and the more general class of $\gamma$-weakly submodular functions -- may only be optimized under the non-negativity assumption $f(S) \geq 0$. In this paper, we show that once the function is expr
Externí odkaz:
http://arxiv.org/abs/1904.09354
Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for $k$-means with a provable guarantee is a simple local search h
Externí odkaz:
http://arxiv.org/abs/1612.07925
We consider the classical $k$-means clustering problem in the setting bi-criteria approximation, in which an algoithm is allowed to output $\beta k > k$ clusters, and must produce a clustering with cost at most $\alpha$ times the to the cost of the o
Externí odkaz:
http://arxiv.org/abs/1507.04227
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. A lot of recent effort has been devoted to developing distribute
Externí odkaz:
http://arxiv.org/abs/1507.03719
A wide variety of problems in machine learning, including exemplar clustering, document summarization, and sensor placement, can be cast as constrained submodular maximization problems. Unfortunately, the resulting submodular optimization problems ar
Externí odkaz:
http://arxiv.org/abs/1502.02606
Autor:
Ward, Justin, Zivny, Stanislav
Publikováno v:
ACM Transactions on Algorithms 12(4) Article no. 47 (2016)
We consider the maximization problem in the value oracle model of functions defined on $k$-tuples of sets that are submodular in every orthant and $r$-wise monotone, where $k\geq 2$ and $1\leq r\leq k$. We give an analysis of a deterministic greedy a
Externí odkaz:
http://arxiv.org/abs/1409.1399