Search Results - subject:"parameterized complexity"

Complexity of scheduling few types of jobs on related and unrelated machines

Koutecký, Martin; Zink, Johannes - In: Journal of Scheduling 28 (2025) 1, pp. 139-156

The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general NP -hard, much attention has...

Persistent link: https://www.econbiz.de/10015437033

Single-machine scheduling with fixed energy recharging times to minimize the number of late jobs and the number of just-in-time jobs : a parameterized complexity analysis

Yu, Renjie; Oron, Daniel - In: European journal of operational research : EJOR 324 (2025) 1, pp. 40-48

Persistent link: https://www.econbiz.de/10015432992

Sparse integer programming is fixed-parameter tractable

Eisenbrand, Friedrich; Hunkenschröder, Christoph; … - In: Mathematics of operations research 50 (2025) 3, pp. 2141-2156

Persistent link: https://www.econbiz.de/10015444745

Fairness in repetitive scheduling

Hermelin, Danny; Molter, Hendrik; Niedermeier, Rolf; … - In: European journal of operational research : EJOR 323 (2025) 3, pp. 724-738

Persistent link: https://www.econbiz.de/10015432897

On the tractability of hard scheduling problems with generalized due-dates with respect to the number of different due-dates

Mosheiov, Gur; Oron, Daniel; Shabtay, Dvir - In: Journal of scheduling : JOS 25 (2022) 5, pp. 577-587

Persistent link: https://www.econbiz.de/10013453936

On data reduction for dynamic vector bin packing

Van Bevern, René; Melnikov, Andrey; Smirnov, Pavel V.; … - In: Operations research letters 51 (2023) 4, pp. 446-452

Persistent link: https://www.econbiz.de/10014426600

Parameterized algorithms for power-efficiently connecting wireless sensor networks : theory and experiments

Bentert, Matthias; Van Bevern, René; Nichterlein, André; … - In: INFORMS journal on computing : JOC ; charting new … 34 (2022) 1, pp. 55-75

Persistent link: https://www.econbiz.de/10013358842

Why is maximum clique often easy in practice?

Walteros, Jose L.; Buchanan, Austin - In: Operations research 68 (2020) 6, pp. 1866-1895

Persistent link: https://www.econbiz.de/10012392172

On the parameterized tractability of the just-in-time flow-shop scheduling problem

Hermelin, Danny; Shabtay, Dvir; Talmon, Nimrod - In: Journal of scheduling 22 (2019) 6, pp. 663-676

Persistent link: https://www.econbiz.de/10012125311

K-adaptability in stochastic combinatorial optimization under objective uncertainty

Buchheim, Christoph; Pruente, Jonas - In: European journal of operational research : EJOR 277 (2019) 3, pp. 953-963

Persistent link: https://www.econbiz.de/10012102217