The \(\ell\)-matroid intersection (\(\ell\)-MI) problem asks if \(\ell\) given matroids share a common basis. Already for \(\ell = 3\), notable canonical NP-complete special cases are 3-Dimensional Matching and Hamiltonian Path on directed graphs. However, while these problems admit exponential-time algorithms that improve the simple brute force significantly (e.g., Eiben-Koana-Wahlström (SODA’24)), the fastest known algorithm for 3-MI on general matroids is exactly brute force with runtime \(2^n/\mathrm{poly}(n)\), where \(n\) is the number of elements. Our main result shows that, in fact, brute force cannot be significantly improved, by ruling out an algorithm for \(\ell\)-MI with runtime \(o\left( 2^{\,n - 5 \cdot n^{\tfrac{1}{\ell-1}} \cdot \log(n)} \right)\), for any fixed \(\ell \ge 3\). For \(3\)-MI, this gives a lower bound of \(o\left( 2^{\,n - 5 \cdot \sqrt{n} \cdot \log(n)} \right)\). Our negative result raises the following natural questions: (i) Is there an algorithm for 3-MI with runtime strictly better than brute force? (ii) Can we separate the parameterized complexity of 3-MI from the important special case on linear matroids (parameterized by the rank of the matroids \(k\))? In particular, can a lower bound match the existing \(c^{k^2} \cdot \mathrm{poly}(n)\) algorithm of Huang-Ward (SIDMA’23) for general \(\ell\)-MI parameterized by the rank? We make progress towards obtaining affirmative answers to the above questions. In particular, we present (i) an algorithm which solves \(\ell\)-MI faster than brute force in time \(2^{\,n - \Omega((\log^2 n))}\) for any \(\ell \ge 3\), and (ii) a parameterized running time lower bound of \(2^{(\ell-2)\cdot k \cdot \log k} \cdot \mathrm{poly}(n)\) for \(\ell\)-MI, for any \(\ell \ge 3\). We obtain these results by generalizing the Monotone Local Search technique of Fomin-Gaspers-Lokshtanov-Saurabh (J. ACM’19). Broadly speaking, given a subset problem, our generalization transforms any algorithm parameterized by solution size, with runtime of the form \(f(k) \cdot \mathrm{poly}(n)\), into an exponential-time algorithm with runtime depending on \(f\). This implies that any \(f(k) \cdot \mathrm{poly}(n)\) time parameterized algorithm for a subset problem yields a \(2^{\,n - \omega(\log n)}\) time algorithm beating brute force, which may be of independent interest.

We study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements that optimizes (i.e., maximizes or minimizes) a linear objective function simultaneously subject to (i) a matroid independent set, or a matroid basis constraint and (ii) additional linear constraint. A notable member in this family is budgeted matroid independent set (BM) , which can be viewed as classic \(0/1\) -knapsack with a matroid constraint. While special cases of BM, such as knapsack with cardinality constraint and multiple-choice knapsack , admit a fully polynomial-time approximation scheme (Fully PTAS), the best-known result for BM on a general matroid is an Efficient PTAS. Prior to this work, the existence of a Fully PTAS for BM, and more generally, for any problem in the family of MOL problems, has been open. In this article, we answer this question negatively by showing that none of the (non-trivial) problems in this family admits a Fully PTAS. This resolves the complexity status of several well-studied problems. Our main result is obtained by showing first that exact weight matroid basis (EMB) does not admit a pseudo-polynomial time algorithm. We then obtain unconditional hardness results for the family of MOL problems in the oracle model (even if randomization is allowed) and show that the same results hold when the matroids are encoded as part of the input, assuming \(\text{P}\neq\text{NP}\) .

We consider a spatial voting model where candidates and voters are positioned in $d$-dimensional Euclidean space, and each voter ranks candidates based on their proximity to the voter's ideal point. We focus on the scenario where information about voters' ideal points is incomplete; for each dimension, only an interval of possible values is known. Here, we investigate the computational complexity of determining possible winners under positional scoring rules. We show the possible winner problem in one dimension is solvable in polynomial time for all $k$-truncated voting rules with constant $k$. For some scoring rules where the problem is NP-complete, such as approval voting for any dimension or $k$-approval for $d \geq 2$, we give an FPT algorithm parameterized by the number of candidates. Finally, we classify tractable and intractable settings of the weighted possible winner problem in one dimension, resolving the complexity for all two-valued positional scoring rules when $d=1$.

We consider spatial voting where candidates are located in the Euclidean d-dimensional space, and each voter ranks candidates based on their distance from the voter's ideal point. We explore the case where information about the location of voters' ideal points is incomplete: for each dimension, we are given an interval of possible values. We study the computational complexity of finding the possible and necessary winners for positional scoring rules. Our results show that we retain tractable cases of the classic model where voters have partial-order preferences. Moreover, we show that there are positional scoring rules under which the possible-winner problem is intractable for partial orders, but tractable in the one-dimensional spatial setting. We also consider approval voting in this setting. We show that for up to two dimensions, the necessary-winner problem is tractable, while the possible-winner problem is hard for any number of dimensions.

