WikiEdge:ArXiv速遞/2025-04-15

摘要

• 原文標題：Breaking a Long-Standing Barrier: 2-$\varepsilon$ Approximation for Steiner Forest
• 中文標題：突破長期障礙：斯坦納森林問題的2-ε近似算法
• 發布日期：2025-04-15 17:13:48+00:00
• 作者：Ali Ahmadi, Iman Gholami, MohammadTaghi Hajiaghayi, Peyman Jabbarzade, Mohammad Mahdavi
• 分類：cs.DS
• 原文鏈接：http://arxiv.org/abs/2504.11398v1

中文摘要：斯坦納森林問題（又稱廣義斯坦納樹問題）是邊加權圖上的一個基本優化問題，其目標是在給定頂點對集合的情況下，選擇一個最小成本的子圖使得每對頂點都連通。該問題推廣了1811年首次提出的斯坦納樹問題，後者的最佳已知近似因子為1.39 Byrka等，2010（STOC 2010最佳論文獎）。Agrawal等，1989（STOC 2023三十年時間檢驗獎）的開創性工作與Goemans和Williamson，1992（SICOMP'95）的改進，在35年前就建立了斯坦納森林問題的2-近似算法。Jain（FOCS'98）開創性的迭代捨入技術後來將這些結果擴展到更高連通性場景。儘管該問題具有長期重要性，但突破2的近似因子始終是重大挑戰，甚至引發類似頂點覆蓋問題的猜想——獲得更好因子可能確實困難。值得注意的是，包括Gupta和Kumar（STOC'15）以及[[Gro{\ss}等]]（ITCS'18）的基礎性工作，分別提出了96和69近似算法，可能寄望為斯坦納森林問題實現低於2的常數因子近似突破鋪路。 本文通過設計一種新穎的確定性算法，實現了$2 - 10^{-11}$的近似比，突破了2的近似壁壘。作為方法的核心組件，我們還針對斯坦納樹問題提出了一種基於對偶的局部搜索算法，其近似保證為$1.943$，該成果本身也具有獨立價值。

摘要

• 原文標題：Progressive Rock Music Classification
• 中文標題：漸進搖滾音樂分類
• 發布日期：2025-04-15 02:48:52+00:00
• 作者：Arpan Nagar, Joseph Bensabat, Jokent Gaza, Moinak Dey
• 分類：cs.SD, cs.AI, cs.LG, eess.AS
• 原文鏈接：http://arxiv.org/abs/2504.10821v1

中文摘要：本研究探討前衛搖滾音樂的分類問題，該音樂流派以複雜的作曲結構和多樣化的器樂編配為特徵，與其他音樂風格截然不同。針對這一音樂信息檢索（MIR）任務，我們使用Librosa庫從歌曲片段中提取了包括聲譜圖、梅爾頻率倒譜係數（MFCCs）、色度圖和節拍位置在內的綜合音頻特徵，並通過贏家通吃投票策略將片段級預測聚合為最終歌曲分類。我們對多種機器學習技術進行了對比分析：在計算資源受限情況下，採用主成分分析（PCA）進行降維處理，探索了包含Bagging（隨機森林、極端隨機樹、Bagging分類器）和Boosting（XGBoost、梯度提升）的集成方法；同時研究了深度學習方法，包括開發具有特定層配置、歸一化和激活函數的定製一維卷積神經網絡（1D CNN）架構（命名為"Zuck"和"Satya"），並微調了基於注意力機制的最先進音頻聲譜圖變換器（AST）模型。驗證集和測試集的性能評估顯示不同模型效果各異，其中極端隨機樹等集成方法最高達到76.38%的測試準確率。本研究為前衛搖滾流派分類這一精細任務提供了多種機器學習範式應用及相對性能的深入見解。