ﻻ يوجد ملخص باللغة العربية
Given a system model where machines have distinct speeds and power ratings but are otherwise compatible, we consider various problems of scheduling under resource constraints on the system which place the restriction that not all machines can be run at once. These can be power, energy, or makespan constraints on the system. Given such constraints, there are problems with divisible as well as non-divisible jobs. In the setting where there is a constraint on power, we show that the problem of minimizing makespan for a set of divisible jobs is NP-hard by reduction to the knapsack problem. We then show that scheduling to minimize energy with power constraints is also NP-hard. We then consider scheduling with energy and makespan constraints with divisible jobs and show that these can be solved in polynomial time, and the problems with non-divisible jobs are NP-hard. We give exact and approximation algorithms for these problems as required.
Consider the problem where $n$ jobs, each with a release time, a deadline and a required processing time are to be feasibly scheduled in a single- or multi-processor setting so as to minimize the total energy consumption of the schedule. A processor
We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning a
We study the role of interactivity in distributed statistical inference under information constraints, e.g., communication constraints and local differential privacy. We focus on the tasks of goodness-of-fit testing and estimation of discrete distrib
We investigate graph problems in the following setting: we are given a graph $G$ and we are required to solve a problem on $G^2$. While we focus mostly on exploring this theme in the distributed CONGEST model, we show new results and surprising conne
Given n jobs with release dates, deadlines and processing times we consider the problem of scheduling them on m parallel machines so as to minimize the total energy consumed. Machines can enter a sleep state and they consume no energy in this state.