3 Search Results for "Harvey, Nicholas J. A."


Document
New Query Lower Bounds for Submodular Function Minimization

Authors: Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)


Abstract
We consider submodular function minimization in the oracle model: given black-box access to a submodular set function f:2^[n] → ℝ, find an element of arg min_S {f(S)} using as few queries to f(⋅) as possible. State-of-the-art algorithms succeed with Õ(n²) queries [Yin Tat Lee et al., 2015], yet the best-known lower bound has never been improved beyond n [Nicholas J. A. Harvey, 2008]. We provide a query lower bound of 2n for submodular function minimization, a 3n/2-2 query lower bound for the non-trivial minimizer of a symmetric submodular function, and a binom{n}{2} query lower bound for the non-trivial minimizer of an asymmetric submodular function. Our 3n/2-2 lower bound results from a connection between SFM lower bounds and a novel concept we term the cut dimension of a graph. Interestingly, this yields a 3n/2-2 cut-query lower bound for finding the global mincut in an undirected, weighted graph, but we also prove it cannot yield a lower bound better than n+1 for s-t mincut, even in a directed, weighted graph.

Cite as

Andrei Graur, Tristan Pollner, Vidhya Ramaswamy, and S. Matthew Weinberg. New Query Lower Bounds for Submodular Function Minimization. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 64:1-64:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{graur_et_al:LIPIcs.ITCS.2020.64,
  author =	{Graur, Andrei and Pollner, Tristan and Ramaswamy, Vidhya and Weinberg, S. Matthew},
  title =	{{New Query Lower Bounds for Submodular Function Minimization}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{64:1--64:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.64},
  URN =		{urn:nbn:de:0030-drops-117493},
  doi =		{10.4230/LIPIcs.ITCS.2020.64},
  annote =	{Keywords: submodular functions, query lower bounds, min cut}
}
Document
Approximating Hit Rate Curves using Streaming Algorithms

Authors: Zachary Drudi, Nicholas J. A. Harvey, Stephen Ingram, Andrew Warfield, and Jake Wires

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)


Abstract
A hit rate curve is a function that maps cache size to the proportion of requests that can be served from the cache. (The caching policy and sequence of requests are assumed to be fixed.) Hit rate curves have been studied for decades in the operating system, database and computer architecture communities. They are useful tools for designing appropriate cache sizes, dynamically allocating memory between competing caches, and for summarizing locality properties of the request sequence. In this paper we focus on the widely-used LRU caching policy. Computing hit rate curves is very efficient from a runtime standpoint, but existing algorithms are not efficient in their space usage. For a stream of m requests for n cacheable objects, all existing algorithms that provably compute the hit rate curve use space linear in n. In the context of modern storage systems, n can easily be in the billions or trillions, so the space usage of these algorithms makes them impractical. We present the first algorithm for provably approximating hit rate curves for the LRU policy with sublinear space. Our algorithm uses O( p^2 * log(n) * log^2(m) / epsilon^2 ) bits of space and approximates the hit rate curve at p uniformly-spaced points to within additive error epsilon. This is not far from optimal. Any single-pass algorithm with the same guarantees must use Omega(p^2 + epsilon^{-2} + log(n)) bits of space. Furthermore, our use of additive error is necessary. Any single-pass algorithm achieving multiplicative error requires Omega(n) bits of space.

Cite as

Zachary Drudi, Nicholas J. A. Harvey, Stephen Ingram, Andrew Warfield, and Jake Wires. Approximating Hit Rate Curves using Streaming Algorithms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 225-241, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{drudi_et_al:LIPIcs.APPROX-RANDOM.2015.225,
  author =	{Drudi, Zachary and Harvey, Nicholas J. A. and Ingram, Stephen and Warfield, Andrew and Wires, Jake},
  title =	{{Approximating Hit Rate Curves using Streaming Algorithms}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{225--241},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.225},
  URN =		{urn:nbn:de:0030-drops-53056},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.225},
  annote =	{Keywords: Cache analysis, hit rate curves, miss rate curves, streaming algorithms}
}
Document
Discrepancy Without Partial Colorings

Authors: Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)


Abstract
Spencer's theorem asserts that, for any family of n subsets of ground set of size n, the elements of the ground set can be "colored" by the values +1 or -1 such that the sum of every set is O(sqrt(n)) in absolute value. All existing proofs of this result recursively construct "partial colorings", which assign +1 or -1 values to half of the ground set. We devise the first algorithm for Spencer's theorem that directly computes a coloring, without recursively computing partial colorings.

Cite as

Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh. Discrepancy Without Partial Colorings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 258-273, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)


Copy BibTex To Clipboard

@InProceedings{harvey_et_al:LIPIcs.APPROX-RANDOM.2014.258,
  author =	{Harvey, Nicholas J. A. and Schwartz, Roy and Singh, Mohit},
  title =	{{Discrepancy Without Partial Colorings}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{258--273},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.258},
  URN =		{urn:nbn:de:0030-drops-47014},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.258},
  annote =	{Keywords: Combinatorial Discrepancy, Brownian Motion, Semi-Definite Programming, Randomized Algorithm}
}
  • Refine by Author
  • 2 Harvey, Nicholas J. A.
  • 1 Drudi, Zachary
  • 1 Graur, Andrei
  • 1 Ingram, Stephen
  • 1 Pollner, Tristan
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Submodular optimization and polymatroids

  • Refine by Keyword
  • 1 Brownian Motion
  • 1 Cache analysis
  • 1 Combinatorial Discrepancy
  • 1 Randomized Algorithm
  • 1 Semi-Definite Programming
  • Show More...

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 1 2014
  • 1 2015
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail