Scheduling two competing agents when one agent has significantly fewer jobs

Danny Hermelin; Judith Madeleine Kubitza; Dvir Shabtay; Nimrod Talmon; Gerhard Woeginger

doi:10.4230/LIPIcs.IPEC.2015.55

Scheduling two competing agents when one agent has significantly fewer jobs

Danny Hermelin, Judith Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, Gerhard Woeginger

Discrete Mathematics

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

9 Citaten (Scopus)

Samenvatting

We study a scheduling problem where two agents (each equipped with a private set of jobs) compete to perform their respective jobs on a common single machine. Each agent wants to keep the weighted sum of completion times of his jobs below a given (agent-dependent) bound. This problem is known to be NP-hard, even for quite restrictive settings of the problem parameters. We consider parameterized versions of the problem where one of the agents has a small number of jobs (and where this small number constitutes the parameter). The problem becomes much more tangible in this case, and we present three positive algorithmic results for it. Our study is complemented by showing that the general problem is NP-complete even when one agent only has a single job.

Originele taal-2	Engels
Titel	10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Redacteuren	Thore Husfeldt, Thore Husfeldt, Iyad Kanj
Uitgeverij	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's	55-65
Aantal pagina's	11
ISBN van elektronische versie	9783939897927
DOI's	https://doi.org/10.4230/LIPIcs.IPEC.2015.55
Status	Gepubliceerd - 1 nov. 2015
Evenement	10th International Symposium on Parameterized and Exact Computation, IPEC 2015 - Patras, Griekenland Duur: 16 sep. 2015 → 18 sep. 2015 Congresnummer: 10 http://algo2015.upatras.gr/ipec

Publicatie series

Naam	Leibniz International Proceedings in Informatics, LIPIcs
Volume	43
ISSN van geprinte versie	1868-8969

Congres

Congres	10th International Symposium on Parameterized and Exact Computation, IPEC 2015
Verkorte titel	IPEC 2015
Land/Regio	Griekenland
Stad	Patras
Periode	16/09/15 → 18/09/15
Internet adres	http://algo2015.upatras.gr/ipec

Bibliografische nota

Publisher Copyright:
© Danny Hermelin, Judith Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger;.

Toegang tot document

10.4230/LIPIcs.IPEC.2015.55

Andere bestanden en links

Link naar publicatie in Scopus

Citeer dit

Hermelin, D., Kubitza, J. M., Shabtay, D., Talmon, N., & Woeginger, G. (2015). Scheduling two competing agents when one agent has significantly fewer jobs. In T. Husfeldt, T. Husfeldt, & I. Kanj (editors), 10th International Symposium on Parameterized and Exact Computation, IPEC 2015 (blz. 55-65). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 43). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2015.55

Hermelin, Danny ; Kubitza, Judith Madeleine ; Shabtay, Dvir et al. / Scheduling two competing agents when one agent has significantly fewer jobs. 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. redacteur / Thore Husfeldt ; Thore Husfeldt ; Iyad Kanj. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. blz. 55-65 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{392694ef7b72400a9327a798a96b9e78,

title = "Scheduling two competing agents when one agent has significantly fewer jobs",

abstract = "We study a scheduling problem where two agents (each equipped with a private set of jobs) compete to perform their respective jobs on a common single machine. Each agent wants to keep the weighted sum of completion times of his jobs below a given (agent-dependent) bound. This problem is known to be NP-hard, even for quite restrictive settings of the problem parameters. We consider parameterized versions of the problem where one of the agents has a small number of jobs (and where this small number constitutes the parameter). The problem becomes much more tangible in this case, and we present three positive algorithmic results for it. Our study is complemented by showing that the general problem is NP-complete even when one agent only has a single job.",

keywords = "Multiagent scheduling, Parameterized complexity",

author = "Danny Hermelin and Kubitza, {Judith Madeleine} and Dvir Shabtay and Nimrod Talmon and Gerhard Woeginger",

note = "Publisher Copyright: {\textcopyright} Danny Hermelin, Judith Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger;.; 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, IPEC 2015 ; Conference date: 16-09-2015 Through 18-09-2015",

year = "2015",

month = nov,

day = "1",

doi = "10.4230/LIPIcs.IPEC.2015.55",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",

pages = "55--65",

editor = "Thore Husfeldt and Thore Husfeldt and Iyad Kanj",

booktitle = "10th International Symposium on Parameterized and Exact Computation, IPEC 2015",

url = "http://algo2015.upatras.gr/ipec",

}

