A logarithmic approximation for unsplittable flow on line graphs
Bibliographic record
Abstract
We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time s i , an end time t i , a demand d i > 0, and a profit p i > 0. A task, if accepted, requires d i units of “bandwidth” from time s i to t i and accrues a profit of p i . For every time t , we are also specified the available bandwidth c t , and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints. We present the first polynomial time O (log n ) approximation algorithm for this problem. This significantly advances the state of the art, as no polynomial time o ( n ) approximation was known previously. Previous results for this problem were known only in more restrictive settings; in particular, either the instance satisfies the so-called “no-bottleneck” assumption: max i d i ≤ min t c t , or the ratio of both maximum to minimum demands and maximum to minimum capacities are polynomially (or quasi-polynomially) bounded in n . Our result, on the other hand, does not require these assumptions. Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω( n ) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame machine prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. The Gemma side is a direct model label for every work in the frame, read from the title-only record. The Codex side is a classifier learned from the 10,348 direct Codex labels and calibrated to design-weighted sample rates; fields without enough sample support carry no Codex call. Candidate is the union of the two sides; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels.
Distilled classifier scores by category (both heads)
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.002 | 0.007 |
| Meta-epidemiology (narrow) | 0.002 | 0.001 |
| Meta-epidemiology (broad) | 0.002 | 0.001 |
| Bibliometrics | 0.001 | 0.002 |
| Science and technology studies | 0.001 | 0.001 |
| Scholarly communication | 0.003 | 0.007 |
| Open science | 0.003 | 0.002 |
| Research integrity | 0.002 | 0.003 |
| Insufficient payload (model declined to judge) | 0.012 | 0.002 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one source (direct Gemma or distilled Codex), not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".