Search

We consider a feature-based personalized pricing problem in which the buyer is strategic: given the seller's pricing policy, the buyer can augment the features that they reveal to the seller to obtain a low price for the product. We model the seller's pricing problem as a stochastic program over an infinite-dimensional space of pricing policies where the radii by which the buyer can perturb the features are strictly positive. We establish that the sample average approximation of this problem is asymptotically consistent; that is, we prove that the objective value of the sample average approximation converges almost surely to the objective value of the stochastic problem as the number of samples tends to infinity under mild technical assumptions. This consistency guarantee thus shows that incorporating strategic consumer behavior into a data-driven pricing problem can, in addition to making the pricing problem more realistic, also help prevent overfitting.

Incorporating energy storage systems (ESS) into power systems has been studied in many recent works, where binary variables are often introduced to model the complementary nature of battery charging and discharging. A conventional approach for these ESS optimization problems is to relax binary variables and convert the problem into a linear program. However, such linear programming relaxation models can yield unrealistic fractional solutions, such as simultaneous charging and discharging. In this paper, we develop a regularized Mixed-Integer Programming (MIP) model for the ESS optimal power flow (OPF) problem. We prove that under mild conditions, the proposed regularized model admits a zero integrality gap with its linear programming relaxation; hence, it can be solved efficiently. By studying the properties of the regularized MIP model, we show that its optimal solution is also near-optimal to the original ESS OPF problem, thereby providing a valid and tight upper bound for the ESS OPF problem. The use of the regularized MIP model allows us to solve two intractable problems: a two-stage stochastic ESS OPF problem and a trilevel network contingency problem.

A traditional stochastic program under a finite population typically seeks to optimize efficiency by maximizing the expected profits or minimizing the expected costs, subject to a set of constraints. However, implementing such optimization-based decisions can have varying impacts on individuals, and when assessed using the individuals' utility functions, these impacts may differ substantially across demographic groups delineated by sensitive attributes, such as gender, race, age, and socioeconomic status. As each group comprises multiple individuals, a common remedy is to enforce group fairness, which necessitates the measurement of disparities in the distributions of utilities across different groups. This paper introduces the concept of Distributionally Fair Stochastic Optimization (DFSO) based on the Wasserstein fairness measure. The DFSO aims to minimize distributional disparities among groups, quantified by the Wasserstein distance, while adhering to an acceptable level of inefficiency. Our analysis reveals that: (i) the Wasserstein fairness measure recovers the demographic parity fairness prevalent in binary classification literature; (ii) this measure can approximate the well-known Kolmogorov-Smirnov fairness measure with considerable accuracy; and (iii) despite DFSO's biconvex nature, the epigraph of the Wasserstein fairness measure is generally Mixed-Integer Convex Programming Representable (MICP-R). Additionally, we introduce two distinct lower bounds for the Wasserstein fairness measure: the Jensen bound, applicable to the general Wasserstein fairness measure, and the Gelbrich bound, specific to the type-2 Wasserstein fairness measure. We establish the exactness of the Gelbrich bound and quantify the theoretical difference between the Wasserstein fairness measure and the Gelbrich bound., Comment: No more revision

Distributionally Favorable Optimization (DFO) is an important framework for decision-making under uncertainty, with applications across fields such as reinforcement learning, online learning, robust statistics, chance-constrained programming, and two-stage stochastic optimization without relatively complete recourse. In contrast to the traditional Distributionally Robust Optimization (DRO) paradigm, DFO presents a unique challenge -- the application of the inner infimum operator often fails to retain the convexity. In light of this challenge, we study the tractability and complexity of DFO. We establish sufficient and necessary conditions for determining when DFO problems are tractable or intractable. Despite the typical nonconvex nature of DFO problems, our findings show that they are mixed-integer convex programming representable (MICP-R), thereby enabling solutions via standard optimization solvers. Finally, we numerically validate the efficacy of our MICP-R formulations.

