2024/04/26 by Klaus Jansen, Jansen, Klaus, Kai Kahler +3 · 1 citation
Business, Management and Accounting · Engineering · #68Q27 #Advanced Queuing Theory Analysis #Advanced Wireless Network Optimization #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Scheduling and Optimization Algorithms
paper · pdf · doi:10.48550/arxiv.2404.17274
openalex publication_date 2024/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Goemans and Rothvoss (SODA'14) gave a framework for solving problems which can be described as finding a point in int.cone(P∩ℤN)∩ Q, where P,Q⊂ℝN are (bounded) polyhedra. The running time for solving such a problem is enc(P)^2O(N)enc(Q)O(1). This framework can be used to solve various scheduling problems, but the encoding length enc(P) usually involves large parameters like the makespan. We describe three tools to improve the framework: - Problem-specific preprocessing can be used to greatly reduce enc(P). - By solving a certain LP relaxation and then using the classical result by Frank and Tardos (J. Comb. '87), we get a more compact encoding of P in general. - A result by Jansen and Klein (SODA'17) makes the running time depend on the number of vertices of the integer hull of P. We provide a new bound for this number that is similar to the one by Berndt et al. (SOSA'21) but better for our setting. For example, applied to the scheduling problem P||Cmax, these tools improve the running time from (log(Cmax))^2O(d)enc(I)O(1) to the possibly much better (log(pmax))^2O(d)enc(I)O(1). Here, pmax is the largest processing time, d is the number of different processing times, Cmax is the makespan and enc(I) is the encoding length of the instance. On the complexity side, we use reductions from the literature to provide new parameterized lower bounds for P||Cmax. Finally, we show that the big open question asked by Mnich and van Bevern (Comput. Oper. Res. '18) whether P||Cmax is FPT w.r.t. the number of job types d has the same answer as the question whether Q||Cmax is FPT w.r.t. the number of job and machine types d+τ (all in high-multiplicity encoding). The same holds for objective Cmin.