2 citations · 2 across the 1 of their papers we have counts for
6 papers · 1 filter
Redistricting Algorithms
Amariah Becker, Justin Solomon
Why not have a computer just draw a map? This is something you hear a lot when people talk about gerrymandering, and it's easy to think at first that this could solve redistricting…
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…
A Framework for Vehicle Routing Approximation Schemes in Trees
Amariah Becker, Alice Paul
We develop a general framework for designing polynomial-time approximation schemes (PTASs) for various vehicle routing problems in trees. In these problems, the goal is to optimall…
A Tight 4/3 Approximation for Capacitated Vehicle Routing in Trees
Amariah Becker
Given a set of clients with demands, the Capacitated Vehicle Routing problem is to find a set of tours that collectively cover all client demand, such that the capacity of each veh…
Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Graphs with Bounded Highway Dimension
Amariah Becker, Philip N. Klein, David Saulpic
The concept of bounded highway dimension was developed to capture observed properties of the metrics of road networks. We show that a graph with bounded highway dimension, for any…
Capacitated Dominating Set on Planar Graphs
Amariah Becker
Capacitated Domination generalizes the classic Dominating Set problem by specifying for each vertex a required demand and an available capacity for covering demand in its closed ne…