Approximation in (Poly-) Logarithmic Space
type: Item
instance of: scholarly article
author: Arindam Biswas
author: Venkatesh Raman
author: Saket Saurabh
publication date: 2022-07-18T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
zbMATH DE Number: 7559387
zbMATH Keywords: approximation
zbMATH Keywords: logspace
zbMATH Keywords: logarithmic
zbMATH Keywords: log
zbMATH Keywords: space
zbMATH Keywords: small
zbMATH Keywords: limited
zbMATH Keywords: memory
zbMATH Keywords: ROM
zbMATH Keywords: Read-only
MaRDI profile type: Publication
cites work: The complexity of planarity testing
cites work: Algorithmic construction of sets for k -restrictions
cites work: Q3503433
cites work: Q3002828
cites work: A general Sequential Time-Space Tradeoff for Finding Unique Elements
cites work: A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
cites work: A time-space tradeoff for sorting on non-oblivious machines
cites work: Nondeterminism within $P^ * $
cites work: Advice classes of parametrized tractability
cites work: Universal classes of hash functions
cites work: A Framework for In-place Graph Algorithms
cites work: Approximation Resistance from Pairwise-Independent Subgroups
cites work: Selection and Sorting in the “Restore” Model
cites work: Parameterized Algorithms
cites work: Analytical approach to parallel repetition
cites work: Embedding and canonizing graphs of bounded genus in logspace
cites work: A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
cites work: Upper bounds for time-space trade-offs in sorting and selection
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
cites work: Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: A parallel approximation algorithm for positive linear programming
cites work: Selection and sorting with limited storage
cites work: Selection from read-only memory and sorting with minimum data movement
cites work: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
cites work: A simple local 3-approximation algorithm for vertex cover
cites work: Q4719333
cites work: Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
cites work: Symmetric Complementation
cites work: Undirected connectivity in log-space
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: Approximating linear programming is log-space complete for P
cites work: Logspace optimization problems and their approximability properties
cites work: Parallel approximation algorithms by positive linear programming
cites work: Q4955353
cites work: Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
full work available at URL: LIPIcs.MFCS.2020.16
OpenAlex ID: W3082645185
title: Approximation in (Poly-) Logarithmic Space
DOI: 10.4230/LIPICS.MFCS.2020.16
description: scientific article; zbMATH DE number 7559387