In [Math. Oper. Res., 2011], Fleischer et al. introduced a powerful technique for solving the generic class of separable assignment problems (SAP), in which a set of items of given values and weights needs to be packed into a set of bins subject to separable assignment constraints, so as to maximize the total value. The approach of Fleischer at al. relies on solving a configuration LP and sampling a configuration for each bin independently based on the LP solution. While there is a SAP variant for which this approach yields the best possible approximation ratio, for various special cases, there are discrepancies between the approximation ratios obtained using the above approach and the state-of-the-art approximations. This raises the following natural question: Can we do better by iteratively solving the configuration LP and sampling a few bins at a time? To assess the potential of the iterative approach we consider a specific SAP variant as a case-study, Uniform Cardinality Constrained Multiple Knapsack, for which we answer this question affirmatively. The input is a set of items, each has a value and a weight, and a set of uniform capacity bins. The goal is to assign a subset of the items of maximum total value to the bins such that (i) the capacity of any bin is not exceeded, and (ii) the number of items assigned to each bin satisfies a given cardinality constraint. While the technique of Fleischer et al. yields a (1-1/e)-approximation for the problem, we show that iterative randomized rounding leads to efficient polynomial time approximation scheme (EPTAS), thus essentially resolving the complexity status of the problem. Our analysis of iterative randomized rounding may be useful for solving other SAP variants.

We study a family of matroid optimization problems with a linear constraint (MOL). In these problems, we seek a subset of elements which optimizes (i.e., maximizes or minimizes) a linear objective function subject to (i) a matroid independent set, or a matroid basis constraint, (ii) additional linear constraint. A notable member in this family is budgeted matroid independent set (BM), which can be viewed as classic $0/1$-knapsack with a matroid constraint. While special cases of BM, such as knapsack with cardinality constraint and multiple-choice knapsack, admit a fully polynomial-time approximation scheme (Fully PTAS), the best known result for BM on a general matroid is an Efficient PTAS. Prior to this work, the existence of a Fully PTAS for BM, and more generally, for any problem in the family of MOL problems, has been open. In this paper, we answer this question negatively by showing that none of the (non-trivial) problems in this family admits a Fully PTAS. This resolves the complexity status of several well studied problems. Our main result is obtained by showing first that exact weight matroid basis (EMB) does not admit a pseudo-polynomial time algorithm. This distinguishes EMB from the special cases of $k$-subset sum and EMB on a linear matroid, which are solvable in pseudo-polynomial time. We then obtain unconditional hardness results for the family of MOL problems in the oracle model (even if randomization is allowed), and show that the same results hold when the matroids are encoded as part of the input, assuming $P \neq NP$. For the hardness proof of EMB, we introduce the $Π$-matroid family. This intricate subclass of matroids, which exploits the interaction between a weight function and the matroid constraint, may find use in tackling other matroid optimization problems.

We consider the Bin Packing problem with a partition matroid constraint. The input is a set of items of sizes in [0,1], and a partition matroid over the items. The goal is to pack the items in a minimum number of unit-size bins, such that each bin forms an independent set in the matroid. This variant of classic Bin Packing has natural applications in secure storage on the Cloud, as well as in equitable scheduling and clustering with fairness constraints. Our main result is an asymptotic fully polynomial-time approximation scheme (AFPTAS) for Bin Packing with a partition matroid constraint. This scheme generalizes the known AFPTAS for Bin Packing with Cardinality Constraints and improves the existing asymptotic polynomial-time approximation scheme (APTAS) for Group Bin Packing, which are both special cases of Bin Packing with partition matroid. We derive the scheme via a new method for rounding a (fractional) solution for a configuration-LP. Our method uses this solution to obtain prototypes, in which items are interpreted as placeholders for other items, and applies fractional grouping to modify a fractional solution (prototype) into one having desired integrality properties.

We study the d-DIMENSIONAL VECTOR BIN PACKING ($d \mathbf{V B P})$ problem, a generalization of BIN PACKING with central applications in resource allocation and scheduling. In $d \mathrm{VBP}$, we are given a set of items, each of which is characterized by a d-dimensional volume vector; the objective is to partition the items into a minimum number of subsets (bins), such that the total volume of items in each subset is at most 1 in each dimension. Our main result is an asymptotic approximation algorithm for d VBP that yields a ratio of $(1+\ln d-\chi(d)+\varepsilon)$ for all $d \in \mathbb{N}$ and any $\varepsilon\gt0$; here, $\chi(d)$ is some strictly positive function. This improves upon the best known asymptotic ratio of $(1+\ln d+\varepsilon)$ due to Bansal, Caprara and Sviridenko (SICOMP 2010) for any $d\gt3$. By slightly modifying our algorithm to include an initial matching phase and applying a tighter analysis, we obtain an asymptotic approximation ratio of $\left(\frac{4}{3}+\varepsilon\right)$ for the special case of $d=2$, thus substantially improving the previous best ratio of $\left(\frac{3}{2}+\varepsilon\right)$ due to Bansal, Eliáš and Khan (SODA 2016). Our algorithm iteratively solves a configuration LP relaxation for the residual instance (from previous iterations) and samples a small number of configurations based on the solution for the configuration LP. While iterative rounding was already used by Karmarkar and Karp (FOCS 1982) to establish their celebrated result for classic (one-dimensional) BIN PACKING, iterative randomized rounding is used here for the first time in the context of (VECTOR) BIN PACKING. Our results show that iterative randomized rounding is a powerful tool for approximating d VBP, leading to simple algorithms with improved approximation guarantees.

We consider the budgeted matroid independent set problem. The input is a ground set, where each element has a cost and a non-negative profit, along with a matroid over the elements and a budget. The goal is to select a subset of elements which maximizes the total profit subject to the matroid and budget constraints. Several well known special cases, where we have, e.g., a uniform matroid and a budget, or no matroid constraint (i.e., the classic knapsack problem), admit a fully polynomial-time approximation scheme (FPTAS). In contrast, already a slight generalization to the multi-budgeted matroid independent set problem has a PTAS but does not admit an efficient polynomial-time approximation scheme (EPTAS). This implies a PTAS for our problem, which is the best known result prior to this work. Our main contribution is an EPTAS for the budgeted matroid independent set problem. A key idea of the scheme is to find a representative set for the instance, whose cardinality depends solely on $1/\varepsilon$, where $\varepsilon > 0$ is the accuracy parameter of the scheme. The representative set is identified via matroid basis minimization, which can be solved by a simple greedy algorithm. Our scheme enumerates over subsets of the representative set and extends each subset using a linear program. The notion of representative sets may be useful in solving other variants of the budgeted matroid independent set problem.

