Copertina

A (1.999999)-approximation ratio for vertex cover problem

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Zohrehbandian, Majid
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

On the approximability of graph visibility problems
di: Bilò, Davide, et al.
Pubblicazione: (2024)

A $4/3$ ratio approximation algorithm for the Tree Augmentation Problem by deferred local-ratio and climbing
di: Kortsarz, Guy
Pubblicazione: (2026)

The geodesic cover problem for butterfly networks
di: Manuel, Paul, et al.
Pubblicazione: (2022)

Hardness of approximation for ground state problems
di: Gharibian, Sevag, et al.
Pubblicazione: (2024)

Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs
di: Duda, Jarek
Pubblicazione: (2024)

Disjoint covering of bipartite graphs with $s$-clubs
di: Monti, Angelo, et al.
Pubblicazione: (2024)

Sketching approximability of all finite CSPs
di: Chou, Chi-Ning, et al.
Pubblicazione: (2021)

An approximation notion between P and FPTAS
di: Bismuth, Samuel, et al.
Pubblicazione: (2026)

Hardness of clique approximation for monotone circuits
di: Błasiok, Jarosław, et al.
Pubblicazione: (2025)

On the complexity of the Maker-Breaker happy vertex game
di: Hilaire, Mathieu, et al.
Pubblicazione: (2026)

On the complexity of covering points by guillotine cuts
di: Garijo, Delia, et al.
Pubblicazione: (2026)

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
di: Bok, Jan, et al.
Pubblicazione: (2021)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
di: Colli, Giordano
Pubblicazione: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
di: Ben-Ameur, Walid, et al.
Pubblicazione: (2025)

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
di: Dikstein, Yotam, et al.
Pubblicazione: (2023)

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
di: Bengali, Vedangi, et al.
Pubblicazione: (2024)

Sketching approximations and LP approximations for finite CSPs are related
di: Singer, Noah G., et al.
Pubblicazione: (2025)

Approximate cycle double cover
di: Ghanbari, Babak, et al.
Pubblicazione: (2025)

Attacking the Polynomials in the Maze of Finite Fields problem
di: Barbero, Àngela, et al.
Pubblicazione: (2026)

Unlocking the Theory Behind Scaling 1-Bit Neural Networks
di: Daliri, Majid, et al.
Pubblicazione: (2024)

Low-degree approximation of QAC$^0$ circuits
di: Montanaro, Ashley, et al.
Pubblicazione: (2024)

A combinatorial view of Holant problems on higher domains
di: Liu, Yin
Pubblicazione: (2024)

Quantum Max-Cut is NP hard to approximate
di: Piddock, Stephen
Pubblicazione: (2025)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

Complexity analysis and practical resolution of the data classification problem with private characteristics
di: Pantoja, David, et al.
Pubblicazione: (2026)

The complexity of strong conflict-free vertex-connection $k$-colorability
di: Hsieh, Sun-Yuan, et al.
Pubblicazione: (2024)

Factorization norms and Zarankiewicz problems
di: Tomon, István
Pubblicazione: (2025)

On the complexity of unique quantum witnesses and quantum approximate counting
di: Anshu, Anurag, et al.
Pubblicazione: (2024)

On approximability of the Permanent of PSD matrices
di: Ebrahimnejad, Farzam, et al.
Pubblicazione: (2024)

Inner-approximate Reachability Computation via Zonotopic Boundary Analysis
di: Ren, Dejin, et al.
Pubblicazione: (2024)

Efficient approximate unitary designs from random Pauli rotations
di: Haah, Jeongwan, et al.
Pubblicazione: (2024)

BQP, meet NP: Search-to-decision reductions and approximate counting
di: Gharibian, Sevag, et al.
Pubblicazione: (2024)

Simple approximation algorithms for Polyamorous Scheduling
di: Biktairov, Yuriy, et al.
Pubblicazione: (2024)

An in-principle super-polynomial quantum advantage for approximating combinatorial optimization problems via computational learning theory
di: Pirnay, Niklas, et al.
Pubblicazione: (2022)

Streaming approximation resistance of every ordering CSP
di: Singer, Noah G., et al.
Pubblicazione: (2021)

Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity
di: Sim, Chee-Khian
Pubblicazione: (2024)

A simplified version of the quantum OTOC$^{(2)}$ problem
di: King, Robbie, et al.
Pubblicazione: (2025)

On the complexity and approximability of Bounded access Lempel Ziv coding
di: Cicalese, Ferdinando, et al.
Pubblicazione: (2024)

The dihedral hidden subgroup problem
di: Chen, Imin, et al.
Pubblicazione: (2021)

Critical window for approximate counting in dense Ising models
di: Galanis, Andreas, et al.
Pubblicazione: (2026)