اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn k-Column Sparse Packing Programs
112
0
0.0
(
0
)
نشر من قبل
Viswanath Nagarajan
تاريخ النشر
2009
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We consider the class of packing integer programs (PIPs) that are column sparse, i.e. 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 on recent results of $k^2cdot 2^k$ and $O(k^2)$. We also show that the integrality gap of our linear programming relaxation is at least 2k-1; it is known that k-column sparse PIPs are $Omega(k/ log k)$-hard to approximate. We also extend our result (at the loss of a small constant factor) to the more general case of maximizing a submodular objective over k-column sparse packing constraints.
قيم البحث
اقرأ أيضاً
We give an approximation algorithm for packing and covering linear programs (linear programs with non-negative coefficients). Given a constraint matrix with n non-zeros, r rows, and c columns, the algorithm computes feasible primal and dual solutions
whose costs are within a factor of 1+eps of the optimal cost in time O((r+c)log(n)/eps^2 + n).
We describe the first nearly linear-time approximation algorithms for explicitly given mixed packing/covering linear programs, and for (non-metric) fractional facility location. We also describe the first parallel algorithms requiring only near-linea
r total work and finishing in polylog time. The algorithms compute $(1+epsilon)$-approximate solutions in time (and work) $O^*(N/epsilon^2)$, where $N$ is the number of non-zeros in the constraint matrix. For facility location, $N$ is the number of eligible client/facility pairs.
We study algorithms based on local improvements for the $k$-Set Packing problem. The well-known local improvement algorithm by Hurkens and Schrijver has been improved by Sviridenko and Ward from $frac{k}{2}+epsilon$ to $frac{k+2}{3}$, and by Cygan to
$frac{k+1}{3}+epsilon$ for any $epsilon>0$. In this paper, we achieve the approximation ratio $frac{k+1}{3}+epsilon$ for the $k$-Set Packing problem using a simple polynomial-time algorithm based on the method by Sviridenko and Ward. With the same approximation guarantee, our algorithm runs in time singly exponential in $frac{1}{epsilon^2}$, while the running time of Cygans algorithm is doubly exponential in $frac{1}{epsilon}$. On the other hand, we construct an instance with locality gap $frac{k+1}{3}$ for any algorithm using local improvements of size $O(n^{1/5})$, here $n$ is the total number of sets. Thus, our approximation guarantee is optimal with respect to results achievable by algorithms based on local improvements.
We present a packing-based approximation algorithm for the $k$-Set Cover problem. We introduce a new local search-based $k$-set packing heuristic, and call it Restricted $k$-Set Packing. We analyze its tight approximation ratio via a complicated comb
inatorial argument. Equipped with the Restricted $k$-Set Packing algorithm, our $k$-Set Cover algorithm is composed of the $k$-Set Packing heuristic cite{schrijver} for $kgeq 7$, Restricted $k$-Set Packing for $k=6,5,4$ and the semi-local $(2,1)$-improvement cite{furer} for 3-Set Cover. We show that our algorithm obtains a tight approximation ratio of $H_k-0.6402+Theta(frac{1}{k})$, where $H_k$ is the $k$-th harmonic number. For small $k$, our results are 1.8667 for $k=6$, 1.7333 for $k=5$ and 1.5208 for $k=4$. Our algorithm improves the currently best approximation ratio for the $k$-Set Cover problem of any $kgeq 4$.
Edge connectivity of a graph is one of the most fundamental graph-theoretic concepts. The celebrated tree packing theorem of Tutte and Nash-Williams from 1961 states that every $k$-edge connected graph $G$ contains a collection $cal{T}$ of $lfloor k/
2 rfloor$ edge-disjoint spanning trees, that we refer to as a tree packing; the diameter of the tree packing $cal{T}$ is the largest diameter of any tree in $cal{T}$. A desirable property of a tree packing, that is both sufficient and necessary for leveraging the high connectivity of a graph in distributed communication, is that its diameter is low. Yet, despite extensive research in this area, it is still unclear how to compute a tree packing, whose diameter is sublinear in $|V(G)|$, in a low-diameter graph $G$, or alternatively how to show that such a packing does not exist. In this paper we provide first non-trivial upper and lower bounds on the diameter of tree packing. First, we show that, for every $k$-edge connected $n$-vertex graph $G$ of diameter $D$, there is a tree packing $cal{T}$ of size $Omega(k)$, diameter $O((101klog n)^D)$, that causes edge-congestion at most $2$. Second, we show that for every $k$-edge connected $n$-vertex graph $G$ of diameter $D$, the diameter of $G[p]$ is $O(k^{D(D+1)/2})$ with high probability, where $G[p]$ is obtained by sampling each edge of $G$ independently with probability $p=Theta(log n/k)$. This provides a packing of $Omega(k/log n)$ edge-disjoint trees of diameter at most $O(k^{(D(D+1)/2)})$ each. We then prove that these two results are nearly tight. Lastly, we show that if every pair of vertices in a graph has $k$ edge-disjoint paths of length at most $D$ connecting them, then there is a tree packing of size $k$, diameter $O(Dlog n)$, causing edge-congestion $O(log n)$. We also provide several applications of low-diameter tree packing in distributed computation.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