Hermelin, D, Kubitza, JM, Shabtay, D, Talmon, N & Woeginger, G 2015, Scheduling two competing agents when one agent has significantly fewer jobs. in T Husfeldt, T Husfeldt & I Kanj (uitgave), 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. Leibniz International Proceedings in Informatics, LIPIcs, vol. 43, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, blz. 55-65, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015, Patras, Griekenland, 16/09/15. https://doi.org/10.4230/LIPIcs.IPEC.2015.55

Scheduling two competing agents when one agent has significantly fewer jobs. / Hermelin, Danny; Kubitza, Judith Madeleine; Shabtay, Dvir et al.
10th International Symposium on Parameterized and Exact Computation, IPEC 2015. uitgave / Thore Husfeldt; Thore Husfeldt; Iyad Kanj. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2015. blz. 55-65 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 43).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Scheduling two competing agents when one agent has significantly fewer jobs

AU - Hermelin, Danny

AU - Kubitza, Judith Madeleine

AU - Shabtay, Dvir

AU - Talmon, Nimrod

AU - Woeginger, Gerhard

N1 - Conference code: 10

PY - 2015/11/1

Y1 - 2015/11/1

N2 - We study a scheduling problem where two agents (each equipped with a private set of jobs) compete to perform their respective jobs on a common single machine. Each agent wants to keep the weighted sum of completion times of his jobs below a given (agent-dependent) bound. This problem is known to be NP-hard, even for quite restrictive settings of the problem parameters. We consider parameterized versions of the problem where one of the agents has a small number of jobs (and where this small number constitutes the parameter). The problem becomes much more tangible in this case, and we present three positive algorithmic results for it. Our study is complemented by showing that the general problem is NP-complete even when one agent only has a single job.

AB - We study a scheduling problem where two agents (each equipped with a private set of jobs) compete to perform their respective jobs on a common single machine. Each agent wants to keep the weighted sum of completion times of his jobs below a given (agent-dependent) bound. This problem is known to be NP-hard, even for quite restrictive settings of the problem parameters. We consider parameterized versions of the problem where one of the agents has a small number of jobs (and where this small number constitutes the parameter). The problem becomes much more tangible in this case, and we present three positive algorithmic results for it. Our study is complemented by showing that the general problem is NP-complete even when one agent only has a single job.

KW - Multiagent scheduling

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=84958232398&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.IPEC.2015.55

DO - 10.4230/LIPIcs.IPEC.2015.55

M3 - Conference contribution

AN - SCOPUS:84958232398

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 55

EP - 65

BT - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015

A2 - Husfeldt, Thore

A2 - Kanj, Iyad

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 10th International Symposium on Parameterized and Exact Computation, IPEC 2015

Y2 - 16 September 2015 through 18 September 2015

ER -

Hermelin D, Kubitza JM, Shabtay D, Talmon N, Woeginger G. Scheduling two competing agents when one agent has significantly fewer jobs. In Husfeldt T, Husfeldt T, Kanj I, redacteurs, 10th International Symposium on Parameterized and Exact Computation, IPEC 2015. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. 2015. blz. 55-65. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.IPEC.2015.55

Scheduling two competing agents when one agent has significantly fewer jobs

Samenvatting

Publicatie series

Congres

Bibliografische nota

Toegang tot document

Andere bestanden en links

Vingerafdruk

Citeer dit