We study the uniform $2$-dimensional vector multiple knapsack (2VMK) problem, a natural variant of multiple knapsack arising in real-world applications such as virtual machine placement. The input for 2VMK is a set of items, each associated with a $2$-dimensional weight vector and a positive profit, along with $m$ $2$-dimensional bins of uniform (unit) capacity in each dimension. The goal is to find an assignment of a subset of the items to the bins, such that the total weight of items assigned to a single bin is at most one in each dimension, and the total profit is maximized. Our main result is a $(1- \frac{\ln 2}{2} - \varepsilon)$-approximation algorithm for 2VMK, for every fixed $\varepsilon > 0$, thus improving the best known ratio of $(1 - \frac{1}{e}-\varepsilon)$ which follows as a special case from a result of [Fleischer at al., MOR 2011]. Our algorithm relies on an adaptation of the Round$\&$Approx framework of [Bansal et al., SICOMP 2010], originally designed for set covering problems, to maximization problems. The algorithm uses randomized rounding of a configuration-LP solution to assign items to $\approx m\cdot \ln 2 \approx 0.693\cdot m$ of the bins, followed by a reduction to the ($1$-dimensional) Multiple Knapsack problem for assigning items to the remaining bins.

We study budgeted variants of well known maximization problems with multiple matroid constraints. Given an 𝓁-matchoid ℳ on a ground set E, a profit function p:E → ℝ_{≥ 0}, a cost function c:E → ℝ_{≥ 0}, and a budget B ∈ ℝ_{≥ 0}, the goal is to find in the 𝓁-matchoid a feasible set S of maximum profit p(S) subject to the budget constraint, i.e., c(S) ≤ B. The budgeted 𝓁-matchoid (BM) problem includes as special cases budgeted 𝓁-dimensional matching and budgeted 𝓁-matroid intersection. A strong motivation for studying BM from parameterized viewpoint comes from the APX-hardness of unbudgeted 𝓁-dimensional matching (i.e., B = ∞) already for 𝓁 = 3. Nevertheless, while there are known FPT algorithms for the unbudgeted variants of the above problems, the budgeted variants are studied here for the first time through the lens of parameterized complexity. We show that BM parametrized by solution size is W[1]-hard, already with a degenerate single matroid constraint. Thus, an exact parameterized algorithm is unlikely to exist, motivating the study of FPT-approximation schemes (FPAS). Our main result is an FPAS for BM (implying an FPAS for 𝓁-dimensional matching and budgeted 𝓁-matroid intersection), relying on the notion of representative set - a small cardinality subset of elements which preserves the optimum up to a small factor. We also give a lower bound on the minimum possible size of a representative set which can be computed in polynomial time.

A multiple knapsack constraint over a set of items is defined by a set of bins of arbitrary capacities, and a weight for each of the items. An assignment for the constraint is an allocation of subsets of items to the bins which adheres to bin capacities. In this paper we present a unified algorithm that yields efficient approximations for a wide class of submodular and modular optimization problems involving multiple knapsack constraints. One notable example is a polynomial time approximation scheme for Multiple-Choice Multiple Knapsack, improving upon the best known ratio of $2$. Another example is Non-monotone Submodular Multiple Knapsack, for which we obtain a $(0.385-\varepsilon)$-approximation, matching the best known ratio for a single knapsack constraint. The robustness of our algorithm is achieved by applying a novel fractional variant of the classical linear grouping technique, which is of independent interest.

We consider scheduling real-time jobs in the classic flow shop model. The input is a set of n jobs, each consisting of m segments to be processed on m machines in the specified order, such that segment I_i of a job can start processing on machine M_i only after segment I_{i-1} of the same job completed processing on machine M_{i-1}, for 2 ≤ i ≤ m. Each job also has a release time, a due date, and a weight. The objective is to maximize the throughput (or, profit) of the n jobs, i.e., to find a subset of the jobs that have the maximum total weight and can complete processing on the m machines within their time windows. This problem has numerous real-life applications ranging from manufacturing to cloud and embedded computing platforms, already in the special case where m = 2. Previous work in the flow shop model has focused on makespan, flow time, or tardiness objectives. However, little is known for the flow shop model in the real-time setting. In this work, we give the first nontrivial results for this problem and present a pseudo-polynomial time (2m+1)-approximation algorithm for the problem on m ≥ 2 machines, where m is a constant. This ratio is essentially tight due to a hardness result of Ω(m/(log m)) for the approximation ratio. We further give a polynomial-time algorithm for the two-machine case, with an approximation ratio of (9+ε) where ε = O(1/n). We obtain better bounds for some restricted subclasses of inputs with two machines. To the best of our knowledge, this fundamental problem of throughput maximization in the flow shop scheduling model is studied here for the first time.

We study the problem of maximizing a monotone submodular function subject to a Multiple Knapsack constraint (SMKP). The input is a set I of items, each associated with a non-negative weight, and a set of bins having arbitrary capacities. Also, we are given a submodular, monotone and non-negative function f over subsets of the items. The objective is to find a subset of items A ⊆ I and a packing of these items in the bins, such that f(A) is maximized. SMKP is a natural extension of both Multiple Knapsack and the problem of monotone submodular maximization subject to a knapsack constraint. Our main result is a nearly optimal polynomial time (1-e^{-1}-ε)-approximation algorithm for the problem, for any ε > 0. Our algorithm relies on a refined analysis of techniques for constrained submodular optimization combined with sophisticated application of tools used in the development of approximation schemes for packing problems.

