Approximation in (Poly-) Logarithmic Space
From MaRDI portal
Publication:5089177
DOI10.4230/LIPIcs.MFCS.2020.16OpenAlexW3082645185MaRDI QIDQ5089177
Arindam Biswas, Venkatesh Raman, Saket Saurabh
Publication date: 18 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.16
Related Items (2)
Approximation in (Poly-) logarithmic space ⋮ Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
Cites Work
- 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
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Relationships between nondeterministic and deterministic tape complexities
- 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
- Algorithmic construction of sets for k -restrictions
- A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
- Approximation Resistance from Pairwise-Independent Subgroups
- 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
- A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation
- Nondeterminism within $P^ * $
- Selection and Sorting in the “Restore” Model
- A Framework for In-place Graph Algorithms
- 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
