1 Search Results for "Rathi, Rajat"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.61
Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization

Authors: Rohit Gurjar and Rajat Rathi

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
A set function f : 2^E → ℝ on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any S ⊆ E and x,y ∉ S, we have f(S ∪ {x,y}) - f(S ∪ {y}) ≤ f(S ∪ {x}) - f(S). Submodular minimization problem asks for finding the minimum value a given submodular function takes. We give an algebraic algorithm for this problem for a special class of submodular functions that are "linearly representable". It is known that every submodular function f can be decomposed into a sum of two monotone submodular functions, i.e., there exist two non-decreasing submodular functions f₁,f₂ such that f(S) = f₁(S) + f₂(E ⧵ S) for each S ⊆ E. Our class consists of those submodular functions f, for which each of f₁ and f₂ is a sum of k rank functions on families of subspaces of 𝔽ⁿ, for some field 𝔽. Our algebraic algorithm for this class of functions can be parallelized, and thus, puts the problem of finding the minimizing set in the complexity class randomized NC. Further, we derandomize our algorithm so that it needs only O(log²(kn|E|)) many random bits. We also give reductions from two combinatorial optimization problems to linearly representable submodular minimization, and thus, get such parallel algorithms for these problems. These problems are (i) covering a directed graph by k a-arborescences and (ii) packing k branchings with given root sets in a directed graph.
Cite as

Rohit Gurjar and Rajat Rathi. Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 61:1-61:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gurjar_et_al:LIPIcs.ICALP.2020.61,
  author =	{Gurjar, Rohit and Rathi, Rajat},
  title =	{{Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{61:1--61:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.61},
  URN =		{urn:nbn:de:0030-drops-124687},
  doi =		{10.4230/LIPIcs.ICALP.2020.61},
  annote =	{Keywords: Submodular Minimization, Parallel Algorithms, Derandomization, Algebraic Algorithms}
}
  • Refine by Author
  • 1 Gurjar, Rohit
  • 1 Rathi, Rajat

  • Refine by Classification
  • 1 Mathematics of computing → Combinatorial optimization
  • 1 Theory of computation → Parallel algorithms
  • 1 Theory of computation → Pseudorandomness and derandomization

  • Refine by Keyword
  • 1 Algebraic Algorithms
  • 1 Derandomization
  • 1 Parallel Algorithms
  • 1 Submodular Minimization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact