BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Justin Ward

Justin Ward appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and AlgorithmsArtificial IntelligenceDistributed, Parallel, and Cluster ComputingMachine LearningDiscrete Mathematics

Catalog footprint

What is connected

12works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2023arXiv

An Improved Approximation for Maximum Weighted $k$-Set Packing

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 generalizes the classical 3-dimensional matching problem listed as one of the Karp's original 21 NP-complete problems. We give an algorithm attaining an approximation factor of $1.786$ for weighted 3-set packing, improving on the recent best result of $2-\frac{1}{63,700,992}$ due to Neuwohner. Our algorithm is based on the local search procedure of Berman that attempts to improve the sum of squared weights rather than the problem's objective. When using exchanges of size at most $k$, this algorithm attains an approximation factor of $\frac{k+1}{2}$. Using exchanges of size $k^2(k-1) + k$, we provide a relatively simple analysis to obtain an approximation factor of 1.811 when $k = 3$. We then show that the tools we develop can be adapted to larger exchanges of size $2k^2(k-1) + k$ to give an approximation factor of 1.786. Although our primary focus is on the case $k = 3$, our approach in fact gives slightly stronger improvements on the factor $\frac{k+1}{2}$ for all $k > 3$. As in previous works, our guarantees hold also for the more general problem of finding a maximum weight independent set in a $(k+1)$-claw free graph.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Two-Sided Weak Submodularity for Matroid Constrained Optimization and Regression

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 selection problems where it is necessary to spread observations amongst multiple different classes. We derive new, strengthened guarantees for this problem by improving the analysis of the residual random greedy algorithm and by developing a novel distorted local-search algorithm. To quantify our approximation guarantees, we refine the definition of weak submodularity by Das and Kempe and introduce the notion of an upper submodularity ratio, which we connect to the minimum $k$-sparse eigenvalue of the covariance matrix. More generally, we look at the problem of maximizing a set function $f$ with lower and upper submodularity ratio $γ$ and $β$ under a matroid constraint. For this problem, our algorithms have asymptotic approximation guarantee $1/2$ and $1-e^{-1}$ as the function is closer to being submodular. As a second application, we show that the Bayesian A-optimal design objective falls into our framework, leading to new guarantees for this problem as well.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Improved Multi-Pass Streaming Algorithms for Submodular Maximization with Matroid Constraints

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 in a stream. The family of constraints we consider generalizes both the intersection of $p$ arbitrary matroid constraints and $p$-uniform hypergraph matching. For monotone submodular functions, our algorithm attains a guarantee of $p+1+\varepsilon$ using $O(p/\varepsilon)$-passes and requires storing only $O(k)$ elements, where $k$ is the maximum size of feasible solution. This immediately gives an $O(1/\varepsilon)$-pass $(2+\varepsilon)$-approximation algorithms for monotone submodular maximization in a matroid and $(3+\varepsilon)$-approximation for monotone submodular matching. Our algorithm is oblivious to the choice $\varepsilon$ and can be stopped after any number of passes, delivering the appropriate guarantee. We extend our techniques to obtain the first multi-pass streaming algorithm for general, non-negative submodular functions subject to a $p$-matchoid constraint with a number of passes independent of the size of the ground set and $k$. We show that a randomized $O(p/\varepsilon)$-pass algorithm storing $O(p^3k\log(k)/\varepsilon^3)$ elements gives a $(p+1+\barγ+O(\varepsilon))$-approximation, where $\bar{gamma}$ is the guarantee of the best-known offline algorithm for the same problem.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A New Framework for Distributed Submodular Maximization

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 distributed algorithms for these problems. However, these results suffer from high number of rounds, suboptimal approximation ratios, or both. We develop a framework for bringing existing algorithms in the sequential setting to the distributed setting, achieving near optimal approximation ratios for many settings in only a constant number of MapReduce rounds. Our techniques also give a fast sequential algorithm for non-monotone maximization subject to a matroid constraint.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A bi-criteria approximation algorithm for $k$ Means

We consider the classical $k$-means clustering problem in the setting bi-criteria approximation, in which an algoithm is allowed to output $βk > k$ clusters, and must produce a clustering with cost at most $α$ times the to the cost of the optimal set of $k$ clusters. We argue that this approach is natural in many settings, for which the exact number of clusters is a priori unknown, or unimportant up to a constant factor. We give new bi-criteria approximation algorithms, based on linear programming and local search, respectively, which attain a guarantee $α(β)$ depending on the number $βk$ of clusters that may be opened. Our gurantee $α(β)$ is always at most $9 + ε$ and improves rapidly with $β$ (for example: $α(2)<2.59$, and $α(3) < 1.4$). Moreover, our algorithms have only polynomial dependence on the dimension of the input data, and so are applicable in high-dimensional settings.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Maximizing k-Submodular Functions and Beyond

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 algorithm that shows that any such function can be approximated to a factor of $1/(1+r)$. For $r=k$, we give an analysis of a randomised greedy algorithm that shows that any such function can be approximated to a factor of $1/(1+\sqrt{k/2})$. In the case of $k=r=2$, the considered functions correspond precisely to bisubmodular functions, in which case we obtain an approximation guarantee of $1/2$. We show that, as in the case of submodular functions, this result is the best possible in both the value query model, and under the assumption that $NP\neq RP$. Extending a result of Ando et al., we show that for any $k\geq 3$ submodularity in every orthant and pairwise monotonicity (i.e. $r=2$) precisely characterize $k$-submodular functions. Consequently, we obtain an approximation guarantee of $1/3$ (and thus independent of $k$) for the maximization problem of $k$-submodular functions.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Power of Randomization: Distributed Submodular Maximization on Massive Datasets

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 are often too large to be solved on a single machine. We develop a simple distributed algorithm that is embarrassingly parallel and it achieves provable, constant factor, worst-case approximation guarantees. In our experiments, we demonstrate its efficiency in large problems with different kinds of constraints with objective values always close to what is achievable in the centralized setting.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Optimal approximation for submodular and supermodular optimization with bounded curvature

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a nondecreasing submodular function or minimize a nonincreasing supermodular function in the setting of bounded total curvature $c$. In the case of submodular maximization with curvature $c$, we obtain a $(1-c/e)$-approximation --- the first improvement over the greedy $(1-e^{-c})/c$-approximation of Conforti and Cornuejols from 1984, which holds for a cardinality constraint, as well as recent approaches that hold for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and non-oblivious local search, and allows us to approximately maximize the sum of a nonnegative, nondecreasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. We define an extension of the notion of curvature to general monotone set functions and show $(1-c)$-approximation for maximization and $1/(1-c)$-approximation for minimization cases. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Submodular Stochastic Probing on Matroids

In a stochastic probing problem we are given a universe $E$, where each element $e \in E$ is active independently with probability $p_e$, and only a probe of e can tell us whether it is active or not. On this universe we execute a process that one by one probes elements --- if a probed element is active, then we have to include it in the solution, which we gradually construct. Throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. This abstract model was presented by Gupta and Nagarajan (IPCO '13), and provides a unified view of a number of problems. Thus far, all the results falling under this general framework pertain mainly to the case in which we are maximizing a linear objective function of the successfully probed elements. In this paper we generalize the stochastic probing problem by considering a monotone submodular objective function. We give a $(1 - 1/e)/(k_{in} + k_{out}+1)$-approximation algorithm for the case in which we are given $k_{in}$ matroids as inner constraints and $k_{out}$ matroids as outer constraints. Additionally, we obtain an improved $1/(k_{in} + k_{out})$-approximation algorithm for linear objective functions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint

We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm (Calinescu, Chekuri, Pal and Vondrak, 2008), our algorithm is extremely simple and requires no rounding. It consists of the greedy algorithm followed by local search. Both phases are run not on the actual objective function, but on a related non-oblivious potential function, which is also monotone submodular. Our algorithm runs in randomized time O(n^8u), where n is the rank of the given matroid and u is the size of its ground set. We additionally obtain a 1-1/e-eps approximation algorithm running in randomized time O (eps^-3n^4u). For matroids in which n = o(u), this improves on the runtime of the continuous greedy algorithm. The improvement is due primarily to the time required by the pipage rounding phase, which we avoid altogether. Furthermore, the independence of our algorithm from pipage rounding techniques suggests that our general approach may be helpful in contexts such as monotone submodular maximization subject to multiple matroid constraints. Our approach generalizes to the case where the monotone submodular function has restricted curvature. For any curvature c, we adapt our algorithm to produce a (1-e^-c)/c approximation. This result complements results of Vondrak (2008), who has shown that the continuous greedy algorithm produces a (1-e^-c)/c approximation when the objective function has curvature c. He has also proved that achieving any better approximation ratio is impossible in the value oracle model.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Large Neighborhood Local Search for the Maximum Set Packing Problem

In this paper we consider the classical maximum set packing problem where set cardinality is upper bounded by $k$. We show how to design a variant of a polynomial-time local search algorithm with performance guarantee $(k+2)/3$. This local search algorithm is a special case of a more general procedure that allows to swap up to $Θ(\log n)$ elements per iteration. We also design problem instances with locality gap $k/3$ even for a wide class of exponential time local search procedures, which can swap up to $cn$ elements for a constant $c$. This shows that our analysis of this class of algorithms is almost tight.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A $(k + 3)/2$-approximation algorithm for monotone submodular maximization over a $k$-exchange system

We consider the problem of maximizing a monotone submodular function in a $k$-exchange system. These systems, introduced by Feldman et al., generalize the matroid k-parity problem in a wide class of matroids and capture many other combinatorial optimization problems. Feldman et al. show that a simple non-oblivious local search algorithm attains a $(k + 1)/2$ approximation ratio for the problem of linear maximization in a $k$-exchange system. Here, we extend this approach to the case of monotone submodular objective functions. We give a deterministic, non-oblivious local search algorithm that attains an approximation ratio of $(k + 3)/2$ for the problem of maximizing a monotone submodular function in a $k$-exchange system.

0 citations0 reviewsNo code linkedOpen access