1 Search Results for "Kubitza, Judith-Madeleine"

Document
DOI: 10.4230/LIPIcs.IPEC.2015.55
Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs

Authors: Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

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.
Cite as

Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger. Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 55-65, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{hermelin_et_al:LIPIcs.IPEC.2015.55,
  author =	{Hermelin, Danny and Kubitza, Judith-Madeleine and Shabtay, Dvir and Talmon, Nimrod and Woeginger, Gerhard},
  title =	{{Scheduling Two Competing Agents When One Agent Has Significantly Fewer Jobs}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{55--65},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.55},
  URN =		{urn:nbn:de:0030-drops-55713},
  doi =		{10.4230/LIPIcs.IPEC.2015.55},
  annote =	{Keywords: Parameterized Complexity, Multiagent Scheduling}
}
  • Refine by Author
  • 1 Hermelin, Danny
  • 1 Kubitza, Judith-Madeleine
  • 1 Shabtay, Dvir
  • 1 Talmon, Nimrod
  • 1 Woeginger, Gerhard

  • Refine by Classification

  • Refine by Keyword
  • 1 Multiagent Scheduling
  • 1 Parameterized Complexity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact