Vikrant Ashvinkumar

activity

20192026

collaborators

Showing 2024Show all

3 papers · 1 filter

cs.DS2024

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs

Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz

In the restricted shortest paths problem, we are given a graph $G$ whose edges are assigned two non-negative weights: lengths and delays, a source $s$ , and a delay threshold $D$ . T…

math.CO2024

Palette Sparsification via FKNP

Vikrant Ashvinkumar, Charles Kenney

A random set $S$ is $p$ -spread if, for all sets $T$ , $P (S \supseteq T) \leq p^{∣ T ∣} .$ There is a constant $C > 1$ large enough that for every graph $G$ with maximum degree…

cs.DS2024

Low Sensitivity Hopsets

Vikrant Ashvinkumar, Aaron Bernstein, Chengyuan Deng +2

Given a weighted graph $G$ , a $(β, ε)$ -hopset $H$ is an edge set such that for any $s, t \in V (G)$ , where $s$ can reach $t$ in $G$ , there is a path from $s$ to $t$ in $G \c…