We consider approximation algorithms for packing integer programs (PIPs) of the form @math where @math , @math , and @math are nonnegative. We let @math denote the width of @math which is at least @math . Previous work by bansal-sparse obtained an @math -approximation ratio where @math is the maximum number of nonzeroes in any column of @math (in other words the @math -column sparsity of @math ). They raised the question of obtaining approximation ratios based on the @math -column sparsity of @math (denoted by @math ) which can be much smaller than @math . Motivated by recent work on covering integer programs (CIPs) cq,chs-16 we show that simple algorithms based on randomized rounding followed by alteration, similar to those of bansal-sparse (but with a twist), yield approximation ratios for PIPs based on @math . First, following an integrality gap example from bansal-sparse , we observe that the case of @math is as hard as maximum independent set even when @math . In sharp contrast to this negative result, as soon as width is strictly larger than one, we obtain positive results via the natural LP relaxation. For PIPs with width @math where @math , we obtain an @math -approximation. In the large width regime, when @math , we obtain an @math -approximation. We also obtain a @math -approximation when @math .
Approximation algorithms for PIPs in their general form were considered initially by Raghavan and Thompson @cite_8 and refined substantially by Srinivasan @cite_12 . Srinivasan obtained approximation ratios of the form @math when @math had entries from @math , and a ratio of the form @math when @math had entries from @math . Pritchard @cite_2 was the first to obtain a bound for PIPs based solely on the column sparsity parameter @math . He used iterated rounding and his initial bound was improved in @cite_5 to @math . The current state of the art is due to Bansal al @cite_17 . Previously we ignored constant factors when describing the ratio. In fact @cite_17 obtains a ratio of @math by strengthening the basic LP relaxation.
@cite_8 @cite_2 @cite_5 @cite_12 @cite_17
782508147 1982492546 1977980414 2963986064
We give new approximation algorithms for packing integer programs (PIPs) by employing the method of randomized rounding combined with alterations. Our first result is a simpler approximation algorithm for general PIPs which matches the best known bounds, and which admits an efficient parallel implementation. We also extend these results to a multi-criteria version of PIPs. Our second result is for the class of packing integer programs (PIPs) that are column sparse, i. e., where there is a specified upper bound k on the number of constraints that each variable appears in. We give an (ek+ o(k))-approximation algorithm for k-column sparse PIPs, improving over previously known O(k 2 )-approximation ratios. We also generalize our result to the case of maximizing non-negative monotone submodular functions over k-column sparse packing constraints, and obtain an e 2k This paper deals with the design of efficiently computable incentive compatible, or truthful, mechanisms for combinatorial optimization problems with multi-parameter agents. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques.Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone FPTAS. This can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multi-unit auctions. The best previous result for such auctions was a 2-approximation. In addition, we present a monotone PTAS for the generalized assignment problem with any bounded number of parameters per agent.The most efficient way to solve packing integer programs (PIPs) is LP-based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs), unsplittable flow routing and multicast routing. Our approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle. This paper deals with the design of efficiently computable incentive-compatible mechanisms for combinatorial optimization problems with single-minded agents each possibly having multiple private parameters. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques. Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone fully polynomial time approximation scheme (FPTAS). This can be applied to various problems like, e.g., knapsack, constrained shortest path, or job scheduling with deadlines. For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multiunit auctions. The best previous result for such auctions was a 2-appro-xi-ma-tion. In addition, we present a monotone PTAS for the generalized assignment problem with any constant number of private parameters per agent. The most efficient way to solve packing integer programs (PIPs) is linear programming-based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs), unsplittable flow routing, and multicast routing. Our primal-dual approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle. We consider positive covering integer programs, which generalize set cover and which have attracted a long line of research developing (randomized) approximation algorithms. Srinivasan (2006) gave a rounding algorithm based on the FKG inequality for systems which are "column-sparse." This algorithm may return an integer solution in which the variables get assigned large (integral) values; Kolliopoulos & Young (2005) modified this algorithm to limit the solution size, at the cost of a worse approximation ratio. We develop a new rounding scheme based on the Partial Resampling variant of the Lovasz Local Lemma developed by Harris & Srinivasan (2013). This achieves an approximation ratio of 1 + ln([EQUATION]), where amin is the minimum covering constraint and Δ1 is the maximum e1-norm of any column of the covering matrix (whose entries are scaled to lie in [0, 1]); we also show nearly-matching inapproximability and integrality-gap lower bounds. Our approach improves asymptotically, in several different ways, over known results. First, it replaces Δ0, the maximum number of nonzeroes in any column (from the result of Srinivasan) by Δ1 which is always - and can be much - smaller than Δ0; this is the first such result in this context. Second, our algorithm automatically handles multi-criteria programs; we achieve improved approximation ratios compared to the algorithm of Srinivasan, and give, for the first time when the number of objective functions is large, polynomial-time algorithms with good multi-criteria approximations. We also significantly improve upon the upper-bounds of Kolliopoulos & Young when the integer variables are required to be within (1 + e) of some given upper-bounds, and show nearly-matching inapproximability.