Approximation in (Poly-) logarithmic space
From MaRDI portal
Publication:2037114
DOI10.1007/s00453-021-00826-7OpenAlexW3141229161MaRDI QIDQ2037114
Arindam Biswas, Saket Saurabh, Venkatesh Raman
Publication date: 30 June 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2008.04416
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Selection from read-only memory and sorting with minimum data movement
- Advice classes of parametrized tractability
- Approximating linear programming is log-space complete for P
- Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
- A simple local 3-approximation algorithm for vertex cover
- Upper bounds for time-space trade-offs in sorting and selection
- Selection and sorting with limited storage
- A time-space tradeoff for sorting on non-oblivious machines
- Universal classes of hash functions
- Parallel approximation algorithms by positive linear programming
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- The complexity of planarity testing
- Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
- Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Relationships between nondeterministic and deterministic tape complexities
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Logspace optimization problems and their approximability properties
- Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
- Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond
- Depth-First Search Using $$O(n)$$ Bits
- Algorithmic construction of sets for k -restrictions
- A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
- Space-efficient Basic Graph Algorithms
- Approximation Resistance from Pairwise-Independent Subgroups
- Time-Space Tradeoffs for Dynamic Programming Algorithms in Trees and Bounded Treewidth Graphs
- A general Sequential Time-Space Tradeoff for Finding Unique Elements
- Undirected connectivity in log-space
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- Symmetric Complementation
- Problems complete for deterministic logarithmic space
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Nondeterminism within $P^ * $
- Selection and Sorting in the “Restore” Model
- Derandomized Concentration Bounds for Polynomials, and Hypergraph Maximal Independent Set
- A Framework for In-place Graph Algorithms
- Approximation in (Poly-) Logarithmic Space
- A parallel approximation algorithm for positive linear programming
- Embedding and canonizing graphs of bounded genus in logspace
- Analytical approach to parallel repetition
- Parameterized Complexity of Directed Steiner Tree on Sparse Graphs
- Parameterized Algorithms
This page was built for publication: Approximation in (Poly-) logarithmic space
