Many combinatorial optimization problems arise in the context of resource allocation.In this paper, we study the problem of allocating shareable resources of different types to jobs, where each job consists of multiple tasks, and each task has a demand of a given duration to a single resource type.All resources are available over a common time interval.Several copies from each resource may be allocated.In a valid solution, at any given time, each job may be processed by at most one resource, and each resource may process at most one job.The objective is to complete all jobs while minimizing the total cost of the allocated resources.We focus on the power of preemptions in this model, analyzing how much the total cost can be reduced when jobs are allowed to be preempted -that is, when the processing of tasks can be split into multiple intervals.We present both theoretical and experimental results, distinguishing between environments where jobs may be preempted but all intervals of a task must be processed on the same resource copy (weak preemptions), and environments where jobs may split the processing of a task among different resource copies (strong preemptions).Without preemptions, the problem is clearly NPhard, as it generalizes the classical Bin Packing problem.We provide an optimal polynomial-time algorithm for the strongpreemption model, as well as a polynomial-time algorithm for the non-preemption model under a restricted class of task durations.Our empirical evaluation investigates the performance of several greedy heuristics, showing that even simple methods can achieve near-optimal results.

In job-scheduling games, each job is a selfish player that selects a machine to minimize its own completion time. Coordination mechanisms are employed to reduce the inefficiency of equilibria that result from such decentralized decision-making. This paper contributes to the extensive body of research on coordination mechanisms by investigating their application to unrelated parallel machines, where each machine may use its own scheduling policy to determine the processing order of assigned jobs. Since pure Nash equilibria (NE) are not guaranteed to exist in this setting, we identify and characterize several classes of instances—motivated by real-world applications—in which a NE is guaranteed to exist. For each such class, we design an algorithm to compute a NE, prove the convergence of best-response dynamics, and analyze the inefficiency of equilibria with respect to the makespan. In addition, we study two fundamental problems: (1) computing a NE schedule with low makespan, and (2) selecting, given a matrix of processing times, machine-specific scheduling policies that guarantee the existence of a NE with low makespan. For both problems, we establish computational hardness results.

No abstract available.

An instance of a weighted Stackelberg load balancing game is given by a set of identical machines, a set of variable-length jobs and a parameter 0 ≤ α ≤ 1.A centralized authority, denoted the leader, selects a subset of the jobs whose total length is at most an α-fraction of the total length and determines their assignment on the machines.After the controlled jobs are assigned, the remaining jobs join the schedule.They act selfishly, each determining its own assignment.Our work combines theoretical and experimental results for this setting.We suggest various heuristics for the leader and analyze their performance.

We consider cost-sharing games in which resources' costs are fairly shared by their users.The total players' cost in a Nash Equilibrium profile may be significantly higher than the social optimum.We compare and analyze several methods to lead the players to a good Nash Equilibrium by temporal addition of dummy players.The dummy players create artificial load on some resources, that encourage other players to change their strategies.We show that it is NP-hard to calculate an optimal strategy for the dummy players.We then focus on symmetric singleton games for which we suggest several heuristics for the problem.We analyze their performance distinguishing between several classes of instances and several performance measures.

In many scheduling environments, some jobs have higher priority than others.Such scenarios are theoretically modelled by associating jobs with weights, or by having precedence constraints that limit jobs' processing order.In this paper we define and consider a new model, motivated by real-life behaviour, in which the priority among jobs is defined by a dominance hierarchy.Specifically, the jobs are arranged in hierarchy levels, and high ranking jobs are ready to accept only outcomes in which the service they receive is better than the service of subordinate jobs.We first define the model and the set of feasible schedules formally.We then consider two classical problems: minimizing the maximal tardiness and minimizing the number of tardy jobs.We provide optimal algorithms or hardness proofs for these problems, distinguishing between a global objective function and a multi-criteria objective.

