2 papers
cs.CC2019
Parameterized Intractability of Even Set and Shortest Vector Problem
Arnab Bhattacharyya, Édouard Bonnet, László Egri +5
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…
cs.DS2010
Improved Approximation for the Directed Spanner Problem
Arnab Bhattacharyya, Konstantin Makarychev
We prove that the size of the sparsest directed k-spanner of a graph can be approximated in polynomial time to within a factor of , for all k >= 3. This improv…