In this paper we introduce randomized branching as a tool for parameterized approximation and develop the mathematical machinery for its analysis. Our algorithms substantially improve the best known running times of parameterized approximation algorithms for Vertex Cover and 3-Hitting Set for a wide range of approximation ratios. The running times of our algorithms are derived from an asymptotic analysis of a broad class of two-variable recurrence relations. Our main theorem gives a simple formula for this asymptotics. The formula can be efficiently calculated by solving a simple numerical optimization problem, and provides the mathematical insight required for the algorithm design. To this end, we show an equivalence between the recurrence and a stochastic process. We analyze this process using the method of types, by introducing an adaptation of Sanov's theorem to our setting. We believe our novel analysis of recurrence relations which is of independent interest is a main contribution of this paper.

We study a variant of the generalized assignment problem (GAP) with group constraints. An instance of (Group GAP) is a set I of items, partitioned into L groups, and a set of m uniform (unit-sized) bins. Each item i in I has a size s_i >0, and a profit p_{i,j} >= 0 if packed in bin j. A group of items is satisfied if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total profit from satisfied groups is maximized. We point to central applications of Group GAP in Video-on-Demand services, mobile Device-to-Device network caching and base station cooperation in 5G networks. Our main result is a 1/6-approximation algorithm for Group GAP instances where the total size of each group is at most m/2. At the heart of our algorithm lies an interesting derivation of a submodular function from the classic LP formulation of GAP, which facilitates the construction of a high profit solution utilizing at most half the total bin capacity, while the other half is reserved for later use. In particular, we give an algorithm for submodular maximization subject to a knapsack constraint, which finds a solution of profit at least 1/3 of the optimum, using at most half the knapsack capacity, under mild restrictions on element sizes. Our novel approach of submodular optimization subject to a knapsack with reserved capacity constraint may find applications in solving other group assignment problems.

We revisit a classical scheduling model to incorporate modern trends in data center networks and cloud services. Addressing some key challenges in the allocation of shared resources to user requests (jobs) in such settings, we consider the following variants of the classic resource allocation problem (RAP). The input to our problems is a set J of jobs and a set M of homogeneous hosts, each has an available amount of some resource. A job is associated with a release time, a due date, a weight and a given length, as well as its resource requirement. A feasible schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. A crucial distinction between classic RAP and our problems is that we allow preemption and migration of jobs, motivated by virtualization techniques. We consider two natural objectives: throughput maximization (MaxT), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in M, and resource minimization (MinR), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We first present an Omega(1)-approximation algorithm for MaxT instances where time-windows form a laminar family of intervals. We then extend the algorithm to handle instances with arbitrary time-windows, assuming there is sufficient slack for each job to be completed. For MinR we study a more general setting with d resources and derive an O(log d)-approximation for any fixed d >= 1, under the assumption that time-windows are not too small. This assumption can be removed leading to a slightly worse ratio of O(log d log^* T), where T is the maximum due date of any job.

We study the generalized assignment problem with time-sensitive item groups (chi-AGAP). It has central applications in advertisement placement on the Internet, and in virtual network embedding in Cloud data centers. We are given a set of items, partitioned into n groups, and a set of T identical bins (or, time-slots). Each group 1 <= j <= n has a time-window chi_j = [r_j, d_j]subseteq [T] in which it can be packed. Each item i in group j has a size s_i>0 and a non-negative utility u_{it} when packed into bin t in chi_j. A bin can accommodate at most one item from each group and the total size of the items in a bin cannot exceed its capacity. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from groups that are completely packed is maximized. Our main result is an Omega(1)-approximation algorithm for chi-AGAP. Our approximation technique relies on a non-trivial rounding of a configuration LP, which can be adapted to other common scenarios of resource allocation in Cloud data centers.

Cloud services require the allocation of scarce resources to multiple user requests (jobs) in a setting that facilitates preemption and migration while respecting resource and timing constraints. This gives rise to the following variants of the classical \em resource allocation problem (RAP). The input is a set J of jobs and a set M of homogeneous hosts, each has available amount of some resource. A job is associated with a release time, a due date, a weight and a given length, as well as its resource requirement. A feasible schedule is an allocation of the resource to a subset of the jobs, satisfying the job release times/due dates as well as the resource constraints. We consider two essential objectives: \em throughput maximization (MaxT), which seeks a maximum weight subset of the jobs that can be feasibly scheduled on the hosts in M , and \em resource minimization (MinM), that is finding the minimum number of (homogeneous) hosts needed to feasibly schedule all jobs. Both problems are known to be NP-hard. We address these fundamental problems, which have been studied previously in the \em non-preemptive model, and develop novel techniques for tackling them. In the full version of the paper, we present an $Ømega(1)$-approximation algorithm for MaxT, assuming there is sufficient slack for each job to be completed in its time window. For MinM, we study a more general setting with d resources and derive an $O(łog d)$-approximation for any fixed $d \geq 1$, under the assumption that time windows are not too small. This assumption can be removed, leading to a slightly worse ratio of $O(łog dłog^* T)$, where T is the maximum due date of any job.