The classical Canonical Correlation Analysis (CCA) identifies the correlations between two sets of multivariate variables based on their covariance, which has been widely applied in diverse fields such as computer vision, natural language processing, and speech analysis. Despite its popularity, CCA can encounter challenges in explaining correlations between two variable sets within high-dimensional data contexts. Thus, this paper studies Sparse Canonical Correlation Analysis (SCCA) that enhances the interpretability of CCA. We first show that SCCA generalizes three well-known sparse optimization problems, sparse PCA, sparse SVD, and sparse regression, which are all classified as NP-hard problems. This result motivates us to develop strong formulations and efficient algorithms. Our main contributions include (i) the introduction of a combinatorial formulation that captures the essence of SCCA and allows the development of approximation algorithms; (ii) the derivation of an equivalent mixed-integer semidefinite programming model that facilitates a specialized branch-and-cut algorithm with analytical cuts; and (iii) the establishment of the complexity results for two low-rank special cases of SCCA. The effectiveness of our proposed formulations and algorithms is validated through numerical experiments.

We consider the problem of learning fair policies for multi-stage selection problems from observational data. This problem arises in several high-stakes domains such as company hiring, loan approval, or bail decisions where outcomes (e.g., career success, loan repayment, recidivism) are only observed for those selected. We propose a multi-stage framework that can be augmented with various fairness constraints, such as demographic parity or equal opportunity. This problem is a highly intractable infinite chance-constrained program involving the unknown joint distribution of covariates and outcomes. Motivated by the potential impact of selection decisions on people's lives and livelihoods, we propose to focus on interpretable linear selection rules. Leveraging tools from causal inference and sample average approximation, we obtain an asymptotically consistent solution to this selection problem by solving a mixed binary conic optimization problem, which can be solved using standard off-the-shelf solvers. We conduct extensive computational experiments on a variety of datasets adapted from the UCI repository on which we show that our proposed approaches can achieve an 11.6% improvement in precision and a 38% reduction in the measure of unfairness compared to the existing selection policy., Comment: 38th Annual AAAI Conference on Artificial Intelligence, 2024

A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective subject to multiple two-sided linear matrix inequalities intersected with a low-rank and spectral constrained domain set. Although solving LSOP is, in general, NP-hard, its partial convexification (i.e., replacing the domain set by its convex hull) termed "LSOP-R," is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of the feasible set of LSOP-R and prove their tightness for the domain sets with different matrix spaces. The proposed rank bounds recover two well-known results in the literature from a fresh angle and also allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to the original LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle, coupled with a rank-reduction algorithm, which ensures the output solution satisfies the theoretical rank bound. Finally, we numerically verify the strength of the LSOP-R and the efficacy of the proposed algorithms.

This paper studies distributionally robust chance constrained programs (DRCCPs), where the uncertain constraints must be satisfied with at least a probability of a prespecified threshold for all probability distributions from the Wasserstein ambiguity set. As DRCCPs are often nonconvex and challenging to solve optimally, researchers have been developing various convex inner approximations. Recently, ALSO-X has been proven to outperform the conditional value-at-risk (CVaR) approximation of a regular chance constrained program when the deterministic set is convex. In this work, we relax this assumption by introducing a new ALSO-X\# method for solving DRCCPs. Namely, in the bilevel reformulations of ALSO-X and CVaR approximation, we observe that the lower-level ALSO-X is a special case of the lower-level CVaR approximation and the upper-level CVaR approximation is more restricted than the one in ALSO-X. This observation motivates us to propose the ALSO-X\#, which still resembles a bilevel formulation -- in the lower-level problem, we adopt the more general CVaR approximation, and for the upper-level one, we choose the less restricted ALSO-X. We show that ALSO-X\# can always be better than the CVaR approximation and can outperform ALSO-X under regular chance constrained programs and type $\infty-$Wasserstein ambiguity set. We also provide new sufficient conditions under which ALSO-X\# outputs an optimal solution to a DRCCP. We apply the proposed ALSO-X\# to a wireless communication problem and numerically demonstrate that the solution quality can be even better than the exact method.

