Author name cluster

Mohit Garg 0003

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

STOC Conference 2025 Conference Paper

A 5/4-Approximation for Two-Edge Connectivity

Miguel Bosch-Calvo
Mohit Garg 0003
Fabrizio Grandoni 0001
Felix Hommelsheim
Afrouz Jabal Ameli
Alexander Lindermayr

The 2-Edge-Connected Spanning Subgraph problem (2ECSS) is among the most basic survivable network design problems: given an undirected and unweighted graph, the task is to find a spanning subgraph with the minimum number of edges that is 2-edge-connected (i.e., it remains connected after the removal of any single edge). 2ECSS is an NP-hard problem that has been extensively studied in the context of approximation algorithms. The best-known approximation ratio for 2ECSS prior to this work was 1.3+ε, for any constant ε>0 [Garg, Grandoni, Jabal-Ameli’23; Kobayashi, Noguchi’23]. In this paper, we present a 5/4-approximation algorithm. Our algorithm is also faster for small values of ε: its running time is n O (1) instead of n O (1/ε) .

Details

SODA Conference 2023 Conference Paper

Improved Approximation for Two-Edge-Connectivity

Mohit Garg 0003
Fabrizio Grandoni 0001
Afrouz Jabal Ameli

The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the 2-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph G, find a 2-edge-connected spanning subgraph H of G with the minimum number of edges (in particular, H remains connected after the removal of one arbitrary edge). 2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is 4/3. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschröder, Vempala and Vetta '00, '19] and [Sebö and Vygen, '14]. In this paper we present an improved approximation for 2-ECSS. The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to 6/5. While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are “almost” 3-vertex-connected: more precisely, given any 2-vertex-cut { u, v } of a structured graph G = (V, E), G[V \ {u, v }] has exactly 2 connected components, one of which contains exactly one node of degree 2 in G. * Partially supported by the SNSF Excellence Grant 200020B 182865/1 and the SNSF Grant 200021 200731/1.

Details

SODA Conference 2019 Conference Paper

Deterministic (½ + ε)-Approximation for Submodular Maximization over a Matroid

Niv Buchbinder
Moran Feldman
Mohit Garg 0003

We study the problem of maximizing a monotone submodular function subject to a matroid constraint and present a deterministic algorithm that achieves (½ + ε )-approximation for the problem. This algorithm is the first deterministic algorithm known to improve over the ½-approximation ratio of the classical greedy algorithm proved by Nemhauser, Wolsely and Fisher in 1978.

Details

SODA Conference 2015 Conference Paper

Set membership with a few bit probes

Mohit Garg 0003
Jaikumar Radhakrishnan

We consider the bit-probe complexity of the set membership problem, where a set S of size at most n from a universe of size m is to be represented as a short bit vector in order to answer membership queries of the form “Is x in S? ” by adaptively probing the bit vector at t places. Let s ( m, n, t ) be the minimum number of bits of storage needed for such a scheme. Buhrman, Miltersen, Radhakrishnan, and Srinivasan [4] and Alon and Feige [2] investigated s ( m, n, t ) for various ranges of the parameter t. We show the following. For two probes ( t = 2): (a) There is a constant C > 0, such that for all large. This improves on a result of Alon and Feige that states that for n ≤ log m, s ( m, n, 2) = O ( mn log((log m ) /n ) / log m ). (b) There is a constant D > 0, such that for 4 ≤ n and all large m, we have. Thus, s ( m, n, 2) = Ω( m ) for n ≥ log m, that is, the requirement n ≤ log m in the upper bound of Alon and Feige is essential for any asymptotic improvement over the characteristic vector representation. For three probes. This improves on a result of Alon and Feige that states that s ( m, n, 2) = O ( m  n ⅓ ). In general: We show that for. This lower bound improves on (for n ≤ log m ) the lower bound (valid only for n ≥ 16log m and for non-adaptive schemes) due to Alon and Feige; for small values of n, it also improves on the lower bound due to Buhrman et al. [4].

Details