The physical design placement problem is one of the hardest and most important problems in micro chips production.The placement defines how to place the electrical components on the chip.We consider the problem as a combinatorial optimization problem, whose instance is defined by a set of 2dimensional rectangles, with various sizes and wire connectivity requirements.We focus on minimizing the placement area and the total wire-length.We propose a local-search method for coping with the problem, based on natural dynamics common in game theory.Specifically, we suggest to perform variants of Best-Response Dynamics (BRD).In our method, we assume that every component is controlled by a selfish agent, who aim at minimizing his individual cost, which depends on his own location and the wire-length of his connections.We suggest several BRD methods, based on selfish migrations of a single or a cooperative of components.We performed a comprehensive experimental study on various test-benches, and compared our results with commonly known algorithms, in particular, with simulated annealing.The results show that selfish local-search, especially when applied with cooperatives of components, may be beneficial for the placement problem.

We introduce and study alternating reachability games with tolls (ARGTs). An ARGT is a multi-player game played on a directed graph. Each player has a source vertex and a set of target vertices. The vertices of the graph are partitioned among the players. Thus, each player owns a subset of the vertices. In the beginning of the game, each player places a token on her source vertex. Whenever a token reaches a vertex v, the owner of the token pays a toll to the owner of vertex v, who directs the token to one of the successors of v. The objective of each player combines a reachability objective with a minimal-cost maximal-profit objective. For the first, the token of the player needs to reach one of her target vertices. For the second, the player aims at decreasing the toll she pays to other players and increasing the toll paid to her due to visits in vertices she owns. ARGTs model settings in which the vertices are owned by entities who also use the network; for example, communication networks in which service providers own the routers and send messages. ARGTs also offer an extension of rational synthesis with rewards to actions. To the best of our knowledge, this model is the first to combine behavioral and revenue objectives. We study different instances of the game, distinguishing between various network topologies and various levels of overlap among the reachability objectives of the players. We analyze the stability of ARGTs, characterizing instances for which a Nash equilibrium is guaranteed to exist, and studying its inefficiency. We also analyze the problems of finding optimal strategies for the players and for the society as a whole.

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.

