--- _id: '13868' author: - first_name: Simon full_name: Pukrop, Simon id: '44428' last_name: Pukrop - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide citation: ama: 'Pukrop S, Mäcker A, Meyer auf der Heide F. Approximating Weighted Completion Time for Order Scheduling with Setup Times. In: Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). ; 2020.' apa: Pukrop, S., Mäcker, A., & Meyer auf der Heide, F. (2020). Approximating Weighted Completion Time for Order Scheduling with Setup Times. In Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM). bibtex: '@inproceedings{Pukrop_Mäcker_Meyer auf der Heide_2020, title={Approximating Weighted Completion Time for Order Scheduling with Setup Times}, booktitle={Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM)}, author={Pukrop, Simon and Mäcker, Alexander and Meyer auf der Heide, Friedhelm}, year={2020} }' chicago: Pukrop, Simon, Alexander Mäcker, and Friedhelm Meyer auf der Heide. “Approximating Weighted Completion Time for Order Scheduling with Setup Times.” In Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2020. ieee: S. Pukrop, A. Mäcker, and F. Meyer auf der Heide, “Approximating Weighted Completion Time for Order Scheduling with Setup Times,” in Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2020. mla: Pukrop, Simon, et al. “Approximating Weighted Completion Time for Order Scheduling with Setup Times.” Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2020. short: 'S. Pukrop, A. Mäcker, F. Meyer auf der Heide, in: Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2020.' date_created: 2019-10-15T12:19:49Z date_updated: 2022-01-06T06:51:45Z department: - _id: '63' language: - iso: eng project: - _id: '4' name: SFB 901 - Project Area C - _id: '1' name: SFB 901 - _id: '16' name: SFB 901 - Subproject C4 publication: Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) status: public title: Approximating Weighted Completion Time for Order Scheduling with Setup Times type: conference user_id: '44428' year: '2020' ... --- _id: '8866' author: - first_name: Klaus full_name: Jansen, Klaus last_name: Jansen - first_name: Marten full_name: Maack, Marten last_name: Maack - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker citation: ama: 'Jansen K, Maack M, Mäcker A. Scheduling on (Un-)Related Machines with Setup Times. In: Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE; 2019:145-154.' apa: Jansen, K., Maack, M., & Mäcker, A. (2019). Scheduling on (Un-)Related Machines with Setup Times. In Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS) (pp. 145–154). IEEE. bibtex: '@inproceedings{Jansen_Maack_Mäcker_2019, title={Scheduling on (Un-)Related Machines with Setup Times}, booktitle={Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS)}, publisher={IEEE}, author={Jansen, Klaus and Maack, Marten and Mäcker, Alexander}, year={2019}, pages={145–154} }' chicago: Jansen, Klaus, Marten Maack, and Alexander Mäcker. “Scheduling on (Un-)Related Machines with Setup Times.” In Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), 145–54. IEEE, 2019. ieee: K. Jansen, M. Maack, and A. Mäcker, “Scheduling on (Un-)Related Machines with Setup Times,” in Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), 2019, pp. 145–154. mla: Jansen, Klaus, et al. “Scheduling on (Un-)Related Machines with Setup Times.” Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2019, pp. 145–54. short: 'K. Jansen, M. Maack, A. Mäcker, in: Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS), IEEE, 2019, pp. 145–154.' date_created: 2019-04-09T11:28:46Z date_updated: 2022-01-06T07:04:04Z department: - _id: '63' language: - iso: eng page: 145 - 154 project: - _id: '4' name: SFB 901 - Project Area C - _id: '16' name: SFB 901 - Subproject C4 - _id: '1' name: SFB 901 publication: Proceedings of the 33rd IEEE International Parallel and Distributed Processing Symposium (IPDPS) publisher: IEEE status: public title: Scheduling on (Un-)Related Machines with Setup Times type: conference user_id: '13536' year: '2019' ... --- _id: '14851' author: - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker citation: ama: Mäcker A. On Scheduling with Setup Times. Universität Paderborn; 2019. doi:10.17619/UNIPB/1-828 apa: Mäcker, A. (2019). On Scheduling with Setup Times. Universität Paderborn. https://doi.org/10.17619/UNIPB/1-828 bibtex: '@book{Mäcker_2019, place={Universität Paderborn}, title={On Scheduling with Setup Times}, DOI={10.17619/UNIPB/1-828}, author={Mäcker, Alexander}, year={2019} }' chicago: Mäcker, Alexander. On Scheduling with Setup Times. Universität Paderborn, 2019. https://doi.org/10.17619/UNIPB/1-828. ieee: A. Mäcker, On Scheduling with Setup Times. Universität Paderborn, 2019. mla: Mäcker, Alexander. On Scheduling with Setup Times. 2019, doi:10.17619/UNIPB/1-828. short: A. Mäcker, On Scheduling with Setup Times, Universität Paderborn, 2019. date_created: 2019-11-07T14:17:05Z date_updated: 2022-01-06T06:52:08Z ddc: - '000' department: - _id: '63' doi: 10.17619/UNIPB/1-828 language: - iso: eng place: Universität Paderborn project: - _id: '1' name: SFB 901 - _id: '16' name: SFB 901 - Subproject C4 - _id: '4' name: SFB 901 - Project Area C related_material: link: - relation: confirmation url: https://doi.org/10.17619/UNIPB/1-828 status: public supervisor: - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide title: On Scheduling with Setup Times type: dissertation user_id: '15415' year: '2019' ... --- _id: '3551' author: - first_name: Jürgen full_name: König, Jürgen id: '22358' last_name: König - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers citation: ama: König J, Mäcker A, Meyer auf der Heide F, Riechers S. Scheduling with interjob communication on parallel processors. Journal of Combinatorial Optimization. 2018;36(4):1356-1379. doi:10.1007/s10878-018-0325-3 apa: König, J., Mäcker, A., Meyer auf der Heide, F., & Riechers, S. (2018). Scheduling with interjob communication on parallel processors. Journal of Combinatorial Optimization, 36(4), 1356–1379. https://doi.org/10.1007/s10878-018-0325-3 bibtex: '@article{König_Mäcker_Meyer auf der Heide_Riechers_2018, title={Scheduling with interjob communication on parallel processors}, volume={36}, DOI={10.1007/s10878-018-0325-3}, number={4}, journal={Journal of Combinatorial Optimization}, author={König, Jürgen and Mäcker, Alexander and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2018}, pages={1356–1379} }' chicago: 'König, Jürgen, Alexander Mäcker, Friedhelm Meyer auf der Heide, and Sören Riechers. “Scheduling with Interjob Communication on Parallel Processors.” Journal of Combinatorial Optimization 36, no. 4 (2018): 1356–79. https://doi.org/10.1007/s10878-018-0325-3.' ieee: J. König, A. Mäcker, F. Meyer auf der Heide, and S. Riechers, “Scheduling with interjob communication on parallel processors,” Journal of Combinatorial Optimization, vol. 36, no. 4, pp. 1356–1379, 2018. mla: König, Jürgen, et al. “Scheduling with Interjob Communication on Parallel Processors.” Journal of Combinatorial Optimization, vol. 36, no. 4, 2018, pp. 1356–79, doi:10.1007/s10878-018-0325-3. short: J. König, A. Mäcker, F. Meyer auf der Heide, S. Riechers, Journal of Combinatorial Optimization 36 (2018) 1356–1379. date_created: 2018-07-13T09:57:48Z date_updated: 2022-01-06T06:59:24Z ddc: - '000' department: - _id: '63' doi: 10.1007/s10878-018-0325-3 file: - access_level: closed content_type: application/pdf creator: ups date_created: 2018-11-02T15:20:24Z date_updated: 2018-11-02T15:20:24Z file_id: '5299' file_name: SchedulingWithInterjobCommunic.pdf file_size: 745708 relation: main_file success: 1 file_date_updated: 2018-11-02T15:20:24Z has_accepted_license: '1' intvolume: ' 36' issue: '4' language: - iso: eng page: 1356-1379 project: - _id: '16' name: SFB 901 - Subproject C4 - _id: '1' name: SFB 901 - _id: '4' name: SFB 901 - Project Area C publication: Journal of Combinatorial Optimization status: public title: Scheduling with interjob communication on parallel processors type: journal_article user_id: '477' volume: 36 year: '2018' ... --- _id: '79' abstract: - lang: eng text: Consider a problem in which $n$ jobs that are classified into $k$ types arrive over time at their release times and are to be scheduled on a single machine so as to minimize the maximum flow time.The machine requires a setup taking $s$ time units whenever it switches from processing jobs of one type to jobs of a different type.We consider the problem as an online problem where each job is only known to the scheduler as soon as it arrives and where the processing time of a job only becomes known upon its completion (non-clairvoyance).We are interested in the potential of simple ``greedy-like'' algorithms.We analyze a modification of the FIFO strategy and show its competitiveness to be $\Theta(\sqrt{n})$, which is optimal for the considered class of algorithms.For $k=2$ types it achieves a constant competitiveness.Our main insight is obtained by an analysis of the smoothed competitiveness.If processing times $p_j$ are independently perturbed to $\hat p_j = (1+X_j)p_j$, we obtain a competitiveness of $O(\sigma^{-2} \log^2 n)$ when $X_j$ is drawn from a uniform or a (truncated) normal distribution with standard deviation $\sigma$.The result proves that bad instances are fragile and ``practically'' one might expect a much better performance than given by the $\Omega(\sqrt{n})$-bound. author: - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Manuel full_name: Malatyali, Manuel last_name: Malatyali - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers citation: ama: 'Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times. In: Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA). Vol 10787. Lecture Notes in Computer Science. Springer; 2017:207-222. doi:10.1007/978-3-319-89441-6' apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2017). Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times. In Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA) (Vol. 10787, pp. 207–222). Springer. https://doi.org/10.1007/978-3-319-89441-6 bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2017, series={Lecture Notes in Computer Science}, title={Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times}, volume={10787}, DOI={10.1007/978-3-319-89441-6}, booktitle={Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA)}, publisher={Springer}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2017}, pages={207–222}, collection={Lecture Notes in Computer Science} }' chicago: Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times.” In Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA), 10787:207–22. Lecture Notes in Computer Science. Springer, 2017. https://doi.org/10.1007/978-3-319-89441-6. ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times,” in Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA), 2017, vol. 10787, pp. 207–222. mla: Mäcker, Alexander, et al. “Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times.” Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA), vol. 10787, Springer, 2017, pp. 207–22, doi:10.1007/978-3-319-89441-6. short: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA), Springer, 2017, pp. 207–222.' date_created: 2017-10-17T12:41:06Z date_updated: 2022-01-06T07:03:47Z ddc: - '000' department: - _id: '63' doi: 10.1007/978-3-319-89441-6 file: - access_level: closed content_type: application/pdf creator: ups date_created: 2018-11-02T14:59:22Z date_updated: 2018-11-02T14:59:22Z file_id: '5289' file_name: Non-clairvoyantSchedulingToMin.pdf file_size: 380629 relation: main_file success: 1 file_date_updated: 2018-11-02T14:59:22Z has_accepted_license: '1' intvolume: ' 10787' language: - iso: eng page: 207-222 project: - _id: '1' name: SFB 901 - _id: '16' name: SFB 901 - Subprojekt C4 - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 15th Workshop on Approximation and Online Algorithms (WAOA) publisher: Springer series_title: Lecture Notes in Computer Science status: public title: Non-Clairvoyant Scheduling to Minimize Max Flow Time on a Machine with Setup Times type: conference user_id: '477' volume: 10787 year: '2017' ... --- _id: '59' abstract: - lang: eng text: We consider a scheduling problem on $m$ identical processors sharing an arbitrarily divisible resource. In addition to assigning jobs to processors, the scheduler must distribute the resource among the processors (e.g., for three processors in shares of 20\%, 15\%, and 65\%) and adjust this distribution over time. Each job $j$ comes with a size $p_j \in \mathbb{R}$ and a resource requirement $r_j > 0$. Jobs do not benefit when receiving a share larger than $r_j$ of the resource. But providing them with a fraction of the resource requirement causes a linear decrease in the processing efficiency. We seek a (non-preemptive) job and resource assignment minimizing the makespan.Our main result is an efficient approximation algorithm which achieves an approximation ratio of $2 + 1/(m-2)$. It can be improved to an (asymptotic) ratio of $1 + 1/(m-1)$ if all jobs have unit size. Our algorithms also imply new results for a well-known bin packing problem with splittable items and a restricted number of allowed item parts per bin.Based upon the above solution, we also derive an approximation algorithm with similar guarantees for a setting in which we introduce so-called tasks each containing several jobs and where we are interested in the average completion time of tasks (a task is completed when all its jobs are completed). author: - first_name: Peter full_name: Kling, Peter last_name: Kling - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Sören full_name: Riechers, Sören last_name: Riechers - first_name: Alexander full_name: Skopalik, Alexander id: '40384' last_name: Skopalik citation: ama: 'Kling P, Mäcker A, Riechers S, Skopalik A. Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ; 2017:123--132. doi:10.1145/3087556.3087578' apa: 'Kling, P., Mäcker, A., Riechers, S., & Skopalik, A. (2017). Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource. In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (pp. 123--132). https://doi.org/10.1145/3087556.3087578' bibtex: '@inproceedings{Kling_Mäcker_Riechers_Skopalik_2017, title={Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource}, DOI={10.1145/3087556.3087578}, booktitle={Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}, author={Kling, Peter and Mäcker, Alexander and Riechers, Sören and Skopalik, Alexander}, year={2017}, pages={123--132} }' chicago: 'Kling, Peter, Alexander Mäcker, Sören Riechers, and Alexander Skopalik. “Sharing Is Caring: Multiprocessor Scheduling with a Sharable Resource.” In Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 123--132, 2017. https://doi.org/10.1145/3087556.3087578.' ieee: 'P. Kling, A. Mäcker, S. Riechers, and A. Skopalik, “Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource,” in Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 123--132.' mla: 'Kling, Peter, et al. “Sharing Is Caring: Multiprocessor Scheduling with a Sharable Resource.” Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 123--132, doi:10.1145/3087556.3087578.' short: 'P. Kling, A. Mäcker, S. Riechers, A. Skopalik, in: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2017, pp. 123--132.' date_created: 2017-10-17T12:41:02Z date_updated: 2022-01-06T07:02:46Z ddc: - '040' department: - _id: '63' - _id: '541' doi: 10.1145/3087556.3087578 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T13:17:33Z date_updated: 2018-03-21T13:17:33Z file_id: '1578' file_name: 59-progress.pdf file_size: 784867 relation: main_file success: 1 file_date_updated: 2018-03-21T13:17:33Z has_accepted_license: '1' language: - iso: eng page: 123--132 project: - _id: '1' name: SFB 901 - _id: '7' name: SFB 901 - Subprojekt A3 - _id: '4' name: SFB 901 - Project Area C - _id: '16' name: SFB 901 - Subproject C4 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) status: public title: 'Sharing is Caring: Multiprocessor Scheduling with a Sharable Resource' type: conference user_id: '477' year: '2017' ... --- _id: '706' author: - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Manuel full_name: Malatyali, Manuel last_name: Malatyali - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers citation: ama: Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Cost-efficient Scheduling on Machines from the Cloud. Journal of Combinatorial Optimization. 2017;36(4):1168-1194. doi:10.1007/s10878-017-0198-x apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2017). Cost-efficient Scheduling on Machines from the Cloud. Journal of Combinatorial Optimization, 36(4), 1168–1194. https://doi.org/10.1007/s10878-017-0198-x bibtex: '@article{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2017, title={Cost-efficient Scheduling on Machines from the Cloud}, volume={36}, DOI={10.1007/s10878-017-0198-x}, number={4}, journal={Journal of Combinatorial Optimization}, publisher={Springer}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2017}, pages={1168–1194} }' chicago: 'Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” Journal of Combinatorial Optimization 36, no. 4 (2017): 1168–94. https://doi.org/10.1007/s10878-017-0198-x.' ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient Scheduling on Machines from the Cloud,” Journal of Combinatorial Optimization, vol. 36, no. 4, pp. 1168–1194, 2017. mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.” Journal of Combinatorial Optimization, vol. 36, no. 4, Springer, 2017, pp. 1168–94, doi:10.1007/s10878-017-0198-x. short: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, Journal of Combinatorial Optimization 36 (2017) 1168–1194. date_created: 2017-11-15T10:21:34Z date_updated: 2022-01-06T07:03:27Z ddc: - '040' department: - _id: '63' doi: 10.1007/s10878-017-0198-x file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-14T12:21:34Z date_updated: 2018-03-14T12:21:34Z file_id: '1210' file_name: 706-chp_3A10.1007_2F978-3-319-48749-6_42.pdf file_size: 608614 relation: main_file success: 1 file_date_updated: 2018-03-14T12:21:34Z has_accepted_license: '1' intvolume: ' 36' issue: '4' language: - iso: eng page: 1168-1194 project: - _id: '1' name: SFB 901 - _id: '16' name: SFB 901 - Subprojekt C4 - _id: '4' name: SFB 901 - Project Area C publication: Journal of Combinatorial Optimization publisher: Springer status: public title: Cost-efficient Scheduling on Machines from the Cloud type: journal_article user_id: '15415' volume: 36 year: '2017' ... --- _id: '16461' author: - first_name: Pascal full_name: Bemmann, Pascal last_name: Bemmann - first_name: Felix full_name: Biermeier, Felix last_name: Biermeier - first_name: Jan full_name: Bürmann, Jan last_name: Bürmann - first_name: Arne full_name: Kemper, Arne last_name: Kemper - first_name: Till full_name: Knollmann, Till id: '39241' last_name: Knollmann orcid: 0000-0003-2014-4696 - first_name: Steffen full_name: Knorr, Steffen last_name: Knorr - first_name: Nils full_name: Kothe, Nils last_name: Kothe - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Manuel full_name: Malatyali, Manuel id: '41265' last_name: Malatyali - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers - first_name: Johannes Sebastian full_name: Schaefer, Johannes Sebastian id: '30291' last_name: Schaefer - first_name: Jannik full_name: Sundermeier, Jannik id: '38705' last_name: Sundermeier citation: ama: 'Bemmann P, Biermeier F, Bürmann J, et al. Monitoring of Domain-Related Problems in Distributed Data Streams. In: Structural Information and Communication Complexity. ; 2017. doi:10.1007/978-3-319-72050-0_13' apa: Bemmann, P., Biermeier, F., Bürmann, J., Kemper, A., Knollmann, T., Knorr, S., Kothe, N., Mäcker, A., Malatyali, M., Meyer auf der Heide, F., Riechers, S., Schaefer, J. S., & Sundermeier, J. (2017). Monitoring of Domain-Related Problems in Distributed Data Streams. In Structural Information and Communication Complexity. https://doi.org/10.1007/978-3-319-72050-0_13 bibtex: '@inbook{Bemmann_Biermeier_Bürmann_Kemper_Knollmann_Knorr_Kothe_Mäcker_Malatyali_Meyer auf der Heide_et al._2017, place={Cham}, title={Monitoring of Domain-Related Problems in Distributed Data Streams}, DOI={10.1007/978-3-319-72050-0_13}, booktitle={Structural Information and Communication Complexity}, author={Bemmann, Pascal and Biermeier, Felix and Bürmann, Jan and Kemper, Arne and Knollmann, Till and Knorr, Steffen and Kothe, Nils and Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and et al.}, year={2017} }' chicago: Bemmann, Pascal, Felix Biermeier, Jan Bürmann, Arne Kemper, Till Knollmann, Steffen Knorr, Nils Kothe, et al. “Monitoring of Domain-Related Problems in Distributed Data Streams.” In Structural Information and Communication Complexity. Cham, 2017. https://doi.org/10.1007/978-3-319-72050-0_13. ieee: P. Bemmann et al., “Monitoring of Domain-Related Problems in Distributed Data Streams,” in Structural Information and Communication Complexity, Cham, 2017. mla: Bemmann, Pascal, et al. “Monitoring of Domain-Related Problems in Distributed Data Streams.” Structural Information and Communication Complexity, 2017, doi:10.1007/978-3-319-72050-0_13. short: 'P. Bemmann, F. Biermeier, J. Bürmann, A. Kemper, T. Knollmann, S. Knorr, N. Kothe, A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, J.S. Schaefer, J. Sundermeier, in: Structural Information and Communication Complexity, Cham, 2017.' date_created: 2020-04-08T07:20:20Z date_updated: 2022-01-06T06:52:50Z department: - _id: '63' doi: 10.1007/978-3-319-72050-0_13 external_id: arxiv: - 'arXiv:1706.03568 ' language: - iso: eng place: Cham publication: Structural Information and Communication Complexity publication_identifier: isbn: - '9783319720494' - '9783319720500' issn: - 0302-9743 - 1611-3349 publication_status: published status: public title: Monitoring of Domain-Related Problems in Distributed Data Streams type: book_chapter user_id: '15415' year: '2017' ... --- _id: '207' abstract: - lang: eng text: We consider a scheduling problem where machines need to be rented from the cloud in order to process jobs. There are two types of machines available which can be rented for machine-type dependent prices and for arbitrary durations. However, a machine-type dependent setup time is required before a machine is available for processing. Jobs arrive online over time, have machine-type dependent sizes and have individual deadlines. The objective is to rent machines and schedule jobs so as to meet all deadlines while minimizing the rental cost. Since we observe the slack of jobs to have a fundamental influence on the competitiveness, we study the model when instances are parameterized by their (minimum) slack. An instance is called to have a slack of $\beta$ if, for all jobs, the difference between the job's release time and the latest point in time at which it needs to be started is at least $\beta$. While for $\beta series = {LNCS} author: - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Manuel full_name: Malatyali, Manuel last_name: Malatyali - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers citation: ama: 'Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Cost-efficient Scheduling on Machines from the Cloud. In: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA). ; 2016:578--592. doi:10.1007/978-3-319-48749-6_42' apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2016). Cost-efficient Scheduling on Machines from the Cloud. In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) (pp. 578--592). https://doi.org/10.1007/978-3-319-48749-6_42 bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2016, title={Cost-efficient Scheduling on Machines from the Cloud}, DOI={10.1007/978-3-319-48749-6_42}, booktitle={Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2016}, pages={578--592} }' chicago: Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 578--592, 2016. https://doi.org/10.1007/978-3-319-48749-6_42. ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient Scheduling on Machines from the Cloud,” in Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 578--592. mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.” Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 578--592, doi:10.1007/978-3-319-48749-6_42. short: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 578--592.' date_created: 2017-10-17T12:41:32Z date_updated: 2022-01-06T06:54:33Z ddc: - '000' department: - _id: '63' doi: 10.1007/978-3-319-48749-6_42 file: - access_level: closed content_type: application/pdf creator: ups date_created: 2018-11-02T14:18:51Z date_updated: 2018-11-02T14:18:51Z file_id: '5268' file_name: Cost-EfficientSchedulingOnMach.pdf file_size: 608614 relation: main_file success: 1 file_date_updated: 2018-11-02T14:18:51Z has_accepted_license: '1' language: - iso: eng page: 578--592 project: - _id: '1' name: SFB 901 - _id: '16' name: SFB 901 - Subprojekt C4 - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) status: public title: Cost-efficient Scheduling on Machines from the Cloud type: conference user_id: '477' year: '2016' ... --- _id: '157' abstract: - lang: eng text: Consider a scheduling problem in which a set of jobs with interjob communication, canonically represented by a weighted tree, needs to be scheduled on m parallel processors interconnected by a shared communication channel. In each time step, we may allow any processed job to use a certain capacity of the channel in order to satisfy (parts of) its communication demands to adjacent jobs processed in parallel. The goal is to find a schedule that minimizes the makespan and in which communication demands of all jobs are satisfied.We show that this problem is NP-hard in the strong sense even if the number of processors and the maximum degree of the underlying tree is constant.Consequently, we design and analyze simple approximation algorithms with asymptotic approximation ratio 2-2/m in case of paths and a ratio of 5/2 in case of arbitrary trees. author: - first_name: Jürgen full_name: König, Jürgen last_name: König - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers citation: ama: 'König J, Mäcker A, Meyer auf der Heide F, Riechers S. Scheduling with Interjob Communication on Parallel Processors. In: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA). LNCS. ; 2016:563--577. doi:10.1007/978-3-319-48749-6_41' apa: König, J., Mäcker, A., Meyer auf der Heide, F., & Riechers, S. (2016). Scheduling with Interjob Communication on Parallel Processors. In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) (pp. 563--577). https://doi.org/10.1007/978-3-319-48749-6_41 bibtex: '@inproceedings{König_Mäcker_Meyer auf der Heide_Riechers_2016, series={LNCS}, title={Scheduling with Interjob Communication on Parallel Processors}, DOI={10.1007/978-3-319-48749-6_41}, booktitle={Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA)}, author={König, Jürgen and Mäcker, Alexander and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2016}, pages={563--577}, collection={LNCS} }' chicago: König, Jürgen, Alexander Mäcker, Friedhelm Meyer auf der Heide, and Sören Riechers. “Scheduling with Interjob Communication on Parallel Processors.” In Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 563--577. LNCS, 2016. https://doi.org/10.1007/978-3-319-48749-6_41. ieee: J. König, A. Mäcker, F. Meyer auf der Heide, and S. Riechers, “Scheduling with Interjob Communication on Parallel Processors,” in Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 563--577. mla: König, Jürgen, et al. “Scheduling with Interjob Communication on Parallel Processors.” Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 563--577, doi:10.1007/978-3-319-48749-6_41. short: 'J. König, A. Mäcker, F. Meyer auf der Heide, S. Riechers, in: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA), 2016, pp. 563--577.' date_created: 2017-10-17T12:41:22Z date_updated: 2022-01-06T06:52:32Z ddc: - '040' department: - _id: '63' doi: 10.1007/978-3-319-48749-6_41 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T12:50:29Z date_updated: 2018-03-21T12:50:29Z file_id: '1549' file_name: 157-chp_3A10.1007_2F978-3-319-48749-6_41.pdf file_size: 753147 relation: main_file success: 1 file_date_updated: 2018-03-21T12:50:29Z has_accepted_license: '1' page: 563--577 project: - _id: '1' name: SFB 901 - _id: '16' name: SFB 901 - Subprojekt C4 - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA) series_title: LNCS status: public title: Scheduling with Interjob Communication on Parallel Processors type: conference user_id: '15504' year: '2016' ... --- _id: '16396' abstract: - lang: eng text: "We consider a scheduling problem where machines need to be rented from the\r\ncloud in order to process jobs. There are two types of machines available which\r\ncan be rented for machine-type dependent prices and for arbitrary durations.\r\nHowever, a machine-type dependent setup time is required before a machine is\r\navailable for processing. Jobs arrive online over time, have machine-type\r\ndependent sizes and have individual deadlines. The objective is to rent\r\nmachines and schedule jobs so as to meet all deadlines while minimizing the\r\nrental cost.\r\n Since we observe the slack of jobs to have a fundamental influence on the\r\ncompetitiveness, we study the model when instances are parameterized by their\r\n(minimum) slack. An instance is called to have a slack of $\\beta$ if, for all\r\njobs, the difference between the job's release time and the latest point in\r\ntime at which it needs to be started is at least $\\beta$. While for $\\beta < s$\r\nno finite competitiveness is possible, our main result is an\r\n$O(\\frac{c}{\\varepsilon} + \\frac{1}{\\varepsilon^3})$-competitive online\r\nalgorithm for $\\beta = (1+\\varepsilon)s$ with $\\frac{1}{s} \\leq \\varepsilon\r\n\\leq 1$, where $s$ and $c$ denotes the largest setup time and the cost ratio of\r\nthe machine-types, respectively. It is complemented by a lower bound of\r\n$\\Omega(\\frac{c}{\\varepsilon})$." author: - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Manuel full_name: Malatyali, Manuel last_name: Malatyali - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers citation: ama: Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Cost-efficient Scheduling on Machines from the Cloud. arXiv:160901184. 2016. apa: Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2016). Cost-efficient Scheduling on Machines from the Cloud. ArXiv:1609.01184. bibtex: '@article{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2016, title={Cost-efficient Scheduling on Machines from the Cloud}, journal={arXiv:1609.01184}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2016} }' chicago: Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Cost-Efficient Scheduling on Machines from the Cloud.” ArXiv:1609.01184, 2016. ieee: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Cost-efficient Scheduling on Machines from the Cloud,” arXiv:1609.01184. 2016. mla: Mäcker, Alexander, et al. “Cost-Efficient Scheduling on Machines from the Cloud.” ArXiv:1609.01184, 2016. short: A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, ArXiv:1609.01184 (2016). date_created: 2020-04-03T09:24:28Z date_updated: 2022-01-06T06:52:50Z department: - _id: '63' external_id: arxiv: - '1609.01184' language: - iso: eng publication: arXiv:1609.01184 status: public title: Cost-efficient Scheduling on Machines from the Cloud type: preprint user_id: '15415' year: '2016' ... --- _id: '274' abstract: - lang: eng text: Consider the problem in which n jobs that are classified into k types are to be scheduled on m identical machines without preemption. A machine requires a proper setup taking s time units before processing jobs of a given type. The objective is to minimize the makespan of the resulting schedule. We design and analyze an approximation algorithm that runs in time polynomial in n,m and k and computes a solution with an approximation factor that can be made arbitrarily close to 3/2. author: - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Manuel full_name: Malatyali, Manuel last_name: Malatyali - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers citation: ama: 'Mäcker A, Malatyali M, Meyer auf der Heide F, Riechers S. Non-preemptive Scheduling on Machines with Setup Times. In: Dehne F, Sack JR, Stege U, eds. Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings. Lecture Notes in Computer Science. ; 2015:542--553. doi:10.1007/978-3-319-21840-3_45' apa: 'Mäcker, A., Malatyali, M., Meyer auf der Heide, F., & Riechers, S. (2015). Non-preemptive Scheduling on Machines with Setup Times. In F. Dehne, J. R. Sack, & U. Stege (Eds.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings (pp. 542--553). https://doi.org/10.1007/978-3-319-21840-3_45' bibtex: '@inproceedings{Mäcker_Malatyali_Meyer auf der Heide_Riechers_2015, series={Lecture Notes in Computer Science}, title={Non-preemptive Scheduling on Machines with Setup Times}, DOI={10.1007/978-3-319-21840-3_45}, booktitle={Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings}, author={Mäcker, Alexander and Malatyali, Manuel and Meyer auf der Heide, Friedhelm and Riechers, Sören}, editor={Dehne, Frank and Sack, Jörg Rüdiger and Stege, UlrikeEditors}, year={2015}, pages={542--553}, collection={Lecture Notes in Computer Science} }' chicago: 'Mäcker, Alexander, Manuel Malatyali, Friedhelm Meyer auf der Heide, and Sören Riechers. “Non-Preemptive Scheduling on Machines with Setup Times.” In Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, edited by Frank Dehne, Jörg Rüdiger Sack, and Ulrike Stege, 542--553. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-319-21840-3_45.' ieee: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, and S. Riechers, “Non-preemptive Scheduling on Machines with Setup Times,” in Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, 2015, pp. 542--553.' mla: 'Mäcker, Alexander, et al. “Non-Preemptive Scheduling on Machines with Setup Times.” Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, edited by Frank Dehne et al., 2015, pp. 542--553, doi:10.1007/978-3-319-21840-3_45.' short: 'A. Mäcker, M. Malatyali, F. Meyer auf der Heide, S. Riechers, in: F. Dehne, J.R. Sack, U. Stege (Eds.), Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, 2015, pp. 542--553.' date_created: 2017-10-17T12:41:45Z date_updated: 2022-01-06T06:57:39Z ddc: - '040' department: - _id: '63' doi: 10.1007/978-3-319-21840-3_45 editor: - first_name: Frank full_name: Dehne, Frank last_name: Dehne - first_name: Jörg Rüdiger full_name: Sack, Jörg Rüdiger last_name: Sack - first_name: Ulrike full_name: Stege, Ulrike last_name: Stege file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T09:28:34Z date_updated: 2018-03-21T09:28:34Z file_id: '1473' file_name: 274-chp_3A10.1007_2F978-3-319-21840-3_45.pdf file_size: 215498 relation: main_file success: 1 file_date_updated: 2018-03-21T09:28:34Z has_accepted_license: '1' page: 542--553 project: - _id: '1' name: SFB 901 - _id: '16' name: SFB 901 - Subprojekt C4 - _id: '4' name: SFB 901 - Project Area C publication: 'Algorithms and Data Structures: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings' series_title: Lecture Notes in Computer Science status: public title: Non-preemptive Scheduling on Machines with Setup Times type: conference user_id: '15504' year: '2015' ... --- _id: '240' abstract: - lang: eng text: We consider online leasing problems in which demands arrive over time and need to be served by leasing resources. We introduce a new model for these problems such that a resource can be leased for K different durations each incurring a different cost (longer leases cost less per time unit). Each demand i can be served anytime between its arrival ai and its deadline ai+di by a leased resource. The objective is to meet all deadlines while minimizing the total leasing costs. This model is a natural generalization of Meyerson’s ParkingPermitProblem (FOCS 2005) in which di=0 for all i. We propose an online algorithm that is Θ(K+dmaxlmin)-competitive where dmax and lmin denote the largest di and the shortest available lease length, respectively. We also extend the SetCoverLeasing problem by deadlines and give a competitive online algorithm which also improves on existing solutions for the original SetCoverLeasing problem. author: - first_name: Shouwei full_name: Li, Shouwei last_name: Li - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Christine full_name: Markarian, Christine id: '37612' last_name: Markarian - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide - first_name: Sören full_name: Riechers, Sören last_name: Riechers citation: ama: 'Li S, Mäcker A, Markarian C, Meyer auf der Heide F, Riechers S. Towards Flexible Demands in Online Leasing Problems. In: Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science. ; 2015:277--288. doi:10.1007/978-3-319-21398-9_22' apa: Li, S., Mäcker, A., Markarian, C., Meyer auf der Heide, F., & Riechers, S. (2015). Towards Flexible Demands in Online Leasing Problems. In Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON) (pp. 277--288). https://doi.org/10.1007/978-3-319-21398-9_22 bibtex: '@inproceedings{Li_Mäcker_Markarian_Meyer auf der Heide_Riechers_2015, series={Lecture Notes in Computer Science}, title={Towards Flexible Demands in Online Leasing Problems}, DOI={10.1007/978-3-319-21398-9_22}, booktitle={Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON)}, author={Li, Shouwei and Mäcker, Alexander and Markarian, Christine and Meyer auf der Heide, Friedhelm and Riechers, Sören}, year={2015}, pages={277--288}, collection={Lecture Notes in Computer Science} }' chicago: Li, Shouwei, Alexander Mäcker, Christine Markarian, Friedhelm Meyer auf der Heide, and Sören Riechers. “Towards Flexible Demands in Online Leasing Problems.” In Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON), 277--288. Lecture Notes in Computer Science, 2015. https://doi.org/10.1007/978-3-319-21398-9_22. ieee: S. Li, A. Mäcker, C. Markarian, F. Meyer auf der Heide, and S. Riechers, “Towards Flexible Demands in Online Leasing Problems,” in Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON), 2015, pp. 277--288. mla: Li, Shouwei, et al. “Towards Flexible Demands in Online Leasing Problems.” Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON), 2015, pp. 277--288, doi:10.1007/978-3-319-21398-9_22. short: 'S. Li, A. Mäcker, C. Markarian, F. Meyer auf der Heide, S. Riechers, in: Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON), 2015, pp. 277--288.' date_created: 2017-10-17T12:41:38Z date_updated: 2022-01-06T06:56:05Z ddc: - '040' department: - _id: '63' doi: 10.1007/978-3-319-21398-9_22 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-21T10:28:50Z date_updated: 2018-03-21T10:28:50Z file_id: '1498' file_name: 240-chp_3A10.1007_2F978-3-319-21398-9_22.pdf file_size: 264482 relation: main_file success: 1 file_date_updated: 2018-03-21T10:28:50Z has_accepted_license: '1' page: 277--288 project: - _id: '1' name: SFB 901 - _id: '16' name: SFB 901 - Subprojekt C4 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A - _id: '4' name: SFB 901 - Project Area C publication: Proceedings of the 21st Annual International Computing and Combinatorics Conference (COCOON) series_title: Lecture Notes in Computer Science status: public title: Towards Flexible Demands in Online Leasing Problems type: conference user_id: '15504' year: '2015' ... --- _id: '367' abstract: - lang: eng text: Online social networks are attracting billions of nowadays, both on a global scale as well as in social enterprise networks. Using distributed hash tables and peer-to-peer technology allows online social networks to be operated securely and efficiently only by using the resources of the user devices, thus alleviating censorship or data misuse by a single network operator. In this paper, we address the challenges that arise in implementing reliably and conveniently to use distributed data structures, such as lists or sets, in such a distributed hash-tablebased online social network. We present a secure, distributed list data structure that manages the list entries in several buckets in the distributed hash table. The list entries are authenticated, integrity is maintained and access control for single users and also groups is integrated. The approach for secure distributed lists is also applied for prefix trees and sets, and implemented and evaluated in a peer-to-peer framework for social networks. Evaluation shows that the distributed data structure is convenient and efficient to use and that the requirements on security hold. author: - first_name: Jens full_name: Janiuk, Jens last_name: Janiuk - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Kalman full_name: Graffi, Kalman last_name: Graffi citation: ama: 'Janiuk J, Mäcker A, Graffi K. Secure Distributed Data Structures for Peer-to-Peer-based Social Networks. In: Proceedings of the International Conference on Collaboration Technologies and Systems (CTS). ; 2014:396-405. doi:10.1109/CTS.2014.6867595' apa: Janiuk, J., Mäcker, A., & Graffi, K. (2014). Secure Distributed Data Structures for Peer-to-Peer-based Social Networks. In Proceedings of the International Conference on Collaboration Technologies and Systems (CTS) (pp. 396–405). https://doi.org/10.1109/CTS.2014.6867595 bibtex: '@inproceedings{Janiuk_Mäcker_Graffi_2014, title={Secure Distributed Data Structures for Peer-to-Peer-based Social Networks}, DOI={10.1109/CTS.2014.6867595}, booktitle={Proceedings of the International Conference on Collaboration Technologies and Systems (CTS)}, author={Janiuk, Jens and Mäcker, Alexander and Graffi, Kalman}, year={2014}, pages={396–405} }' chicago: Janiuk, Jens, Alexander Mäcker, and Kalman Graffi. “Secure Distributed Data Structures for Peer-to-Peer-Based Social Networks.” In Proceedings of the International Conference on Collaboration Technologies and Systems (CTS), 396–405, 2014. https://doi.org/10.1109/CTS.2014.6867595. ieee: J. Janiuk, A. Mäcker, and K. Graffi, “Secure Distributed Data Structures for Peer-to-Peer-based Social Networks,” in Proceedings of the International Conference on Collaboration Technologies and Systems (CTS), 2014, pp. 396–405. mla: Janiuk, Jens, et al. “Secure Distributed Data Structures for Peer-to-Peer-Based Social Networks.” Proceedings of the International Conference on Collaboration Technologies and Systems (CTS), 2014, pp. 396–405, doi:10.1109/CTS.2014.6867595. short: 'J. Janiuk, A. Mäcker, K. Graffi, in: Proceedings of the International Conference on Collaboration Technologies and Systems (CTS), 2014, pp. 396–405.' date_created: 2017-10-17T12:42:03Z date_updated: 2022-01-06T06:59:29Z ddc: - '040' department: - _id: '79' doi: 10.1109/CTS.2014.6867595 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-20T07:18:12Z date_updated: 2018-03-20T07:18:12Z file_id: '1404' file_name: 367-cts_conf.pdf file_size: 647997 relation: main_file success: 1 file_date_updated: 2018-03-20T07:18:12Z has_accepted_license: '1' language: - iso: eng page: 396-405 project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publication: Proceedings of the International Conference on Collaboration Technologies and Systems (CTS) status: public title: Secure Distributed Data Structures for Peer-to-Peer-based Social Networks type: conference user_id: '477' year: '2014' ... --- _id: '380' abstract: - lang: eng text: 'Network creation games model the creation and usage costs of networks formed by n selfish nodes. Each node v can buy a set of edges, each for a fixed price α > 0. Its goal is to minimize its private costs, i.e., the sum (SUM-game, Fabrikant et al., PODC 2003) or maximum (MAX-game, Demaine et al., PODC 2007) of distances from v to all other nodes plus the prices of the bought edges. The above papers show the existence of Nash equilibria as well as upper and lower bounds for the prices of anarchy and stability. In several subsequent papers, these bounds were improved for a wide range of prices α. In this paper, we extend these models by incorporating quality-of-service aspects: Each edge cannot only be bought at a fixed quality (edge length one) for a fixed price α. Instead, we assume that quality levels (i.e., edge lengths) are varying in a fixed interval [βˇ,β^] , 0 series = {LNCS}' author: - first_name: Andreas full_name: Cord-Landwehr, Andreas last_name: Cord-Landwehr - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker - first_name: Friedhelm full_name: Meyer auf der Heide, Friedhelm id: '15523' last_name: Meyer auf der Heide citation: ama: 'Cord-Landwehr A, Mäcker A, Meyer auf der Heide F. Quality of Service in Network Creation Games. In: Proceedings of the 10th International Conference on Web and Internet Economics (WINE). ; 2014:423-428. doi:10.1007/978-3-319-13129-0_34' apa: Cord-Landwehr, A., Mäcker, A., & Meyer auf der Heide, F. (2014). Quality of Service in Network Creation Games. In Proceedings of the 10th International Conference on Web and Internet Economics (WINE) (pp. 423–428). https://doi.org/10.1007/978-3-319-13129-0_34 bibtex: '@inproceedings{Cord-Landwehr_Mäcker_Meyer auf der Heide_2014, title={Quality of Service in Network Creation Games}, DOI={10.1007/978-3-319-13129-0_34}, booktitle={Proceedings of the 10th International Conference on Web and Internet Economics (WINE)}, author={Cord-Landwehr, Andreas and Mäcker, Alexander and Meyer auf der Heide, Friedhelm}, year={2014}, pages={423–428} }' chicago: Cord-Landwehr, Andreas, Alexander Mäcker, and Friedhelm Meyer auf der Heide. “Quality of Service in Network Creation Games.” In Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 423–28, 2014. https://doi.org/10.1007/978-3-319-13129-0_34. ieee: A. Cord-Landwehr, A. Mäcker, and F. Meyer auf der Heide, “Quality of Service in Network Creation Games,” in Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 2014, pp. 423–428. mla: Cord-Landwehr, Andreas, et al. “Quality of Service in Network Creation Games.” Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 2014, pp. 423–28, doi:10.1007/978-3-319-13129-0_34. short: 'A. Cord-Landwehr, A. Mäcker, F. Meyer auf der Heide, in: Proceedings of the 10th International Conference on Web and Internet Economics (WINE), 2014, pp. 423–428.' date_created: 2017-10-17T12:42:06Z date_updated: 2022-01-06T06:59:36Z ddc: - '040' department: - _id: '63' doi: 10.1007/978-3-319-13129-0_34 file: - access_level: closed content_type: application/pdf creator: florida date_created: 2018-03-20T07:05:59Z date_updated: 2018-03-20T07:05:59Z file_id: '1394' file_name: 380-WINE2014.pdf file_size: 166640 relation: main_file success: 1 file_date_updated: 2018-03-20T07:05:59Z has_accepted_license: '1' page: 423-428 project: - _id: '1' name: SFB 901 - _id: '2' name: SFB 901 - Project Area A - _id: '5' name: SFB 901 - Subproject A1 publication: Proceedings of the 10th International Conference on Web and Internet Economics (WINE) status: public title: Quality of Service in Network Creation Games type: conference user_id: '15504' year: '2014' ... --- _id: '526' author: - first_name: Alexander full_name: Mäcker, Alexander id: '13536' last_name: Mäcker citation: ama: Mäcker A. Greedy Network Creation With Heavy And Light Edges. Universität Paderborn; 2013. apa: Mäcker, A. (2013). Greedy Network Creation With Heavy And Light Edges. Universität Paderborn. bibtex: '@book{Mäcker_2013, title={Greedy Network Creation With Heavy And Light Edges}, publisher={Universität Paderborn}, author={Mäcker, Alexander}, year={2013} }' chicago: Mäcker, Alexander. Greedy Network Creation With Heavy And Light Edges. Universität Paderborn, 2013. ieee: A. Mäcker, Greedy Network Creation With Heavy And Light Edges. Universität Paderborn, 2013. mla: Mäcker, Alexander. Greedy Network Creation With Heavy And Light Edges. Universität Paderborn, 2013. short: A. Mäcker, Greedy Network Creation With Heavy And Light Edges, Universität Paderborn, 2013. date_created: 2017-10-17T12:42:35Z date_updated: 2022-01-06T07:01:48Z project: - _id: '1' name: SFB 901 - _id: '5' name: SFB 901 - Subprojekt A1 - _id: '2' name: SFB 901 - Project Area A publisher: Universität Paderborn status: public title: Greedy Network Creation With Heavy And Light Edges type: mastersthesis user_id: '15504' year: '2013' ...