Space debris is a growing concern for the sustained operation of our satellites. The population in space is continually increasing, both on a gradual basis as new satellites are placed on orbit and in sudden bursts, as evidenced with the recent collision between the Iridium and inactive Cosmos spacecraft. The problem is most severe in densely populated orbit regimes, where many operational satellites face a sustained presence of close-orbiting objects. In general, the frequent occurrence of potential collisions with debris will have a negative impact on mission performance in two important ways. First, repeated avoidance maneuvers diminish fuel and thus reduce mission life. Second, excursions from the nominal orbit during avoidance maneuvers may violate mission requirements or payload constraints. It is therefore important to consider both fuel minimization and station-keeping objectives in the avoidance planning problem. In this paper, we formulate the avoidance maneuver planning problem as a linear program. Avoidance constraints and orbit station-keeping constraints are expressed as linear functions of the control input. The relative orbit dynamics are modeled as a discrete, linear time-varying system that models both circular and eccentric orbits. The original nonlinear, nonconvex avoidance constraints are transformed into a time-varying sequence of linear constraints, and the navigation uncertainty is applied in a worst-case sense. Finally, the minimum-fuel avoidance maneuver problem is formulated with station-keeping constraints in a way that enables automatic relaxation of certain constraints to ensure feasibility.