SIAM Journal on Computing· 2026Q1
Kayıplı Çekirdekleştirme: Ön İşlem Algoritmaları İçin Yeni Bir Çerçeve
Lossy Kernelization
- 2atıf
- Q1SCImago
- 2026yıl
Kısa özet
Araştırmacılar, çekirdekleştirmeyi yaklaşımlarla birleştiren ön işlem algoritmalarını analiz etmek için yeni bir çerçeve olan polinom boyutlu [Formül: metne bakınız]-yaklaşık çekirdekleri tanıtmaktadır. Bu çerçevenin etkinliğini, mevcut alt sınırları aşan Bağlantılı Köşe Örtüsü, Ayrık Döngü Paketleme ve Ayrık Çarpanlar için bu tür çekirdekler sağlayarak göstermektedirler.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Ana noktalar
- Ön işlem algoritmaları için çekirdekleştirme ve yaklaşımı birleştiren yeni bir çerçeve olan polinom boyutlu [Formül: metne bakınız]-yaklaşık çekirdekler tanıtıldı.
- Bağlantılı Köşe Örtüsü, Ayrık Döngü Paketleme ve Ayrık Çarpanlar için polinom boyutlu [Formül: metne bakınız]-yaklaşık çekirdekler geliştirildi.
- Bu yeni çekirdekler, üç problem için hem çekirdek boyutu hem de yaklaşım zorluğu konusundaki mevcut alt sınırları iyileştirmektedir.
- Uzun Yol ve Küme Örtüsü'nün, NP'nin P/poly'ye eşit olmaması varsayımı altında, herhangi bir [Formül: metne bakınız] için polinom boyutlu [Formül: metne bakınız]-yaklaşık çekirdekleri kabul etmediği kanıtlandı.
Yapay zekâ ile başlık ve abstract'tan üretildi; tam metin okunmaz.
Özet (abstract)
Abstract. In this paper we propose a new framework for analyzing the performance of preprocessing algorithms. Our framework builds on the notion of kernelization from parameterized complexity. However, as opposed to the original notion of kernelization, our definitions combine well with approximation algorithms and heuristics. The key new definition is that of a polynomial size [Formula: see text]-approximate kernel. Loosely speaking, a polynomial size [Formula: see text]-approximate kernel is a polynomial-time preprocessing algorithm that takes as input an instance [Formula: see text] to a parameterized problem, and outputs another instance [Formula: see text] to the same problem, such that [Formula: see text]. Additionally, for every [Formula: see text], a [Formula: see text]-approximate solution [Formula: see text] to the preprocessed instance [Formula: see text] can be turned in polynomial time into a [Formula: see text]-approximate solution [Formula: see text] to the original instance [Formula: see text]. Our main technical contributions are [Formula: see text]-approximate kernels of polynomial size for three problems, namely, Connected Vertex Cover, Disjoint Cycle Packing, and Disjoint Factors. These problems are known not to admit any polynomial size kernels unless NP [Formula: see text] [Formula: see text]. Our approximate kernels simultaneously beat both the lower bounds on the (normal) kernel size and the hardness of approximation lower bounds for all three problems. On the negative side we prove that Longest Path parameterized by the length of the path and Set Cover parameterized by the universe size do not admit even an [Formula: see text]-approximate kernel of polynomial size, for any [Formula: see text], unless NP [Formula: see text] [Formula: see text]. In order to prove this lower bound, we need to combine in a nontrivial way the techniques used for showing kernelization lower bounds with the methods for showing hardness of approximation.
Yazarların özeti; kaynağından alınmıştır. SIAM Journal on Computing, 2026 · DOI ↗
Ücretsiz hesapla devam et
Makaleye Sor ile bu makaleye günde 3 soru ücretsiz; makaleyi kaydet, kaynakçasını al, ilgi alanına göre her gün yeni özetler. Çıkarımlar Premium.
Web'de ücretsiz devam etGoogle ya da Apple hesabınla giriş; kart istemez. Bu makaleye geri dönersin.
Telefonda:
Alan: Hesaplamalı Kuram ve Matematik
Computational Theory and MathematicsComputer Science