Aug 2026· INFORMS journal on computing· 0 citations· 17 references
TL;DR
A general methodology to derive approximation results for different algorithms that share the following high-level structure is proposed: a specific procedure is first applied to a list of long jobs, followed by a standard list scheduling approach.
Abstract
We consider the well-known uniform machine scheduling problem [Formula: see text], in which we are given a set of n jobs with processing times [Formula: see text] and a set of m parallel machines, each with a corresponding speed factor [Formula: see text] for [Formula: see text]. The goal is to find an assignment of the jobs to the machines that minimizes the makespan. We propose a general methodology to derive approximation results for different algorithms that share the following high-level structure: a specific procedure is first applied to a list of long jobs, followed by a standard list scheduling approach. This methodology is based on theoretical results we derive for [Formula: see text] that allow us to analyze instances with a limited number of jobs. We evaluate the worst case performance of several algorithms using mathematical programming formulations and derive both existing and new approximation ratios for the problem with up to seven machines. In this context, our approach offers a more flexible tool than traditional analytical proof systems for studying the [Formula: see text] problem and potentially other related problems.
History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms.
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1129 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1129 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
We study the problem of parallel comparison sorting, modeled as a two-player game between a sorter and an adversary. Using a minimax algorithm enhanced with several domain-specific optimizations, we compute the exact minimal number of rounds [Formula: see text] required to sort [Formula: see text] elements using at mos...
We present deterministic polynomial-space algorithms that solve Max 2-SAT on $n$ variables exactly in time $\Ostar(2^{(1-\gamma)n})$, for a fixed $\gamma>0$, on several classes of instances whose clause density may grow with $n$. Our main tool extends the classic DPLL branching algorithm. When the search gives a variab...
This paper analyzes a matching problem in which the cost of each edge is a vector with $k$ components and provides various results including FPT-membership for parameters $k$ and $Z$ combined, as well as W[P]-membership and W[SAT]-hardness for each of the two parameters individually.
Jonas Friemel, Tilo Hoitz, Phillip Keldenich et al.· 0 citations
We revisit the capacitated $k$-median problem, focusing on constant-factor approximation algorithms with either $(1+\epsilon)$-cardinality or capacity violations. Previous results [DemirciL16, Li16} achieve an $O_\epsilon(1)$-approximation with $(1+\epsilon)$-violations via complex extended configuration linear program...
We give a randomized combinatorial \((1/2 - \varepsilon)\)-approximation for nonnegative non-monotone \(k\)-submodular maximization under a fixed number \(d\) of knapsack constraints, for \(k \ge 2 \). The algorithm selects whole elements and follows the proportional top-2 rule of Chen et al. \cite{chen2026}: it sample...
Si-Yuan Chen, Sui-Xiang Gao, Zhe-Yu Jiang et al.· 0 citations
We give a fixed-parameter tractable (FPT) algorithm with running time $f(k,\bar\Delta)\cdot {|I|}^{O(1)}$ for integer linear programs with 4-block structure, parameterized by the maximum block dimension $k$ and the largest absolute entry $\bar\Delta$ in the local-column blocks. This result resolves a long-standing open...
Klaus Jansen, Felix Ohnesorge, Corinna Wambsganz· arXiv.org· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.