We consider a variant of the classic real-time scheduling problem, which has natural applications in cloud computing. The input consists of a set of jobs, and an integer parameter k ≥ 1. Each job is associated with a processing time, a release time, a due-date and a positive weight. The goal is to feasibly schedule a subset of the jobs of maximum total weight on a single machine, such that each of the jobs is preempted at most k times. Our theoretical results for the real-time k-bounded preemptive scheduling problem include hardness proofs, as well as algorithms for subclasses of instances, for which we derive constant-ratio performance guarantees. We bridge the gap between theory and practice through a comprehensive experimental study, in which we also test the performance of several heuristics for general instances on multiple parallel machines. We use in the experiments a linear programming relaxation to upper bound the optimal solution for a given instance. Our results show that while k-bounded preemptive scheduling is hard to solve already on highly restricted instances, simple priority-based heuristics yield almost optimal schedules for realistic inputs and arbitrary values of k.

Motivated by the cloud computing paradigm, and by key optimization problems in all-optical networks, we study two variants of the classic job interval scheduling problem, where a reusable resource is allocated to competing job intervals in a flexible manner. Each job, Ji, requires the use of up to rmax(i) units of the resource, with a profit of pi ≥ 1 accrued for each allocated unit. The goal is to feasibly schedule a subset of the jobs so as to maximize the total profit. The resource can be allocated either in contiguous or non-contiguous blocks. These problems can be viewed as flexible variants of the well known storage allocation and bandwidth allocation problems.

We study a variant of the generalized assignment problem ( gap ), which we label all-or-nothing gap ( agap ). We are given a set of items, partitioned into n groups, and a set of m bins. Each item ℓ has size s ℓ > 0, and utility a ℓ j ⩾ 0 if packed in bin j . Each bin can accommodate at most one item from each group; the total size of the items in a bin cannot exceed its capacity. A group of items is satisfied if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from satisfied groups is maximized. We motivate the study of agap by pointing out a central application in scheduling advertising campaigns. Our main result is an O (1)-approximation algorithm for agap instances arising in practice, in which each group consists of at most m /2 items. Our algorithm uses a novel reduction of agap to maximizing submodular function subject to a matroid constraint. For agap instances with a fixed number of bins, we develop a randomized polynomial time approximation scheme (PTAS) , relying on a nontrivial LP relaxation of the problem. We present a (3 + ε)-approximation as well as PTASs for other special cases of agap , where the utility of any item does not depend on the bin in which it is packed. Finally, we derive hardness results for the different variants of agap studied in this paper.

We introduce and study a network resource management problem that is a special case of non-metric k-median, naturally arising in cross platform scheduling and cloud computing. In the continuous d-dimensional container selection problem, we are given a set C of input points in d-dimensional Euclidean space, for some d >= 2, and a budget k. An input point p can be assigned to a "container point" c only if c dominates p in every dimension. The assignment cost is then equal to the L1-norm of the container point. The goal is to find k container points in the d-dimensional space, such that the total assignment cost for all input points is minimized. The discrete variant of the problem has one key distinction, namely, the container points must be chosen from a given set F of points. For the continuous version, we obtain a polynomial time approximation scheme for any fixed dimension d>= 2. On the negative side, we show that the problem is NP-hard for any d>=3. We further show that the discrete version is significantly harder, as it is NP-hard to approximate without violating the budget k in any dimension d>=3. Thus, we focus on obtaining bi-approximation algorithms. For d=2, the bi-approximation guarantee is (1+epsilon,3), i.e., for any epsilon>0, our scheme outputs a solution of size 3k and cost at most (1+epsilon) times the optimum. For fixed d>2, we present a (1+epsilon,O((1/epsilon)log k)) bi-approximation algorithm.

We consider a job-scheduling problem arising on cloud systems and in broadcasting networks, where the goal is to optimally utilize a limited amount of a resource (e.g., cloud servers, bandwidth, or storage capacity) available along a given time interval. The resource is utilized by a set of weighted jobs. The processing of a job consists of several contiguous stages, each having a specific length and a specific resource-demand, such that the set of demands forms a decreasing sequence. Each job is associated with a release time and a deadline, defining the time interval in which it can be processed. Some notable applications for this scenario include progressive download, QuickStart and prefetching methods, hierarchical image reconstruction, and routine security and maintenance tasks. The goal is to find a feasible schedule of a maximum-weight subset of the jobs. In a feasible schedule, at any time, the total amount of resource allocated to the active jobs does not exceed the available amount of resource. Since this problem is NP-hard already for highly restricted inputs, we focus on obtaining approximation algorithms and heuristics and present a comparative study among them. Our main result, the first constant-factor approximation algorithm for the problem, generalizes the state of art for the fundamental problem of resource constrained real-time scheduling, to scenarios where jobs may have dwindling resource requirements. Our empirical study shows that this algorithm is in fact nearly optimal for realistic inputs.

All-optical networks have been largely investigated due to their high data transmission rates. In the traditional Wavelength-Division Multiplexing (WDM) technology, the spectrum of light that can be transmitted through the optical fiber has been divided into frequency intervals of fixed width, with a gap of unused frequencies between them. Recently, an alternative emerging architecture was suggested which moves away from the rigid Dense WDM (DWDM) model towards a flexible model, where usable frequency intervals are of variable width (even within the same link). Each light path has to be assigned a frequency interval (sub-spectrum), which remains fixed through all of the links it traverses. Two different light paths using the same link must be assigned disjoint sub-spectra. This technology is termed flex-grid (or, flex-spectrum), as opposed to fixed-grid (or, fixed-spectrum) current technology. In this work we study a problem of optimal bandwidth allocation arising in the flex-grid technology. In this setting, each light path has a lower and upper bound on the width of its frequency interval, as well as an associated profit, and we want to find a bandwidth assignment that maximizes the total profit. This problem is known to be NP-Complete. We observe that, in fact, the problem is inapproximable within any constant ratio even on a path network. We further derive NP-hardness results and present approximation algorithms for several special cases of the path and ring networks, which are of practical interest. Finally, while in general our problem is hard to approximate, we show that an optimal solution can be obtained by allowing resource augmentation. Our study has applications also in real time scheduling.

