License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.69
URN: urn:nbn:de:0030-drops-112848
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11284/
Go to the corresponding LIPIcs Volume Portal

Yaroslavtsev, Grigory ; Zhou, Samson

Approximate F_2-Sketching of Valuation Functions

pdf-format:
LIPIcs-APPROX-RANDOM-2019-69.pdf (0.6 MB)

Abstract

We study the problem of constructing a linear sketch of minimum dimension that allows approximation of a given real-valued function f : F_2^n - > R with small expected squared error. We develop a general theory of linear sketching for such functions through which we analyze their dimension for most commonly studied types of valuation functions: additive, budget-additive, coverage, alpha-Lipschitz submodular and matroid rank functions. This gives a characterization of how many bits of information have to be stored about the input x so that one can compute f under additive updates to its coordinates.
Our results are tight in most cases and we also give extensions to the distributional version of the problem where the input x in F_2^n is generated uniformly at random. Using known connections with dynamic streaming algorithms, both upper and lower bounds on dimension obtained in our work extend to the space complexity of algorithms evaluating f(x) under long sequences of additive updates to the input x presented as a stream. Similar results hold for simultaneous communication in a distributed setting.

BibTeX - Entry

@InProceedings{yaroslavtsev_et_al:LIPIcs:2019:11284,
  author =	{Grigory Yaroslavtsev and Samson Zhou},
  title =	{{Approximate F_2-Sketching of Valuation Functions}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{69:1--69:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11284},
  URN =		{urn:nbn:de:0030-drops-112848},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.69},
  annote =	{Keywords: Sublinear algorithms, linear sketches, approximation algorithms}
}

Keywords: Sublinear algorithms, linear sketches, approximation algorithms
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Issue Date: 2019
Date of publication: 17.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI