Source author record

Andrei Graur

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Discrete Mathematics Distributed, Parallel, and Cluster Computing math.CO math.OC

Catalog footprint

Research overview

2works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Improved Lower Bounds for Submodular Function Minimization

We provide a generic technique for constructing families of submodular functions to obtain lower bounds for submodular function minimization (SFM). Applying this technique, we prove that any deterministic SFM algorithm on a ground set of $n$ elements requires at least $Ω(n \log n)$ queries to an evaluation oracle. This is the first super-linear query complexity lower bound for SFM and improves upon the previous best lower bound of $2n$ given by [Graur et al., ITCS 2020]. Using our construction, we also prove that any (possibly randomized) parallel SFM algorithm, which can make up to $\mathsf{poly}(n)$ queries per round, requires at least $Ω(n / \log n)$ rounds to minimize a submodular function. This improves upon the previous best lower bound of $\tildeΩ(n^{1/3})$ rounds due to [Chakrabarty et al., FOCS 2021], and settles the parallel complexity of query-efficient SFM up to logarithmic factors due to a recent advance in [Jiang, SODA 2021].

preprint2020arXiv

Efficient Splitting of Measures and Necklaces

We provide approximation algorithms for two problems, known as NECKLACE SPLITTING and $ε$ -CONSENSUS SPLITTING. In the problem $ε$ -CONSENSUS SPLITTING, there are $n$ non-atomic probability measures on the interval $[0, 1]$ and $k$ agents. The goal is to divide the interval, via at most $n (k-1)$ cuts, into pieces and distribute them to the $k$ agents in an approximately equitable way, so that the discrepancy between the shares of any two agents, according to each measure, is at most $2 ε/ k$ . It is known that this is possible even for $ε= 0$ . NECKLACE SPLITTING is a discrete version of $ε$ -CONSENSUS SPLITTING. For $k = 2$ and some absolute positive constant $ε$ , both of these problems are PPAD-hard. We consider two types of approximation. The first provides every agent a positive amount of measure of each type under the constraint of making at most $n (k - 1)$ cuts. The second obtains an approximately equitable split with as few cuts as possible. Apart from the offline model, we consider the online model as well, where the interval (or necklace) is presented as a stream, and decisions about cutting and distributing must be made on the spot. For the first type of approximation, we describe an efficient algorithm that gives every agent at least $\frac{1}{nk}$ of each measure and works even online. For the second type of approximation, we provide an efficient online algorithm that makes $\text{poly}(n, k, ε)$ cuts and an offline algorithm making $O(nk \log \frac{k}ε)$ cuts. We also establish lower bounds for the number of cuts required in the online model for both problems even for $k=2$ agents, showing that the number of cuts in our online algorithm is optimal up to a logarithmic factor.

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.