This paper studies a scheduling problem with machine calibrations for multi-interval jobs. More exactly, there are n (possibly weighted) jobs of unit size that must be scheduled on a single initially uncalibrated machine. The machine can process jobs only when calibrated, and such a calibration lasts for T time slots. The standard model by Bender et al. [Bender MA, Bunde DP, Leung VJ, McCauley S, Phillips CA (2013) Efficient scheduling to minimize calibrations. Blelloch GE, Vöcking B, eds. 25th ACM Sympos. Parallelism Algorithms Architectures SPAA ‘13 (ACM, New York), 280–287] assumes that each job has a release time and deadline between which it must be processed. We study a generalization in which each job must be processed during one of possibly many job-dependent time intervals. We consider two objectives: In the minimization version, our goal is to minimize the number of calibrations while scheduling all jobs. In the maximization version, our goal is to maximize the total weight of scheduled jobs while using at most B calibrations. For the minimization version, we present a logarithmic approximation algorithm. We also prove that the problem is set-cover hard, implying that our algorithm is optimal up to a constant factor unless P = NP. The special case when each job may be scheduled in at most two time slots is shown to be vertex-cover hard, implying that there is no [Formula: see text]-approximation algorithm based on the unique game conjecture. For the maximization version, we give an algorithm with approximation ratio [Formula: see text]. This improves upon the previously best-known algorithm, which has an approximation ratio of 1/3 [Chau V, Feng S, Li M, Wang Y, Zhang G, Zhang Y (2019) Weighted throughput maximization with calibrations. Friggstad Z, Sack JR, Salavatipour MR, eds. Algorithms Data Structures 16th Internat. Sympos. WADS 2019 Proc., Lecture Notes in Computer Science, vol. 11646 (Springer, New York), 311–324]. Moreover, we also prove that our bound on the approximation ratio is tight. Although all hardness results mentioned above hold for any [Formula: see text], we provide optimal polynomial-time algorithms for T = 2 in both the minimization version and the maximization version. Finally, we show that our methods can be extended into the m identical machines case by losing some running time, whereas all algorithmic results remain the same in both versions. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.0430 .

Scheduling with testing falls under the umbrella of the research on optimization with explorable uncertainty. In this model, each job has an upper limit on its processing time that can be decreased to a lower limit (possibly unknown) by some preliminary action (testing). Recently, D{ü}rr et al. \cite{DBLP:journals/algorithmica/DurrEMM20} has studied a setting where testing a job takes a unit time, and the goal is to minimize total completion time or makespan on a single machine. In this paper, we extend their problem to the budget setting in which each test consumes a job-specific cost, and we require that the total testing cost cannot exceed a given budget. We consider the offline variant (the lower processing time is known) and the oblivious variant (the lower processing time is unknown) and aim to minimize the total completion time or makespan on a single machine. For the total completion time objective, we show NP-hardness and derive a PTAS for the offline variant based on a novel LP rounding scheme. We give a $(4+ε)$-competitive algorithm for the oblivious variant based on a framework inspired by the worst-case lower-bound instance. For the makespan objective, we give an FPTAS for the offline variant and a $(2+ε)$-competitive algorithm for the oblivious variant. Our algorithms for the oblivious variants under both objectives run in time $O(poly(n/ε))$. Lastly, we show that our results are essentially optimal by providing matching lower bounds.

Consider a set P of points in the unit square U = [1,0), one of them being the origin. For each point p ∈ P you may draw an axis-aligned rectangle in U with its lower-left corner being p. What is the maximum area such rectangles can cover without overlapping each other? Freedman posed this problem in 1969, asking whether one can always cover at least 50% of U. Over 40 years later, Dumitrescu and Tóth [Adrian Dumitrescu and Csaba D. Tóth, 2015] achieved the first constant coverage of 9.1%; since then, no significant progress was made. While 9.1% might seem low, the authors could not find any instance where their algorithm covers less than 50%, nourishing the hope to eventually prove a 50% bound. While we indeed significantly raise the algorithm’s coverage to 39%, we extinguish the hope of reaching 50% by giving points for which its coverage stays below 43.3%. Our analysis studies the algorithm’s average and worst-case density of so-called tiles, which represent the staircase polygons in which a point can freely choose its maximum-area rectangle. Our approach is comparatively general and may potentially help in analyzing related algorithms.

In the Anchored Rectangle Packing (ARP) problem, we are given a set of points P in the unit square [0,1]^2 and seek a maximum-area set of axis-aligned interior-disjoint rectangles S, each of which is anchored at a point p in P. In the most prominent variant - Lower-Left-Anchored Rectangle Packing (LLARP) - rectangles are anchored in their lower-left corner. Freedman [W. T. Tutte (Ed.), 1969] conjectured in 1969 that, if (0,0) in P, then there is a LLARP that covers an area of at least 0.5. Somewhat surprisingly, this conjecture remains open to this day, with the best known result covering an area of 0.091 [Dumitrescu and Tóth, 2015]. Maybe even more surprisingly, it is not known whether LLARP - or any ARP-problem with only one anchor - is NP-hard. In this work, we first study the Center-Anchored Rectangle Packing (CARP) problem, where rectangles are anchored in their center. We prove NP-hardness and provide a PTAS. In fact, our PTAS applies to any ARP problem where the anchor lies in the interior of the rectangles. Afterwards, we turn to the LLARP problem and investigate two different resource-augmentation settings: In the first we allow an epsilon-perturbation of the input P, whereas in the second we permit an epsilon-overlap between rectangles. For the former setting, we give an algorithm that covers at least as much area as an optimal solution of the original problem. For the latter, we give an (1 - epsilon)-approximation.