Wyniki wyszukiwania - BazTech

1

Stackelberg strategies for weighted load balancing games

Stein Neta, Tamir Tami

Annals of Computer Science and Information Systems

|

2022

|

Vol. 30

373--382

EN

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.

2

Minimizing Tardiness in a Scheduling Environment with Jobs' Hierarchy

Sinai Michal, Tamir Tami

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

201--209

EN

In many scheduling environments, some jobs have higher priority than others. We consider a new model, motivated by real-life behavior, 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 define the model and the set of feasible schedules formally, and provide algorithms and hardness proofs for 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.

3

Achieving Good Nash Equilibrium by Temporal Addition of Dummy Players

Dadush Ofek, Tamir Tami

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

163--172

EN

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 dummies 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.

4

Best response dynamics for VLSI physical design placement

Rapoport Michael, Tamir Tami

Annals of Computer Science and Information Systems

|

2019

|

Vol. 18

147--156

EN

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 $2$-dimensional rectangles, with various sizes and wire connectivity requirements. We focus on minimizing the placement area and the total wire length.