In Gandhi et al. [2006], we gave an algorithm for the data migration and non-deterministic open shop scheduling problems in the minimum sum version, that was claimed to achieve a 5.06-approximation. Unfortunately, it was pointed to us by Maxim Sviridenko that the argument contained an unfounded assumption that has eluded all of its readers until now. We detail in this document how this error can be amended. A side effect is an improved approximation ratio of 4.96.

Gathering data from nodes in a network is at the heart of many distributed applications, most notably while performing a global task. We consider information spreading among $n$ nodes of a network, where each node $v$ has a message $m(v)$ which must be received by all other nodes. The time required for information spreading has been previously upper-bounded with an inverse relationship to the conductance of the underlying communication graph. This implies high running time bounds for graphs with small conductance. The main contribution of this paper is an information spreading algorithm which overcomes communication bottlenecks and thus achieves fast information spreading for a wide class of graphs, despite their small conductance. As a key tool in our study we use the recently defined concept of weak conductance, a generalization of classic graph conductance which measures how well-connected the components of a graph are. Our hybrid algorithm, which alternates between random and deterministic communication phases, exploits the connectivity within components by first applying partial information spreading, in which information is exchanged within well-connected components, and then sending messages across bottlenecks, thus spreading further throughout the network. This yields substantial improvements over the best known running times of algorithms for information spreading on any graph that has large weak conductance, from a polynomial to a polylogarithmic number of rounds.

Gathering data from nodes in a network is at the heart of many distributed applications, most notably, while performing a global task. We consider information spreading among n nodes of a network, where each node v has a message m(v) which must be received by all other nodes. The time required for information spreading has been previously upper-bounded with an inverse relationship to the conductance of the underlying communication graph. This implies high running times for graphs with small conductance. The main contribution of this paper is an information spreading algorithm which overcomes communication bottlenecks and thus achieves fast information spreading for a wide class of graphs, despite their small conductance. As a key tool in our study we use the recently defined concept of weak conductance, a generalization of classic graph conductance which measures how well-connected the components of a graph are. Our hybrid algorithm, which alternates between random and deterministic communication phases, exploits the connectivity within components by first applying partial information spreading, after which messages are sent across bottlenecks, thus spreading further throughout the network. This yields substantial improvements over the best known running times of algorithms for information spreading on any graph that has a large weak conductance, from polynomial to polylogarithmic number of rounds. We demonstrate the power of fast information spreading in accomplishing global tasks on the leader election problem, which lies at the core of distributed computing. Our results yield an algorithm for leader election that has a scalable running time on graphs with large weak conductance, improving significantly upon previous results.

We consider the following fundamental scheduling problem. The input consists of $n$ jobs to be scheduled on a set of machines of bounded capacities. Each job is associated with a release time, a due date, a processing time and demand for machine capacity. The goal is to schedule all of the jobs non-preemptively in their release-time-deadline windows, subject to machine capacity constraints, such that the total busy time of the machines is minimized. Our problem has important applications in power-aware scheduling, optical network design and unit commitment in power systems. Scheduling to minimize busy times is APX-hard already in the special case where all jobs have the same (unit) processing times and can be scheduled in a fixed time interval. Our main result is a $5$-approximation algorithm for general instances. We extend this result to obtain an algorithm with the same approximation ratio for the problem of scheduling moldable jobs, that requires also to determine, for each job, one of several processing-time vs. demand configurations. Better bounds and exact algorithms are derived for several special cases, including proper interval graphs, intervals forming a clique and laminar families of intervals.

This paper addresses partial information spreading among n nodes of a network. As opposed to traditional information spreading, where each node has a message that must be received by all nodes, we propose a relaxed requirement, where only n/c nodes need to receive each message, and every node should receive n/c messages, for some c ≥ 1.

We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of n jobs J = {J1,..., Jn}. Each job, Jj, is associated with an interval [sj, cj] along which it should be processed. Also given is the parallelism parameter g ges 1, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its busy interval, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines such that the total busy time of the machines is minimized. The problem is known to be NP-hard already for g = 2. We present a 4-approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has important application in optimizing the switching costs of optical networks.

The concept of submodularity plays a vital role in combinatorial optimization. In particular, many important optimization problems can be cast as submodular maximization problems, including maximum coverage, maximum facility location and max cut in directed/undirected graphs. In this paper we present the first known approximation algorithms for the problem of maximizing a non-decreasing submodular set function subject to multiple linear constraints. Given a d-dimensional budget vector , for some d ≥ 1, and an oracle for a non-decreasing submodular set function f over a universe U, where each element e ∊ U is associated with a d-dimensional cost vector, we seek a subset of elements S ⊆ U whose total cost is at most , such that f(S) is maximized. We develop a framework for maximizing submodular functions subject to d linear constraints that yields a (1 – ∊)(1 – e−-1)-approximation to the optimum for any ∊ > 0, where d > 1 is some constant. Our study is motivated by a variant of the classical maximum coverage problem that we call maximum coverage with multiple packing constraints. We use our framework to obtain the same approximation ratio for this problem. To the best of our knowledge, this is the first time the theoretical bound of 1 – e−-1 is (almost) matched for both of these problems.

