## Abstract

Maximum weight independent set (MWIS) admits a _{k}^{1}-approximation in inductively k-independent graphs [2, 40] and a _{2}^{1}_{k}-approximation in k-perfectly orientable graphs [34]. These are a parameterized class of graphs that generalize k-degenerate graphs, chordal graphs, and intersection graphs of various geometric shapes such as intervals, pseudo-disks, and several others [40, 34]. We consider a generalization of MWIS to a submodular objective. Given a graph G = (V,E) and a non-negative submodular function f : 2^{V} → R_{+}, the goal is to approximately solve maxS∈I_{G} f(S) where IG is the set of independent sets of G. We obtain an Ω(_{k}^{1})-approximation for this problem in the two mentioned graph classes. The first approach is via the multilinear relaxation framework and a simple contention resolution scheme, and this results in a randomized algorithm with approximation ratio at least _{e}(_{k}^{1}_{+1)}. This approach also yields parallel (or low-adaptivity) approximations. Motivated by the goal of designing efficient and deterministic algorithms, we describe two other algorithms for inductively k-independent graphs that are inspired by work on streaming algorithms: a preemptive greedy algorithm and a primal-dual algorithm. In addition to being simpler and faster, these algorithms, in the monotone submodular case, yield the first deterministic constant factor approximations for various special cases that have been previously considered such as intersection graphs of intervals, disks and pseudo-disks.

Original language | English (US) |
---|---|

Title of host publication | Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2023 |

Editors | Nicole Megow, Adam Smith |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

ISBN (Electronic) | 9783959772969 |

DOIs | |

State | Published - Sep 2023 |

Externally published | Yes |

Event | 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023 - Atlanta, United States Duration: Sep 11 2023 → Sep 13 2023 |

### Publication series

Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Volume | 275 |

ISSN (Print) | 1868-8969 |

### Conference

Conference | 26th International Conference on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2023 and the 27th International Conference on Randomization and Computation, RANDOM 2023 |
---|---|

Country/Territory | United States |

City | Atlanta |

Period | 9/11/23 → 9/13/23 |

## Keywords

- elimination graphs
- independent set
- primal-dual
- submodular maximization

## ASJC Scopus subject areas

- Software