Matroid-constrained vertex cover (Q6162073)

From MaRDI portal

Jump to:navigation, search

scientific article; zbMATH DE number 7696157

Language	Label	Description	Also known as
English	Matroid-constrained vertex cover	scientific article; zbMATH DE number 7696157

Statements

scholarly article

0 references

Matroid-constrained vertex cover (English)

0 references

Chien-Chung Huang

0 references

0 references

Theoretical Computer Science

0 references

publication date

15 June 2023

0 references

full work available at URL

https://arxiv.org/abs/2306.04342

0 references

zbMATH Keywords

vertex cover

0 references

matroid

0 references

kernel

0 references

local search

0 references

MaRDI profile type

MaRDI publication profile

0 references

0 references

Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder

0 references

0 references

Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs

0 references

New bounds for the CLIQUE-GAP problem using graph decomposition theory

0 references

Maximizing a Submodular Set Function Subject to a Matroid Constraint (Extended Abstract)

0 references

Maximizing a Monotone Submodular Function Subject to a Matroid Constraint

0 references

Submodular maximization meets streaming: matchings, matroids, and more

0 references

0 references

Streaming Algorithms for Submodular Function Maximization

0 references

Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams

0 references

Testing membership in matroid polyhedra

0 references

Transversals and matroid partition

0 references

Approximation Algorithms for Maximization Problems Arising in Graph Partitioning

0 references

A Simple <tt><i>O</i>(log log(rank))</tt>-Competitive Algorithm for the Matroid Secretary Problem

0 references

0 references

Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search

0 references

Algorithms and Data Structures

0 references

On approximation of max-vertex-cover

0 references

An improved rounding method and semidefinite programming relaxation for graph partition

0 references

0 references

0 references

A new series of dense graphs of high girth

0 references

Submodular Maximization over Multiple Matroids via Generalized Exchange Properties

0 references

Approximate multi-matroid intersection via iterative refinement

0 references

Lossy kernelization

0 references

Tight Running Time Lower Bounds for Strong Inapproximability of Maximum <i>k</i>-Coverage, Unique Set Cover and Related Problems (via <i>t</i>-Wise Agreement Testing Theorem)

0 references

Applications of the notion of independence to problems of combinatorial analysis

0 references

0 references

0 references

Combinatorial optimization. Polyhedra and efficiency (3 volumes)

0 references

A simple PTAS for Weighted Matroid Matching on Strongly Base Orderable Matroids

0 references

Transversal Theory and Matroids

0 references

Identifiers

zbMATH Open document ID

0 references

0 references

10.1016/j.tcs.2023.113977

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

zbMATH DE Number

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6162073

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Item:Q6162073&oldid=37524981"