We consider the following scheduling with batching problem that has many applications, for example, in multimedia-on-demand and manufacturing of integrated circuits. The input to the problem consists of n jobs and k parallel machines. Each job is associated with a set of time intervals in which it can be scheduled (given either explicitly or nonexplicitly), a weight, and a family. Each family is associated with a processing time. Jobs that belong to the same family can be batched and executed together on the same machine. The processing time of each batch is the processing time of the family of jobs it contains. The goal is to find a nonpreemptive schedule with batching that maximizes the weight of the scheduled jobs. We give constant factor (4 or 4 + ε) approximation algorithms for two variants of the problem, depending on the precise representation of the input. When the batch size is unbounded and each job is associated with a time window in which it can be processed, these approximation ratios reduce to 2 and 2 + ε, respectively. We also give approximation algorithms for two special cases when all release times are the same.

Abstract We consider the master ring problem (MRP) which often arises in optical network design. Given a network which consists of a collection of interconnected rings R1,…,RK, with n1,…,nK distinct nodes, respectively, we need to find an ordering of the nodes in the network that respects the ordering of every individual ring, if one exists. We show that MRP is NP‐complete, and therefore, it is unlikely to be solvable by a polynomial time algorithm. Our main result is an algorithm which solves MRP in $ Q \cdot \Pi_{k=1}^{K} (n_{k}/\sqrt{2}) $ steps, for some polynomial Q, as the nk values become large. For the ring clearance problem, a special case of practical interest, our algorithm achieves this running time for rings of any size nk ≥ 2. This yields the first nontrivial improvement, by factor of $ (2\sqrt{2})^{K} \approx (2.82)^{K} $ , over the running time of the naive algorithm, which exhaustively enumerates all $ \Pi_{k=1}^{K} (2n_{k}) $ possible solutions. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

We consider a general class of scheduling problems where a set of conflicting jobs needs to be scheduled (preemptively or nonpreemptively) on a set of machines so as to minimize the weighted sum of completion times. The conflicts among jobs are formed as an arbitrary conflict graph. Building on the framework of Queyranne and Sviridenko [2002b], we present a general technique for reducing the weighted sum of completion-times problem to the classical makespan minimization problem. Using this technique, we improve the best-known results for scheduling conflicting jobs with the min-sum objective, on several fundamental classes of graphs, including line graphs, ( k + 1)-claw-free graphs, and perfect graphs. In particular, we obtain the first constant-factor approximation ratio for nonpreemptive scheduling on interval graphs. We also improve the results of Kim [2003] for scheduling jobs on line graphs and for resource-constrained scheduling.

The transactional approach to contention management guarantees atomicity by making sure that whenever two transactions have a conflict on a resource, only one of them proceeds. A major challenge in implementing this approach lies in guaranteeing progress, since transactions are often restarted.Inspired by the paradigm of non-clairvoyant job scheduling, we analyze the performance of a contention manager by comparison with an optimal, clairvoyant contention manager that knows the list of resource accesses that will be performed by each transaction, as well as its release time and duration. The realistic, non-clairvoyant contention manager is evaluated by the competitive ratio between the last completion time (makespan) it provides and the makespan provided by an optimal contention manager.Assuming that the amount of exclusive accesses to the resources is non-negligible, we present a simple proof that every work conserving contention manager guaranteeing the pending commit property achieves an O(s) competitive ratio, where s is the number of resources. This bound holds for the GREEDY contention manager studied by Guerraoui et al. [2] and is a significant improvement over the O(s2) bound they prove for the competitive ratio of GREEDY. We show that this bound is tight for any deterministic contention manager, and under certain assumptions about the transactions, also for randomized contention managers.When transactions may fail, we show that a simple adaptation of GREEDY has a competitive ratio of at most O(ks), assuming that a transaction may fail at most k times. If a transaction can modify its resource requirements when re-invoked, then any deterministic algorithm has a competitive ratio Ω(ks). For the case of unit length jobs, we give (almost) matching lower and upper bounds.

We consider the problem of scheduling jobs that are given as groups of nonintersecting segments on the real line. Each job $J_j$ is associated with an interval, $I_j$, which consists of up to t segments, for some $t \geq 1$, and a weight (profit), $w_j$; two jobs are in conflict if their intervals intersect. Such jobs show up in a wide range of applications, including the transmission of continuous-media data, allocation of linear resources (e.g., bandwidth in linear processor arrays), and computational biology/geometry. The objective is to schedule a subset of nonconflicting jobs of maximum total weight. Our problem can be formulated as the problem of finding a maximum weight independent set in a t-interval graph (the special case of $t=1$ is an ordinary interval graph). We show that, for $t \geq 2$, this problem is APX-hard, even for highly restricted instances. Our main result is a $2t$-approximation algorithm for general instances. This is based on a novel fractional version of the Local Ratio technique. One implication of this result is the first constant factor approximation for nonoverlapping alignment of genomic sequences. We also derive a bicriteria polynomial time approximation scheme for a restricted subclass of t-interval graphs.

The data migration problem is to compute an efficient plan for moving data stored on devices in a network from one configuration to another. We consider this problem with the objective of minimizing the sum of completion times of all storage devices. It is modeled by a transfer graph, where vertices represent the storage devices, and the edges indicate the data transfers required between pairs of devices. Each vertex has a nonnegative weight, and each edge has a release time and a processing time. A vertex completes when all the edges incident on it complete; the constraint is that two edges incident on the same vertex cannot be processed simultaneously. The objective is to minimize the sum of weighted completion times of all vertices. Kim ( Journal of Algorithms, 55:42--57, 2005 ) gave a 9-approximation algorithm for the problem when edges have arbitrary processing times and are released at time zero. We improve Kim's result by giving a 5.06-approximation algorithm. We also address the open shop scheduling problem, O | r j | ∑ w j C j , and show that it is a special case of the data migration problem. Queyranne and Sviridenko ( Journal of Scheduling, 5:287-305, 2002 ) gave a 5.83-approximation algorithm for the nonpreemptive version of the open shop problem. They state as an obvious open question whether there exists an algorithm for open shop scheduling that gives a performance guarantee better than 5.83. Our 5.06 algorithm for data migration proves the existence of such an algorithm. Crucial to our improved result is a property of the linear programming relaxation for the problem. Similar linear programs have been used for various other scheduling problems. Our technique may be useful in obtaining improved results for these problems as well.