In the rank-constrained optimization problem (RCOP), it minimizes a linear objective function over a prespecified closed rank-constrained domain set and $m$ generic two-sided linear matrix inequalities. Motivated by the Dantzig-Wolfe (DW) decomposition, a popular approach of solving many nonconvex optimization problems, we investigate the strength of DW relaxation (DWR) of the RCOP, which admits the same formulation as RCOP except replacing the domain set by its closed convex hull. Notably, our goal is to characterize conditions under which the DWR matches RCOP for any m two-sided linear matrix inequalities. From the primal perspective, we develop the first-known simultaneously necessary and sufficient conditions that achieve: (i) extreme point exactness -- all the extreme points of the DWR feasible set belong to that of the RCOP; (ii) convex hull exactness -- the DWR feasible set is identical to the closed convex hull of RCOP feasible set; and (iii) objective exactness -- the optimal values of the DWR and RCOP coincide. The proposed conditions unify, refine, and extend the existing exactness results in the quadratically constrained quadratic program (QCQP) and fair unsupervised learning. These conditions can be very useful to identify new results, including the extreme point exactness for a QCQP problem that admits an inhomogeneous objective function with two homogeneous two-sided quadratic constraints and the convex hull exactness for fair SVD.

In this paper, we study the mixed-integer nonlinear set given by a separable quadratic constraint on continuous variables, where each continuous variable is controlled by an additional indicator. This set occurs pervasively in optimization problems with uncertainty and in machine learning. We show that optimization over this set is NP-hard. Despite this negative result, we characterize the structure of the convex hull, and show that it can be formally studied using polyhedral theory. Moreover, we show that although perspective relaxation in the literature for this set fails to match the structure of its convex hull, it is guaranteed to be a close approximation.

We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P $=$ NP. Therefore, to solve the DDF problem effectively, we propose two convex integer-programming formulations and investigate their corresponding complementary and Lagrangian-dual problems. We also develop scalable randomized-sampling and local-search algorithms with provable performance guarantees. Leveraging the concavity of the objective functions in the two proposed formulations, we design an exact algorithm, aimed at solving the DDF problem to optimality. We further derive a family of submodular valid inequalities and optimality cuts, which can significantly enhance the algorithm performance. Finally, we test our algorithms using real-world data on the new phasor-measurement-units placement problem for modern power grids, considering the existing conventional sensors. Our numerical study demonstrates the efficiency of our exact algorithm and the scalability and high-quality outputs of our approximation algorithms.

The objective of this study is to address the problem of background/foreground separation with missing pixels by combining the video acquisition, video recovery, background/foreground separation into a single framework. To achieve this, a smooth robust tensor completion (SRTC) model is proposed to recover the data and decompose it into the static background and smooth foreground, respectively. Specifically, the static background is modeled by the low-rank tucker decomposition and the smooth foreground (moving objects) is modeled by the spatiotemporal continuity, which is enforced by the total variation regularization. An efficient algorithm based on tensor proximal alternating minimization (tenPAM) is implemented to solve the proposed model with global convergence guarantee under very mild conditions. Extensive experiments on real data demonstrate that the proposed method significantly outperforms the state-of-the-art approaches for background/foreground separation with missing pixels., Comment: 40 pages, 11 figures

Exponents and logarithms are fundamental components in many important applications such as logistic regression, maximum likelihood, relative entropy, and so on. Since the exponential cone can be viewed as the epigraph of perspective of the natural exponential function or the hypograph of perspective of the natural logarithm function, many mixed-integer convex programs involving exponential or logarithm functions can be recast as mixed-integer exponential conic programs (MIECPs). However, unlike mixed-integer linear programs (MILPs) and mixed-integer second-order conic programs (MISOCPs), MIECPs are still under development. To harvest the past efforts on MILPs and MISOCPs, this paper presents second-order conic (SOC) and polyhedral approximation schemes for the exponential cone with application to MIECPs. To do so, we first extend and generalize existing SOC approximation approaches in the extended space, propose new scaling and shifting methods, prove approximation accuracies, and derive lower bounds of approximations. We then study the polyhedral outer approximation of the exponential cones in the original space using gradient inequalities, show its approximation accuracy, and derive a lower bound of the approximation. When implementing SOC approximations, we suggest learning the approximation pattern by testing smaller cases and then applying it to the large-scale ones; and for the polyhedral approximation, we suggest using the branch and cut method for MIECPs. Our numerical study shows that the proposed methods show speed-ups over solver MOSEK for MIECPs, and the scaling, shifting, and polyhedral outer approximation methods work very well., Comment: 37 pages, 9 figures

