Zobrazeno 1 - 10
of 136
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
Autor:
Ward, Justin
Standard local search algorithms for combinatorial optimization problems repeatedly apply small changes to a current solution to improve the problem's given objective function. In contrast, non-oblivious local search algorithms are guided by an auxil
Externí odkaz:
http://hdl.handle.net/1807/34957
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