A basic problem in graphs and hypergraphs is that of finding a large independent set---one of guaranteed size. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza [J. Graph Theory, 15 (1991), pp. 99--107] have shown a certain lower bound $\alpha_k(H)$ on the size of a maximum independent set in a given k-uniform hypergraph H and have also presented an efficient sequential algorithm to find an independent set of size $\alpha_k(H)$. They also show that $\alpha_k(H)$ is the size of the maximum independent set for various hypergraph families. Here, we show that an RNC algorithm due to Beame and Luby [in Proceedings of the ACM--SIAM Symposium on Discrete Algorithms, 1990, pp. 212--218] finds an independent set of expected size $\alpha_k(H)$ and also derandomizes it for certain special cases. (An intriguing conjecture of Beame and Luby implies that understanding this algorithm better may yield an RNC algorithm to find a maximal independent set in hypergraphs, which is among the outstanding open questions in parallel computation.) We also present lower bounds on independent set size for nonuniform hypergraphs using this algorithm. For graphs, we get an NC algorithm to find independent sets of size essentially that guaranteed by the general (degree-sequence based) version of Turán's theorem.

A basic problem in hypergraphs is that of finding a large independent set–one of guaranteed size–in a given hypergraph. Understanding the parallel complexity of this and related independent set problems on hypergraphs is a fundamental open issue in parallel computation. Caro and Tuza (J. Graph Theory, Vol. 15, pp. 99–107, 1991) have shown a certain lower bound αk(H) on the size of a maximum independent set in a given k-uniform hypergraph H, and have also presented an efficient sequential algorithm to find an independent set of size αk(H). They also show that αk(H) is the size of the maximum independent set for various hypergraph families. Here, we develop the first RNC algorithm to find an independent set of size αk(H), and also derandomize it for various special cases. We also present lower bounds on independent set size and corresponding RNC algorithms for non-uniform hypergraphs.

No abstract available.

This paper studies the power of nonrestricted preprocessing on a communication graph G, in a synchronous, reliable system. In our scenario, arbitrary preprocessing can be performed on G, after which a sequence of labeling problems has to be solved on different subgraphs of G. We suggest a preprocessing that produces an orientation of G. The goal is to exploit this preprocessing for minimizing the radius of the neighborhood around each vertex from which data has to be collected in order to determine a label. We define a set of labeling problems for which this can be done. The time complexity of labeling a subgraph depends on the topology of the graph G and is always less than $\min\{\chi(G), O((\log n)^{2})\}$. On the other hand, we show the existence of a graph for which even unbounded preprocessing does not allow fast solution of a simple labeling problem. Specifically, it is shown that a processor needs to know its $\Omega(\log n / \log \log n)$-neighborhood in order to pick a label. Finally, we derive some results for the resource allocation problem. In particular, we show that $\Omega(\log n / \log \log n)$ communication rounds are needed if resources are to be fully utilized. In this context, we define the compact coloring problem, for which the orientation preprocessing provides fast distributed labeling algorithm. This algorithm suggests efficient solution for the resource allocation problem.

Speculative execution of code is becoming a key technique for enhancing the performance of pipeline processors. We study schemes that predict the execution path of a program based on the history of branch executions. Building on previous work, we present a model for analyzing the effective speedup from pipelining using various schemes for speculative execution. We follow this with stochastic analyses of various speculative execution schemes. Finally, we conclude with simulations covering several of the settings we study.

Considers the problem of scheduling a set of tasks on a parallel machine of identical processors. The tasks are parallelizable and can be run simultaneously on several processors, in which case the runtime is decreased, Our goal is to minimize the finishing time (or makespan) of the entire schedule. This problem is known to be NP-hard. We propose a new approach to scheduling, based on partitioning the available processors into a fixed number of computation channels. We assign tasks to channels based on their execution times and their speed-up function, assuming that these parameters are available prior to the execution of the task sequence. The channel approach is shown to be advantageous whenever the overall work needed to execute tasks does not decrease as a function of the number of processors assigned to it, i.e. in most common scenarios. For cases in which this function is a constant (and, therefore, the overall runtime per task decreases linearly with the number of processors executing it), we present a new scheduling heuristic called the partition-and-assignment (PA) algorithm. PA is shown to achieve a worst case bound of 2 to the optimal schedule. It runs in linear time, O(n+m), where m is the number of processors and n is the number of tasks. For the case of nonlinear speedup, we introduce a generalized version of PA (GPA), which achieves a bound of 2 to the optimum, and runs in time O(m log a+n), where a=min(n,m).

For a video-on-demand computer system we propose a scheme which balances the load on the disks, thereby helping to solve a performance problem crucial to achieving maximal video throughput. Our load balancing scheme consists of two stages. The static stage determines good assignments of videos to groups of striped disks. The dynamic phase uses these assignments, and features a DASD dancing algorithm which performs real-time disk scheduling in an effective manner. Our scheme works synergistically with disk striping. We examine the performance of the DASD dancing algorithm via simulation experiments.