跳到正文
研踪PaperTrail

论文库

检索计算机领域论文，按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+0新增论文
+0其中 AI 相关
+2已有论文修订
+100新增 AI 导读

arXiv 最近完成扫描：2026-11-15 01:33 · 全站最近入库：2026-11-14 15:09各信源进度 →

统计口径与数据新鲜度

统计 2026-11-14 01:43 — 2026-11-15 01:43（北京时间） · 点击数字查看对应简报；AI 相关包含在新增论文内。

最近完成检查：2026-11-15 01:33最近发现新增版本：2026-11-14 15:09库内论文最新更新时间：2026-11-13 02:59

每分钟刷新已保存的数据。空检查不代表采集异常；新收录可能包含历史论文。AI 导读按新增版本计数。

23,348 已收录论文19,580 AI 相关6,729 有修订112 HF 社区发现

浏览论文库

研究日报 / 周报 →按信源浏览 →

时间范围跟随排序：版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常，查看状态 →

找到 5 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-15 01:32（北京时间）
新论文 · v1arXiv:2611.16551

Hardness, Approximation, and Parameterized Algorithms for Asynchronous Border Minimization

Giulian Buzatu, Adrian Miclăuş, Alexandru Popa

原文摘要

In the Asynchronous Border Minimization Problem (BMP), a set of DNA probe strings is placed on a grid and synthesized using a common sequence of nucleotide-deposition steps. At each step, every cell may accept or skip the offered nucleotide. The cost is the total number of disagreements between neighboring cells over all steps. We study both free placement, where the probes may be rearranged, and fixed placement, where their positions are given. We show that free-placement BMP on a square grid is NP-complete over three symbols. For one-dimensional BMP, we prove APX-hardness over a binary alphabet, and NP-completeness even when every probe has length two. We also obtain an $8/7$-approximation for the latter restriction. For square grids, we give a randomized $O(n^{1/4}\log n)$-approximation, improving the earlier $O(n^{1/4}\log^2 n)$ guarantee. Both free- and fixed-placement BMP on rectangular grids are fixed-parameter tractable when parameterized only by the allowed border cost.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.14786

Source Assignment: Hardness, Approximation, and Parameterized Algorithms

Ruxandra Marinescu-Ghemeci, Adrian Miclăuş, Alexandru Popa

原文摘要

In Source Assignment, each pointer represents a substring of a common reference string and may have several possible source occurrences. The goal is to choose one source for each pointer while minimizing the number of distinct reference boundaries used by the selected sources. The problem was introduced by Qiu and Kingsford (Bioinformatics 2021) in the context of compact genome-graph construction. We distinguish \emph{Explicit Source Assignment}, where admissible source sets are given explicitly, from \emph{Complete Source Assignment}, where all occurrences of each pointer string are available. We show that Explicit Source Assignment has an exact value-preserving formulation as cardinality Set Cover with Pairs. For every fixed $\varepsilon>0$, it cannot be approximated within $(1-\varepsilon)\ln p$ unless $\mathrm{P}=\mathrm{NP}$, even over a binary alphabet when all pointers have length one, while known algorithms for Minimum-Weight Multicolored Subgraph give an $O(\sqrt{q\log p})$-approximation for arbitrary pointer lengths. Our main hardness result proves that Complete Source Assignment is APX-hard even over a binary alphabet, with equal pointer lengths and at most two sources per pointer. For edge-disjoint equal-length instances, we give a $3/2$-approximation and a $1.12585$-approximation when each pointer has at most two sources. We also introduce the rainbow-path length $λ$: the problem is polynomial-time solvable for $λ\le2$, and for $λ\le3$ we obtain a $(9/8+\varepsilon)$-approximation. We further give a polynomial-time test for deciding whether abstract source sets can be realized exactly as complete occurrence sets over an unrestricted alphabet. Finally, we give exact fixed-parameter algorithms for several structural parameters, and show that Complete Source Assignment is fixed-parameter tractable in the alphabet size and maximum pointer length.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.12348

How Hard Is Tokenisation? Algorithms and Complexity Beyond NP-Hardness

Andrei Robert Ion, Rares Mateiu, Adrian Miclaus, Alexandru Popa

原文摘要

