BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
A k-connectivity oracle for a graph G=(V,E) is a data structure that given s,t∈V determines whether there are at least k+1 internally disjoint st-paths in G. For undirected graphs, Pettie, Saranurak & Yin [STOC 2022, pp. 151-161] proved that any k-connectivity oracle requires Ω(kn) bits of space. They asked whether Ω(kn) bits are still necessary if G is k-connected. We will show by a very simple proof that this is so even if G is k-connected, answering this open question.
We consider network design problems in which we are given a graph and seek a min-size 2-connected subgraph that satisfies a prescribed property. ∙ In the 1-Connectivity Augmentation problem the goal is to augment a connected graph by a min-size edge subset of a specified edge set such that the augmented graph is 2-connected. We breach the natural ratio of 2 for this problem and also for the more general Crossing Family Cover problem. ∙ In the 2-Connected Dominating Set problem we seek a minimum size 2-connected subgraph that dominates all nodes. We give the first non-trivial approximation algorithm for this problem, with expected ratio O(σlog3n), where σ=O(logn⋅loglogn⋅(logloglogn)3). The unifying technique of both results is a reduction to the Subset Steiner Connected Dominating Set problem. Such a reduction was known for edge-connectivity, and we extend it to 2-node connectivity problems. We show that the same method can be used to obtain easily polylogarithmic approximation ratios that are not too far from the best known ones for several other problems.
In activation network design problems we are given an undirected graph G=(V,E) and a pair of activation costs {ceu,cev} for each e=uv∈E. The goal is to find an edge set F⊆E that satisfies a prescribed property of minimum activation cost $τ(F)=\sum_{v \in V} \max \{c_e^v: e \in F \mbox{ is incident to } v\}$. In the Activation k Disjoint Paths problem we are given s,t∈V and an integer k, and seek an edge set F⊆E of k internally disjoint st-paths of minimum activation cost. The problem admits an easy 2-approximation algorithm. However, it was an open question whether the problem is in P even for k=2 and power activation costs, when ceu=cev for all e=uv∈E. Here we will answer this question by giving a polynomial time algorithm using linear programing. We will also mention several consequences, among them a polynomial time algorithm for the Activation 2 Edge Disjoint Paths problem, and improved approximation ratios for the Min-Power k-Connected Subgraph problem.
A graph G is k-out-connected from its node s if it contains k internally disjoint sv-paths to every node v; G is k-connected if it is k-out-connected from every node. In connectivity augmentation problems the goal is to augment a graph G0=(V,E0) by a minimum costs edge set J such that G0∪J has higher connectivity than G0. In the k-Out-Connectivity Augmentation (k-OCA) problem, G0 is (k−1)-out-connected from s and G0∪J should be k-out-connected from s; in the k-Connectivity Augmentation (k-CA) problem G0 is (k−1)-connected and G0∪J should be k-connected. The parameterized complexity status of these problems was open even for k=3 and unit costs. We will show that k-OCA and 3-CA can be solved in time 9p⋅nO(1), where p is the size of an optimal solution. Our paper is the first that shows fixed parameter tractability of a k-node-connectivity augmentation problem with high values of k. We will also consider the (2,k)-Connectivity Augmentation problem where G0 is (k−1)-edge-connected and G0∪J should be both k-edge-connected and 2-connected. We will show that this problem can be solved in time 9p⋅nO(1), and for unit costs approximated within 1.892.
We consider the problem of maximizing a non-negative monotone submodular function subject to a knapsack constraint, which is also known as the Budgeted Submodular Maximization (BSM) problem. Sviridenko (2004) showed that by guessing 3 appropriate elements of an optimal solution, and then executing a greedy algorithm, one can obtain the optimal approximation ratio of α=1−1/e≈0.632 for BSM. However, the need to guess (by enumeration) 3 elements makes the algorithm of Sviridenko impractical as it leads to a time complexity of O(n5) (which can be slightly improved using the thresholding technique of Badanidiyuru & Vondrak (2014), but only to roughly O(n4)). Our main results in this paper show that fewer guesses suffice. Specifically, by making only 2 guesses, we get the same optimal approximation ratio of α with an improved time complexity of roughly O(n3). Furthermore, by making only a single guess, we get an almost as good approximation ratio of 0.6174>0.9767α in roughly O(n2) time. Prior to our work, the only algorithms that were known to obtain an approximation ratio close to α for BSM were the algorithm of Sviridenko and an algorithm of Ene & Nguyen (2019) that achieves (α−ε)-approximation. However, the algorithm of Ene & Nguyen requires (1/ε)O(1/ε4)nlog2n time, and hence, is of theoretical interest only as (1/ε)O(1/ε4) is huge even for moderate values of ε. In contrast, all the algorithms we analyze are simple and parallelizable, which makes them good candidates for practical use. Recently, Tang et al. (2020) studied a simple greedy algorithm that already has a long research history, and proved that its approximation ratio is at least 0.405. We improve over this result, and show that the approximation ratio of this algorithm is within the range [0.427, 0.462].
In the Tree Augmentation Problem (TAP) the goal is to augment a tree T by a minimum size edge set F from a given edge set E such that T∪F is 2-edge-connected. The best approximation ratio known for TAP is 1.5. In the more general Weighted TAP problem, F should be of minimum weight. Weighted TAP admits several 2-approximation algorithms w.r.t. to the standard cut LP-relaxation, but for all of them the performance ratio of 2 is tight even for TAP. The problem is equivalent to the problem of covering a laminar set family. Laminar set families play an important role in the design of approximation algorithms for connectivity network design problems. In fact, Weighted TAP is the simplest connectivity network design problem for which a ratio better than 2 is not known. Improving this "natural" ratio is a major open problem, which may have implications on many other network design problems. It seems that achieving this goal requires finding an LP-relaxation with integrality gap better than 2, which is a long time open problem even for TAP. In this paper we introduce such an LP-relaxation and give an algorithm that computes a feasible solution for TAP of size at most 1.75 times the optimal LP value. This gives some hope to break the ratio 2 for the weighted case. Our algorithm computes some initial edge set by solving a partial system of constraints that form the integral edge-cover polytope, and then applies local search on 3-leaf subtrees to exchange some of the edges and to add additional edges. Thus we do not need to solve the LP, and the algorithm runs roughly in time required to find a minimum weight edge-cover in a general graph.
The Tree Augmentation Problem (TAP) is: given a connected graph G=(V,E) and an edge set E on V find a minimum size subset of edges F⊆E such that (V,E∪F) is 2-edge-connected. In the conference version \cite{EFKN-APPROX} was sketched a 1.5-approximation algorithm for the problem. Since a full proof was very complex and long, the journal version was cut into two parts. In the first part \cite{EFKN-TALG} was only proved ratio 1.8. An attempt to simplify the second part produced an error in \cite{EKN-IPL}. Here we give a correct, different, and self contained proof of the ratio 1.5, that is also substantially simpler and shorter than the previous proofs.
We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iterative rounding algorithm of the biset LP relaxation for this problem. For directed graphs and k-out-connectivity requirements from a root, our algorithm computes a solution that is a 2-approximation on the cost, and the degree of each node v in the solution is at most 2b(v)+O(k) where b(v) is the degree upper bound on v. For undirected graphs and element-connectivity requirements with maximum connectivity requirement k, our algorithm computes a solution that is a 4-approximation on the cost, and the degree of each node v in the solution is at most 4b(v)+O(k). These ratios improve the previous O(logk)-approximation on the cost and O(2kb(v)) approximation on the degrees. Our algorithms can be used to improve approximation ratios for other node-connectivity problems such as undirected k-out-connectivity, directed and undirected k-connectivity, and undirected rooted k-connectivity and subset k-connectivity.
In Source Location (SL) problems the goal is to select a mini-mum cost source set S⊆V such that the connectivity (or flow) ψ(S,v) from S to any node v is at least the demand dv of v. In many SL problems ψ(S,v)=dv if v∈S, namely, the demand of nodes selected to S is completely satisfied. In a node-connectivity variant suggested recently by Fukunaga, every node v gets a "bonus" pv≤dv if it is selected to S. Fukunaga showed that for undirected graphs one can achieve ratio O(klnk) for his variant, where k=maxv∈Vdv is the maximum demand. We improve this by achieving ratio $\min\{p^*\lnk,k\}\cdot O(\ln (k/q^*))$ for a more general version with node capacities, where p∗=maxv∈Vpv is the maximum bonus and q∗=minv∈Vqv is the minimum capacity. In particular, for the most natural case p∗=1 considered by Fukunaga, we improve the ratio from O(klnk) to O(ln2k). We also get ratio O(k) for the edge-connectivity version, for which no ratio that depends on k only was known before. To derive these results, we consider a particular case of the Survivable Network (SN) problem when all edges of positive cost form a star. We give ratio O(min{lnn,ln2k}) for this variant, improving over the best ratio known for the general case O(k3lnn) of Chuzhoy and Khanna.
We consider low connectivity variants of the Survivable Network with Minimum Number of Steiner Points (SN-MSP) problem: given a finite set R of terminals in a metric space (M,d), a subset B⊆R of "unstable" terminals, and connectivity requirements {r_{uv}: u,v \in R}, find a minimum size set S⊆M of additional points such that the unit-disc graph of R∪S contains ruv pairwise internally edge-disjoint and (B∪S)-disjoint uv-paths for all u,v∈R. The case when ruv=1 for all u,v∈R is the {\sf Steiner Tree with Minimum Number of Steiner Points} (ST-MSP) problem, and the case ruv∈{0,1} is the {\sf Steiner Forest with Minimum Number of Steiner Points} (SF-MSP) problem. Let Δ be the maximum number of points in a unit ball such that the distance between any two of them is larger than 1. It is known that Δ=5 in R2 The previous known approximation ratio for {\sf ST-MSP} was ⌊(Δ+1)/2⌋+1+ε in an arbitrary normed space \cite{NY}, and 2.5+ε in the Euclidean space R2 \cite{cheng2008relay}. Our approximation ratio for ST-MSP is 1+ln(Δ−1)+ε in an arbitrary normed space, which in R2 reduces to 1+ln4+ε<2.3863+ε. For SN-MSP with ruv∈{0,1,2}, we give a simple Δ-approximation algorithm. In particular, for SF-MSP, this improves the previous ratio 2Δ.
An ordered pair S^=(S,S+) of subsets of V is called a {\em biset} if S⊆S+; (V−S+,V−S) is the co-biset of S^. Two bisets X^,Y^ intersect if X∩Y=∅ and cross if both X∩Y=∅ and X+∪Y+=V. The intersection and the union of two bisets X^,Y^ is defined by X^∩Y^=(X∩Y,X+∩Y+) and X^∪Y^=(X∪Y,X+∪Y+). A biset-family F is crossing (intersecting) if X^∩Y^,X^∪Y^∈F for any X^,Y^∈F that cross (intersect). A directed edge covers a biset S^ if it goes from S to V−S+. We consider the problem of covering a crossing biset-family F by a minimum-cost set of directed edges. While for intersecting F, a standard primal-dual algorithm computes an optimal solution, the approximability of the case of crossing F is not yet understood, as it includes several NP-hard problems, for which a poly-logarithmic approximation was discovered only recently. Let us say that a biset-family F is k-regular if X^∩Y^,X^∪Y^∈F for any X^,Y^∈F with ∣V−(X∪Y)∣≥k+1 that intersect. In this paper we obtain an O(log∣V∣)-approximation algorithm for arbitrary crossing F; if in addition both F and the family of co-bisets of F are k-regular, our ratios are: O(log∣V∣−k∣V∣) if ∣S+∖S∣=k for all S^∈F, and O(∣V∣−k∣V∣log∣V∣−k∣V∣) if ∣S+∖S∣≤k for all S^∈F. Using these generic algorithms, we derive approximation algorithms for some network design problems.
Let G=(V,E) be a k-edge-connected graph with edge costs {c(e):e∈E} and let 1≤ℓ≤k−1. We show by a simple and short proof, that G contains an ℓ-edge cover I such that: c(I)≤kℓc(E) if G is bipartite, or if ℓ∣V∣ is even, or if ∣E∣≥2k∣V∣+2ℓk; otherwise, c(I)≤(kℓ+k∣V∣1)c(E). The particular case ℓ=k−1 and unit costs already includes a result of Cheriyan and Thurimella, that G contains a (k−1)-edge-cover of size ∣E∣−⌊∣V∣/2⌋. Using our result, we slightly improve the approximation ratios for the {\sf k-Connected Subgraph} problem (the node-connectivity version) with uniform and β-metric costs. We then consider the dual problem of finding a spanning subgraph of maximum connectivity k∗ with a prescribed number of edges. We give an algorithm that computes a (k∗−1)-connected subgraph, which is tight, since the problem is NP-hard.
We consider connectivity problems with orientation constraints. Given a directed graph D and a collection of ordered node pairs P let $P[D]=\{(u,v) \in P: D {contains a} uv{-path}}$. In the {\sf Steiner Forest Orientation} problem we are given an undirected graph G=(V,E) with edge-costs and a set P⊆V×V of ordered node pairs. The goal is to find a minimum-cost subgraph H of G and an orientation D of H such that P[D]=P. We give a 4-approximation algorithm for this problem. In the {\sf Maximum Pairs Orientation} problem we are given a graph G and a multi-collection of ordered node pairs P on V. The goal is to find an orientation D of G such that ∣P[D]∣ is maximum. Generalizing the result of Arkin and Hassin [DAM'02] for ∣P∣=2, we will show that for a mixed graph G (that may have both directed and undirected edges), one can decide in nO(∣P∣) time whether G has an orientation D with P[D]=P (for undirected graphs this problem admits a polynomial time algorithm for any P, but it is NP-complete on mixed graphs). For undirected graphs, we will show that one can decide whether G admits an orientation D with ∣P[D]∣≥k in O(n+m)+2O(k⋅loglogk) time; hence this decision problem is fixed-parameter tractable, which answers an open question from Dorn et al. [AMB'11]. We also show that {\sf Maximum Pairs Orientation} admits ratio O(log∣P∣/loglog∣P∣), which is better than the ratio O(logn/loglogn) of Gamzu et al. [WABI'10] when ∣P∣<n. Finally, we show that the following node-connectivity problem can be solved in polynomial time: given a graph G=(V,E) with edge-costs, s,t∈V, and an integer ℓ, find a min-cost subgraph H of G with an orientation D such that D contains ℓ internally-disjoint st-paths, and ℓ internally-disjoint ts-paths.
Given a graph with edge costs, the {\em power} of a node is themaximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider the following fundamental problem in wireless network design. Given a graph G=(V,E) with edge costs and degree bounds {r(v):v∈V}, the {\sf Minimum-Power Edge-Multi-Cover} ({\sf MPEMC}) problem is to find a minimum-power subgraph J of G such that the degree of every node v in J is at least r(v). We give two approximation algorithms for {\sf MPEMC}, with ratios O(logk) and k+1/2, where k=maxv∈Vr(v) is the maximum degree bound. This improves the previous ratios O(logn) and k+1, and implies ratios O(logk) for the {\sf Minimum-Power k-Outconnected Subgraph} and O(logklogn−kn) for the {\sf Minimum-Power k-Connected Subgraph} problems; the latter is the currently best known ratio for the min-cost version of the problem.
A subset T⊆V of terminals is k-connected to a root s in a directed/undirected graph J if J has k internally-disjoint vs-paths for every v∈T; T is k-connected in J if T is k-connected to every s∈T. We consider the {\sf Subset k-Connectivity Augmentation} problem: given a graph G=(V,E) with edge/node-costs, node subset T⊆V, and a subgraph J=(V,EJ) of G such that T is k-connected in J, find a minimum-cost augmenting edge-set F⊆E∖EJ such that T is (k+1)-connected in J∪F. The problem admits trivial ratio O(∣T∣2). We consider the case ∣T∣>k and prove that for directed/undirected graphs and edge/node-costs, a ρ-approximation for {\sf Rooted Subset k-Connectivity Augmentation} implies the following ratios for {\sf Subset k-Connectivity Augmentation}: (i) b(ρ+k)+(∣T∣−k3∣T∣)2H(∣T∣−k3∣T∣); (ii) ρ⋅O(∣T∣−k∣T∣logk), where b=1 for undirected graphs and b=2 for directed graphs, and H(k) is the kth harmonic number. The best known values of ρ on undirected graphs are min{∣T∣,O(k)} for edge-costs and min{∣T∣,O(klog∣T∣)} for node-costs; for directed graphs ρ=∣T∣ for both versions. Our results imply that unless k=∣T∣−o(∣T∣), {\sf Subset k-Connectivity Augmentation} admits the same ratios as the best known ones for the rooted version. This improves the ratios in \cite{N-focs,L}.
We focus on designing combinatorial algorithms for the Capacitated Network Design problem (Cap-SNDP). The Cap-SNDP is the problem of satisfying connectivity requirements when edges have costs and hard capacities. We begin by showing that the Group Steiner tree problem (GST) is a special case of Cap-SNDP even when there is connectivity requirement between only one source-sink pair. This implies the first poly-logarithmic lower bound for the Cap-SNDP. We next provide combinatorial algorithms for several special cases of this problem. The Cap-SNDP is equivalent to its special case when every edge has either zero cost or infinite capacity. We consider a special case, called Connected Cap-SNDP, where all infinite-capacity edges in the solution are required to form a connected component containing the sinks. This problem is motivated by its similarity to the Connected Facility Location problem [G+01,SW04]. We solve this problem by reducing it to Submodular tree cover problem, which is a common generalization of Connected Cap-SNDP and Group Steiner tree problem. We generalize the recursive greedy algorithm [CEK] achieving a poly-logarithmic approximation algorithm for Submodular tree cover problem. This result is interesting in its own right and gives the first poly-logarithmic approximation algorithms for Connected hard capacities set multi-cover and Connected source location. We then study another special case of Cap-SNDP called Unbalanced point-to-point connection problem. Besides its practical applications to shift design problems [EKS], it generalizes many problems such as k-MST, Steiner Forest and Point-to-Point Connection. We give a combinatorial logarithmic approximation algorithm for this problem by reducing it to degree-bounded SNDP.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.