Matroid-constrained vertex cover
From MaRDI portal
Publication:6162073
DOI10.1016/j.tcs.2023.113977zbMath1522.68406arXiv2306.04342MaRDI QIDQ6162073
Chien-Chung Huang, Unnamed Author
Publication date: 15 June 2023
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2306.04342
Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35) Approximation algorithms (68W25) Signed and weighted graphs (05C22)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Submodular maximization meets streaming: matchings, matroids, and more
- Testing membership in matroid polyhedra
- Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
- New bounds for the CLIQUE-GAP problem using graph decomposition theory
- On approximation of max-vertex-cover
- An improved rounding method and semidefinite programming relaxation for graph partition
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Approximation Algorithms for Maximization Problems Arising in Graph Partitioning
- A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids
- Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
- Streaming Algorithms for Submodular Function Maximization
- A new series of dense graphs of high girth
- Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams
- Transversal Theory and Matroids
- Lossy kernelization
- Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)
- A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
- Algorithms and Data Structures
- Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)
- Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search
- Transversals and matroid partition
- Applications of the notion of independence to problems of combinatorial analysis
- Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder
- Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
- Approximate multi-matroid intersection via iterative refinement
This page was built for publication: Matroid-constrained vertex cover