Given a collection of strings and a vocabulary budget, how well can we minimize its total token count, and how does the answer change with the tokenisation model? For binary direct tokenisation, previous work proved APX-hardness but left constant-factor approximability unresolved \citep{kastreva2026}. We rule out every polynomial-time $M^{1-\varepsilon}$ approximation, for fixed $\varepsilon>0$, unless $\mathrm{P}=\mathrm{NP}$, even on distinct equal-length strings with $K=m-1$. Here $M$ is the total input length and $m$ is the number of input strings. We complement this lower bound with a deterministic polynomial-time $O(M/\log M)$ approximation algorithm and stronger bounds for selected vocabulary budgets. For the different objective of maximizing compression savings, GreedTok was shown to attain a constant fraction of the optimum on unrestricted alphabets \citep{baliga2026}; we establish a deterministic EPTAS for direct savings on every fixed alphabet and analyze greedy selection by true marginal gains. For exact optimization, we give a binary direct algorithm running in $2^{O(n\log\log n/\log n)}\poly(I)$ time, where $n$ is the total length of the distinct input strings and $I$ is the input encoding length. Finally, we resolve two unary merge-model hardness questions left by the bounded-alphabet study \citep{kastreva2026}: standard unary bottom-up tokenisation is APX-hard, and unary optimal pair encoding is strongly NP-complete, strengthening the previously known weak hardness.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04889

NP-Hardness and a PTAS for Maximum Interval Multicover, with Applications to Dense Subgraphs

Morteza Alimi, Tobias Mömke, Alexandru Popa, Michael Ruderer

原文摘要

Given intervals and points on a line, each point with a demand, and a budget $K$, Maximum Interval Multicover asks for at most $K$ intervals that satisfy as many points as possible, a point being satisfied if it lies in at least as many chosen intervals as its demand. One application is committee elections in which each candidate is approved by consecutive voters and voters have individual demands. Xu, Ran and Zhang introduced the problem and gave a $1/2$-approximation; the objective is not submodular when demands exceed one. Li, Tu, Zhang and Cao gave a polynomial-time approximation scheme (PTAS) for the minimization counterpart, unweighted partial interval multicover, and asked for its complexity. We prove that both problems are NP-hard, even for intervals of equal length; as their optima are integers bounded by the input size, neither has a fully polynomial-time approximation scheme unless $\mathrm{P}=\mathrm{NP}$. We then give a PTAS for Maximum Interval Multicover, also for arbitrary nonnegative nondecreasing rewards for the coverage of each point. Building on a decomposition from Nonner's PTAS for Densest $k$-Subgraph on interval graphs, our scheme cuts the line into pieces at a small loss and solves every piece exactly. The key dynamic program handles intervals crossing a common point by choosing an interleaving of their left and right endpoints rather than sweeping along the line; it needs only two counters to track these intervals. The same algorithm yields PTASes on convex bipartite graphs for Bipartite Dense Subgraph, improving on the ratio $2/3$ of Backer and Keil for the subclass of bipartite permutation graphs, and on interval graphs for Maximum $k$-Vertex Cover and weighted clique counts.

cs.DS

查看论文
arXiv ↗PDF ↗
新论文 · v1arXiv:2611.04457

Entropy-Weighted Soundness for Multi-Answer Birthday Graphs

Alexandru Popa

原文摘要

The vertices of a Boolean birthday graph are partial assignments on $\ell$-subsets of $n$ variables. Although a satisfying assignment induces a $K$-clique for $K=\binom n\ell$, an arbitrary selection of $K$ vertices may repeat some views and omit others. This makes soundness substantially harder than under uniform view sampling. For bounded-occurrence, constant-gap Boolean ternary CSPs whose constraints each involve three distinct variables (allowing arbitrary Boolean predicates), we prove that the graph's maximum induced $K$-vertex density satisfies \[ ρ^*(K)\le 2\exp\!\left(-c\, \frac{\ell^3}{n^2\log(en/\ell)}\right) \] for $2\le\ell\le x_0n$ and $\ell\log(en/\ell)\ge C_0\log(n+1)$, with positive constants depending only on the source parameters. The argument refines the biclique counting method by charging the entropy of an adversarially chosen flattening to mutual information and a combinatorial obstruction energy. In the overlapping parameter range it strengthens the explicit soundness exponent previously established for this graph. We also establish an unconditional stability theorem for arbitrary sets $H$ of exactly $K$ distinct local assignments, with missing views and multiple answers: $f_*(H)\le34(n/\ell)q_{\mathrm{con}}(H)$ for every $1\le\ell\le n$. It gives a complementary additive near-clique soundness bound. We do not derive a new fine-grained hardness theorem.

cs.CC · cs.DS

查看论文
arXiv ↗PDF ↗