Showing 2019Show all
3 papers · 1 filter
cs.DC2019
Improved Distributed Approximations for Maximum Independent Set
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild +1
We present improved results for approximating maximum-weight independent set ($\MaxIS$) in the CONGEST and LOCAL models of distributed computing. Given an input graph, let and…
cs.DS2019
Network design for s-t effective resistance
Pak Hay Chan, Lap Chi Lau, Aaron Schild +2
We consider a new problem of designing a network with small - effective resistance. In this problem, we are given an undirected graph , two designated vertices $s,t…
cs.DS2019
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
Amariah Becker, Philip N. Klein, Aaron Schild
The Capacitated Vehicle Routing problem is to find a minimum-cost set of tours that collectively cover clients in a graph, such that each tour starts and ends at a specified depot…