As the amount of space debris accumulates, and as more future missions involve multiple close-orbiting spacecraft, the risk of collision is becoming a more prominent concern in both mission design and operations. The recent collision between the Iridium and inactive COSMOS spacecraft has shown demonstrated this growing problem, with NORAD already tracking over 200 pieces of new debris in just the first few weeks since the event. Spacecraft with the capability to detect potential collisions, then plan and enact avoidance maneuvers can successfully mitigate this risk. A particular challenge with avoiding space debris is the large degree of uncertainty in the relative state of the objects. In this paper, we present a practical method for the onboard planning of collision avoidance maneuvers. The relative orbit dynamics are modeled as a discrete, linear time-varying system that models both circular and eccentric orbits. Minimum-fuel avoidance maneuvers are planned by using a robust linear programming (LP) technique. The original non-linear, non-convex avoidance constraints are transformed into a time-varying sequence of linear constraints, and the navigation uncertainty is applied in a worst-case sense. The resulting maneuver can be solved efficiently as an LP with no integer constraints, and can guarantee collision avoidance with respect to bounded navigation uncertainty.