Truncated singular value decomposition (SVD), also known as the best low-rank matrix approximation, has been successfully applied to many domains such as biology, healthcare, and others, where high-dimensional datasets are prevalent. To enhance the interpretability of the truncated SVD, sparse SVD (SSVD) is introduced to select a few rows and columns of the original matrix along with the low rank approximation. Different from the literature, this paper presents a novel SSVD formulation that can select the best submatrix precisely up to a given size to maximize its truncated Ky Fan norm. The fact that the SSVD problem is NP-hard motivates us to study effective algorithms with provable performance guarantees. To do so, we first reformulate SSVD as a mixed-integer semidefinite program, which can be solved exactly for small- or medium-sized instances by a customized branch and cut algorithm with closed-form cuts, and is extremely useful to evaluate the quality of approximation algorithms. We next develop three selection algorithms based on different selection criteria and two searching algorithms -- greedy and local search. We prove the approximation ratios for all the approximation algorithms and show that all the ratios are tight, i.e., we demonstrate that these approximation ratios are unimprovable. Finally, our numerical study demonstrates the high solution quality and computational efficiency of the proposed algorithms.

As an important problem in modern data analytics, classification has witnessed varieties of applications from different domains. Different from conventional classification approaches, fair classification concerns the issues of unintentional biases against the sensitive features (e.g., gender, race). Due to high nonconvexity of fairness measures, existing methods are often unable to model exact fairness, which can cause inferior fair classification outcomes. This paper fills the gap by developing a novel unified framework to jointly optimize accuracy and fairness. The proposed framework is versatile and can incorporate different fairness measures studied in literature precisely as well as can be applicable to many classifiers including deep classification models. Specifically, in this paper, we first prove Fisher consistency of the proposed framework. We then show that many classification models within this framework can be recast as mixed-integer convex programs, which can be solved effectively by off-the-shelf solvers when the instance sizes are moderate and can be used as benchmarks to compare the efficiency of approximation algorithms. We prove that in the proposed framework, when the classification outcomes are known, the resulting problem, termed "unbiased subdata selection," is strongly polynomial-solvable and can be used to enhance the classification fairness by selecting more representative data points. This motivates us to develop an iterative refining strategy (IRS) to solve the large-scale instances, where we improve the classification accuracy and conduct the unbiased subdata selection in an alternating fashion. We study the convergence property of IRS and derive its approximation bound. More broadly, this framework can be leveraged to improve classification models with unbalanced data by taking F1 score into consideration., Comment: 42 pages, 4 Figures

In a chance constrained program (CCP), the decision-makers aim to seek the best decision whose probability of violating the uncertainty constraints is within the prespecified risk level. As a CCP is often nonconvex and is difficult to solve to optimality, much effort has been devoted to developing convex inner approximations for a CCP, among which the conditional value-at-risk (CVaR) has been known to be the best for more than a decade. This paper studies and generalizes the ALSO-X, originally proposed by Ahmed, Luedtke, SOng, and Xie (2017), for solving a CCP. We first show that the ALSO-X resembles a bilevel optimization, where the upper-level problem is to find the best objective function value and enforce the feasibility of a CCP for a given decision from the lower-level problem, and the lower-level problem is to minimize the expectation of constraint violations subject to the upper bound of the objective function value provided by the upper-level problem. This interpretation motivates us to prove that when uncertain constraints are convex in the decision variables, ALSO-X always outperforms the CVaR approximation. We further show (i) sufficient conditions under which ALSO-X can recover an optimal solution to a CCP; (ii) an equivalent bilinear programming formulation of a CCP, inspiring us to enhance ALSO-X with a convergent alternating minimization method (ALSO-X+); (iii) extensions of ALSO-X and ALSO-X+ to solve distributionally robust chance constrained programs (DRCCPs) under $\infty$-Wasserstein ambiguity set. Our numerical study demonstrates the effectiveness of the proposed methods., Comment: 60 pages, 3 figures