Many real-life applications involve systems that change dynamically over time.Thus, throughout the continuous operation of such a system, it is required to compute solutions for new problem instances, derived from previous instances.Since the transition from one solution to another incurs some cost, a natural goal is to have the solution for the new instance close to the original one (under a certain distance measure).We study reoptimization problems arising in scheduling systems.Formally, due to changes in the environment (out-of-order or new machines, modified jobs' processing requirements, etc.), the schedule needs to be modified.That is, jobs might be migrated from their current machine to a different one.Migrations are associated with a cost -due to relocation overhead and machine set-up times.In some systems, a migration is also associated with job extension.The goal is to find a good modified schedule, with a low transition cost from the initial one.We consider reoptimization with respect to the classical objectives of minimum makespan and minimum total flowtime.We first prove that the reoptimization variants of both problems are NP-hard, already for very restricted classes.We then develop and present several heuristics for each objective, implement these heuristics, compare their performance on various classes of instances and analyze the results.

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.

In classical congestion games, players' strategies are subsets of resources. We introduce and study multiset congestion games, where players' strategies are multisets of resources. Thus, in each strategy a player may need to use each resource a different number of times, and his cost for using the resource depends on the load that he and the other players generate on the resource. Beyond the theoretical interest in examining the effect of a repeated use of resources, our study enables better understanding of non-cooperative systems and environments whose behavior is not covered by previously studied models. Indeed, congestion games with multiset-strategies arise, for example, in production planing and network formation with tasks that are more involved than reachability. We study in detail the application of synthesis from component libraries: different users synthesize systems by gluing together components from a component library. A component may be used in several systems and may be used several times in a system. The performance of a component and hence the system's quality depends on the load on it. Our results reveal how the richer setting of multisets congestion games affects the stability and equilibrium efficiency compared to standard congestion games. In particular, while we present very simple instances with no pure Nash equilibrium and prove tighter and simpler lower bounds for equilibrium inefficiency, we are also able to show that some of the positive results known for affine and weighted congestion games apply to the richer setting of multisets.

We study capacitated automata(CAs), where transitions correspond to resources and may have bounded capacities. Each transition in a CA is associated with a (possibly infinite) bound on the number of times it may be traversed. We study CAs from two points of view. The first is that of traditional automata theory, where we view CAs as recognizers of formal languages and examine their expressive power, succinctness, and determinization. The second is that of resource-allocation theory, where we view CAs as a rich description of a flow network and study their utilization.

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.

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.

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.

A Nash Equilibrium (NE) is a strategy profile resilient to unilateral deviations, and is predominantly used in the analysis of multiagent systems. A downside of NE is that it is not necessarily stable against deviations by coalitions. Yet, as we show in this paper, in some cases, NE does exhibit stability against coalitional deviations, in that the benefits from a joint deviation are bounded. In this sense, NE approximates strong equilibrium. Coalition formation is a key issue in multiagent systems. We provide a framework for quantifying the stability and the performance of various assignment policies and solution concepts in the face of coalitional deviations. Within this framework we evaluate a given configuration according to three measures: (i) IR_min: the maximal number alpha, such that there exists a coalition in which the minimal improvement ratio among the coalition members is alpha, (ii) IR_max: the maximal number alpha, such that there exists a coalition in which the maximal improvement ratio among the coalition members is alpha, and (iii) DR_max: the maximal possible damage ratio of an agent outside the coalition. We analyze these measures in job scheduling games on identical machines. In particular, we provide upper and lower bounds for the above three measures for both NE and the well-known assignment rule Longest Processing Time (LPT). Our results indicate that LPT performs better than a general NE. However, LPT is not the best possible approximation. In particular, we present a polynomial time approximation scheme (PTAS) for the makespan minimization problem which provides a schedule with IR_min of 1+epsilon for any given epsilon. With respect to computational complexity, we show that given an NE on m >= 3 identical machines or m >= 2 unrelated machines, it is NP-hard to determine whether a given coalition can deviate such that every member decreases its cost.

Given is a sequence of n positive integers w 1 , w 2 ,…, w n that are associated with the items 1,2,… n , respectively. In the windows scheduling problem, the goal is to schedule all the items (equal-length information pages) on broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most w i slots (a slot is the transmission time of one page). In the unit-fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item i is 1/ w i . The optimization objective is to minimize the number of channels or bins. In the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. Since a page requires at least 1/ w i of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing. Let H = ⌈Σ i ==1 n (1/ w i ) be the bandwidth lower bound on the required number of bins (channels). The best-known offline algorithm for the windows scheduling problem used H + O (ln H ) channels. This article presents an offline algorithm for the unit-fractions bin packing problem with at most H + 1 bins. In the online setting, this article presents algorithms for both problems with H + O (√ H ) channels or bins, where the one for the unit-fractions bin packing problem is simpler. On the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least H +Ω(ln H ) bins. For instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. Finally, this article includes a new NP-hardness proof for the windows scheduling problem.

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 study truthful mechanisms for auctions in which the auctioneer is trying to hire a team of agents to perform a complex task, and paying them for their work. As common in the field of mechanism design, we assume that the agents are selfish and will act in such a way as to maximize their profit, which in particular may include misrepresenting their true incurred cost. Our first contribution is a new and natural definition of the frugality ratio of a mechanism, measuring the amount by which a mechanism "overpays ", and extending previous definitions to all monopoly-free set systems. After reexamining several known results in light of this new definition, we proceed to study in detail shortest path auctions and 'r-out-of-k sets" auctions. We show that when individual set systems (e.g., graphs) are considered instead of worst cases over all instances, these problems exhibit a rich structure, and the performance of mechanisms may be vastly different. In particular, we show that the well-known VCG mechanism may be far from optimal in these settings, and we propose and analyze a mechanism that is always within a constant factor of optimal.

The generalized windows scheduling problem for n jobs on multiple machines is defined as follows: Given is a sequence, I =\ang(w1, l1),(w2, l 2),...,(wn, ln) of n pairs of positive integers that are associated with the jobs 1,2,...,n, respectively. The processing length of job i is li slots (a slot is the processing time of one length unit). The goal is to repeatedly and non-preemptively schedule all the jobs on the fewest possible parallel machines such that the gap (window) between two consecutive executions of the first slot of job i is at most wi slots. This problem arises in push broadcast systems in which data is transmitted on parallel channels.

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.