Sparse PCA (SPCA) is a fundamental model in machine learning and data analytics, which has witnessed a variety of application areas such as finance, manufacturing, biology, healthcare. To select a prespecified-size principal submatrix from a covariance matrix to maximize its largest eigenvalue for the better interpretability purpose, SPCA advances the conventional PCA with both feature selection and dimensionality reduction. This paper proposes two exact mixed-integer SDPs (MISDPs) by exploiting the spectral decomposition of the covariance matrix and the properties of the largest eigenvalues. We then analyze the theoretical optimality gaps of their continuous relaxation values and prove that they are stronger than that of the state-of-art one. We further show that the continuous relaxations of two MISDPs can be recast as saddle point problems without involving semi-definite cones, and thus can be effectively solved by first-order methods such as the subgradient method. Since off-the-shelf solvers, in general, have difficulty in solving MISDPs, we approximate SPCA with arbitrary accuracy by a mixed-integer linear program (MILP) of a similar size as MISDPs. To be more scalable, we also analyze greedy and local search algorithms, prove their first-known approximation ratios, and show that the approximation ratios are tight. Our numerical study demonstrates that the continuous relaxation values of the proposed MISDPs are quite close to optimality, the proposed MILP model can solve small and medium-size instances to optimality, and the approximation algorithms work very well for all the instances. Finally, we extend the analyses to Rank-one Sparse SVD (R1-SSVD) with non-symmetric matrices and Sparse Fair PCA (SFPCA) when there are multiple covariance matrices, each corresponding to a protected group., Comment: 49 pages, 1 figure

This paper studies data-driven distributionally robust bottleneck combinatorial problems (DRBCP) with stochastic costs, where the probability distribution of the cost vector is contained in a ball of distributions centered at the empirical distribution specified by the Wasserstein distance. We study two distinct versions of DRBCP from different applications: (i) Motivated by the multi-hop wireless network application, we first study the uncertainty quantification of DRBCP (denoted by DRBCP-U), where decision-makers would like to have an accurate estimation of the worst-case value of DRBCP. The difficulty of DRBCP-U is to handle its max-min-max form. Fortunately, the alternative forms of the bottleneck combinatorial problems from their blockers allow us to derive equivalent deterministic reformulations, which can be computed via mixed-integer programs. In addition, by drawing the connection between DRBCP-U and its sampling average approximation counterpart under empirical distribution, we show that the Wasserstein radius can be chosen in the order of negative square root of sample size, improving the existing known results; and (ii) Next, motivated by the ride-sharing application, decision-makers choose the best service-and-passenger matching that minimizes the unfairness. This gives rise to the decision-making DRBCP (denoted by DRBCP-D). For DRBCP-D, we show that its optimal solution is also optimal to its sampling average approximation counterpart, and the Wasserstein radius can be chosen in a similar order as DRBCP-U. When the sample size is small, we propose to use the optimal value of DRBCP-D to construct an indifferent solution space and propose an alternative decision-robust model, which finds the best indifferent solution to minimize the empirical variance. We further show that the decision robust model can be recast as a mixed-integer program., Comment: 32 pages, 4 figures

This paper studies a classic maximum entropy sampling problem (MESP), which aims to select the most informative principal submatrix of a prespecified size from a covariance matrix. MESP has been widely applied to many areas, including healthcare, power system, manufacturing and data science. By investigating its Lagrangian dual and primal characterization, we derive a novel convex integer program for MESP and show that its continuous relaxation yields a near-optimal solution. The results motivate us to study an efficient sampling algorithm and develop its approximation bound for MESP, which improves the best-known bound in literature. We then provide an efficient deterministic implementation of the sampling algorithm with the same approximation bound. By developing new mathematical tools for the singular matrices and analyzing the Lagrangian dual of the proposed convex integer program, we investigate the widely-used local search algorithm and prove its first-known approximation bound for MESP. The proof techniques further inspire us with an efficient implementation of the local search algorithm. Our numerical experiments demonstrate that these approximation algorithms can efficiently solve medium-sized and large-scale instances to near-optimality. Our proposed algorithms are coded and released as open-source software. Finally, we extend the analyses to the A-Optimal MESP (A-MESP), where the objective is to minimize the trace of the inverse of the selected principal submatrix., Comment: 62 pages

In the optimization under uncertainty, decision-makers first select a wait-and-see policy before any realization of uncertainty and then place a here-and-now decision after the uncertainty has been observed. Two-stage stochastic programming is a popular modeling paradigm for the optimization under uncertainty that the decision-makers first specifies a probability distribution, and then seek the best decisions to jointly optimize the deterministic wait-and-see and expected here-and-now costs. In practice, such a probability distribution may not be fully available but is probably observable through an empirical dataset. Therefore, this paper studies distributionally robust two-stage stochastic program (DRTSP) which jointly optimizes the deterministic wait-and-see and worst-case expected here-and-now costs, and the probability distribution comes from a family of distributions which are centered at the empirical distribution using $\infty-$Wasserstein metric. There have been successful developments on deriving tractable approximations of the worst-case expected here-and-now cost in DRTSP. Unfortunately, limited results on exact tractable reformulations of DRTSP. This paper fills this gap by providing sufficient conditions under which the worst-case expected here-and-now cost in DRTSP can be efficiently computed via a tractable convex program. By exploring the properties of binary variables, the developed reformulation techniques are extended to DRTSP with binary random parameters. The main tractable reformulations in this paper are projected into the original decision space and thus can be interpreted as conventional two-stage stochastic programs under discrete support with extra penalty terms enforcing the robustness. These tractable results are further demonstrated to be sharp through complexity analysis., Comment: 31 pages

This paper studies a distributionally robust chance constrained program (DRCCP) with Wasserstein ambiguity set, where the uncertain constraints should be satisfied with a probability at least a given threshold for all the probability distributions of the uncertain parameters within a chosen Wasserstein distance from an empirical distribution. In this work, we investigate equivalent reformulations and approximations of such problems. We first show that a DRCCP can be reformulated as a conditional value-at-risk constrained optimization problem, and thus admits tight inner and outer approximations. We also show that a DRCCP of bounded feasible region is mixed integer representable by introducing big-M coefficients and additional binary variables. For a DRCCP with pure binary decision variables, by exploring the submodular structure, we show that it admits a big-M free formulation, which can be solved by a branch and cut algorithm. Finally, we present a numerical study to illustrate the effectiveness of the proposed formulations., Comment: 32 pages, 2 figures

Sparse regression and variable selection for large-scale data have been rapidly developed in the past decades. This work focuses on sparse ridge regression, which enforces the sparsity by use of the L0 norm. We first prove that the continuous relaxation of the mixed integer second order conic (MISOC) reformulation using perspective formulation is equivalent to that of the convex integer formulation proposed in recent work. We also show that the convex hull of the constraint system of MISOC formulation is equal to its continuous relaxation. Based upon these two formulations (i.e., the MISOC formulation and convex integer formulation), we analyze two scalable algorithms, the greedy and randomized algorithms, for sparse ridge regression with desirable theoretical properties. The proposed algorithms are proved to yield near-optimal solutions under mild conditions. We further propose to integrate the greedy algorithm with the randomized algorithm, which can greedily search the features from the nonzero subset identified by the continuous relaxation of the MISOC formulation. The merits of the proposed methods are illustrated through numerical examples in comparison with several existing ones., Comment: 31 pages

Experimental design is a classical statistics problem and its aim is to estimate an unknown $m$-dimensional vector $\beta$ from linear measurements where a Gaussian noise is introduced in each measurement. For the combinatorial experimental design problem, the goal is to pick $k$ out of the given $n$ experiments so as to make the most accurate estimate of the unknown parameters, denoted as $\hat{\beta}$. In this paper, we will study one of the most robust measures of error estimation - $D$-optimality criterion, which corresponds to minimizing the volume of the confidence ellipsoid for the estimation error $\beta-\hat{\beta}$. The problem gives rise to two natural variants depending on whether repetitions of experiments are allowed or not. We first propose an approximation algorithm with a $\frac1e$-approximation for the $D$-optimal design problem with and without repetitions, giving the first constant factor approximation for the problem. We then analyze another sampling approximation algorithm and prove that it is $(1-\epsilon)$-approximation if $k\geq \frac{4m}{\epsilon}+\frac{12}{\epsilon^2}\log(\frac{1}{\epsilon})$ for any $\epsilon \in (0,1)$. Finally, for $D$-optimal design with repetitions, we study a different algorithm proposed by literature and show that it can improve this asymptotic approximation ratio., Comment: 34 pages, accepted by Mathematics of Operations Research