Published in: OASIcs, Volume 143, 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)
Diogo Ferreira and Ibéria Medeiros. Discovering and Repairing Flaws in C Binaries Without Requiring Codebase and Instrumentation. In 30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026). Open Access Series in Informatics (OASIcs), Volume 143, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)
@InProceedings{ferreira_et_al:OASIcs.AEiC.2026.2,
author = {Ferreira, Diogo and Medeiros, Ib\'{e}ria},
title = {{Discovering and Repairing Flaws in C Binaries Without Requiring Codebase and Instrumentation}},
booktitle = {30th Ada-Europe International Conference on Reliable Software Technologies (AEiC 2026)},
pages = {2:1--2:19},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-425-3},
ISSN = {2190-6807},
year = {2026},
volume = {143},
editor = {Filieri, Antonio and Backeman, Peter},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.AEiC.2026.2},
URN = {urn:nbn:de:0030-drops-259209},
doi = {10.4230/OASIcs.AEiC.2026.2},
annote = {Keywords: Buffer Overflow Vulnerabilities, Binary Patching, Reverse Engineering, Static Analysis, Software Security}
}
Published in: TGDK, Volume 3, Issue 2 (2025). Transactions on Graph Data and Knowledge, Volume 3, Issue 2
Arnab Sharma, N'Dah Jean Kouagou, and Axel-Cyrille Ngonga Ngomo. Resilience in Knowledge Graph Embeddings. In Transactions on Graph Data and Knowledge (TGDK), Volume 3, Issue 2, pp. 1:1-1:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@Article{sharma_et_al:TGDK.3.2.1,
author = {Sharma, Arnab and Kouagou, N'Dah Jean and Ngomo, Axel-Cyrille Ngonga},
title = {{Resilience in Knowledge Graph Embeddings}},
journal = {Transactions on Graph Data and Knowledge},
pages = {1:1--1:38},
ISSN = {2942-7517},
year = {2025},
volume = {3},
number = {2},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/TGDK.3.2.1},
URN = {urn:nbn:de:0030-drops-248117},
doi = {10.4230/TGDK.3.2.1},
annote = {Keywords: Knowledge graphs, Resilience, Robustness}
}
Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)
Jakub Balabán, Matthias Gehnen, Henri Lotze, Finn Seesemann, and Moritz Stocker. Online Knapsack Problems with Estimates. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 12:1-12:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{balaban_et_al:LIPIcs.MFCS.2025.12,
author = {Balab\'{a}n, Jakub and Gehnen, Matthias and Lotze, Henri and Seesemann, Finn and Stocker, Moritz},
title = {{Online Knapsack Problems with Estimates}},
booktitle = {50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
pages = {12:1--12:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-388-1},
ISSN = {1868-8969},
year = {2025},
volume = {345},
editor = {Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.12},
URN = {urn:nbn:de:0030-drops-241190},
doi = {10.4230/LIPIcs.MFCS.2025.12},
annote = {Keywords: Knapsack, Online Knapsack, Removability, Estimate, Prediction}
}
Published in: OASIcs, Volume 135, 14th Symposium on Languages, Applications and Technologies (SLATE 2025)
André Freitas, Tiago Baptista, and Pedro Rangel Henriques. Bridging Language Barriers: A Comparative Review and Empirical Evaluation of Source-To-Source Transpilers. In 14th Symposium on Languages, Applications and Technologies (SLATE 2025). Open Access Series in Informatics (OASIcs), Volume 135, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{freitas_et_al:OASIcs.SLATE.2025.11,
author = {Freitas, Andr\'{e} and Baptista, Tiago and Henriques, Pedro Rangel},
title = {{Bridging Language Barriers: A Comparative Review and Empirical Evaluation of Source-To-Source Transpilers}},
booktitle = {14th Symposium on Languages, Applications and Technologies (SLATE 2025)},
pages = {11:1--11:16},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-387-4},
ISSN = {2190-6807},
year = {2025},
volume = {135},
editor = {Baptista, Jorge and Barateiro, Jos\'{e}},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2025.11},
URN = {urn:nbn:de:0030-drops-236911},
doi = {10.4230/OASIcs.SLATE.2025.11},
annote = {Keywords: Source-to-source translation, Code transformation, Parsing, Lexical analysis, Syntax analysis, Semantic analysis, Transpilation}
}
Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)
Binqi Sun, Zhihang Wei, Andrea Bastoni, Debayan Roy, Mirco Theile, Tomasz Kloda, Rodolfo Pellizzoni, and Marco Caccamo. Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 2:1-2:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{sun_et_al:LIPIcs.ECRTS.2025.2,
author = {Sun, Binqi and Wei, Zhihang and Bastoni, Andrea and Roy, Debayan and Theile, Mirco and Kloda, Tomasz and Pellizzoni, Rodolfo and Caccamo, Marco},
title = {{Multi-Objective Memory Bandwidth Regulation and Cache Partitioning for Multicore Real-Time Systems}},
booktitle = {37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
pages = {2:1--2:23},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-377-5},
ISSN = {1868-8969},
year = {2025},
volume = {335},
editor = {Mancuso, Renato},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.2},
URN = {urn:nbn:de:0030-drops-235807},
doi = {10.4230/LIPIcs.ECRTS.2025.2},
annote = {Keywords: Multi-objective optimization, memory bandwidth regulation, cache partitioning, partitioned scheduling, real-time systems}
}
Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)
Nasim Samimi, Luca Abeni, Daniel Casini, Mauro Marinoni, Twan Basten, Mitra Nasri, Marc Geilen, and Alessandro Biondi. Enabling Containerisation of Distributed Applications with Real-Time Constraints. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 3:1-3:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{samimi_et_al:LIPIcs.ECRTS.2025.3,
author = {Samimi, Nasim and Abeni, Luca and Casini, Daniel and Marinoni, Mauro and Basten, Twan and Nasri, Mitra and Geilen, Marc and Biondi, Alessandro},
title = {{Enabling Containerisation of Distributed Applications with Real-Time Constraints}},
booktitle = {37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
pages = {3:1--3:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-377-5},
ISSN = {1868-8969},
year = {2025},
volume = {335},
editor = {Mancuso, Renato},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.3},
URN = {urn:nbn:de:0030-drops-235816},
doi = {10.4230/LIPIcs.ECRTS.2025.3},
annote = {Keywords: Kubernetes, real-time containers, SCHED\underlineDEADLINE, KubeRay}
}
Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)
Soumya Ranjan Sahoo, Amalinda Gamage, Niraj Kumar, and Arvind Easwaran. LoRaHART: Hardware-Aware Real-Time Scheduling for LoRa. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 10:1-10:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{sahoo_et_al:LIPIcs.ECRTS.2025.10,
author = {Sahoo, Soumya Ranjan and Gamage, Amalinda and Kumar, Niraj and Easwaran, Arvind},
title = {{LoRaHART: Hardware-Aware Real-Time Scheduling for LoRa}},
booktitle = {37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
pages = {10:1--10:28},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-377-5},
ISSN = {1868-8969},
year = {2025},
volume = {335},
editor = {Mancuso, Renato},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.10},
URN = {urn:nbn:de:0030-drops-235880},
doi = {10.4230/LIPIcs.ECRTS.2025.10},
annote = {Keywords: LoRa, LPWAN, Real-time Scheduling, Hardware Constraints}
}
Published in: LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025)
Kunal Agrawal, Sanjoy Baruah, Jeremy T. Fineman, Alberto Marchetti-Spaccamela, and Jinhao Zhao. Analysis of EDF for Real-Time Multiprocessor Systems with Resource Sharing. In 37th Euromicro Conference on Real-Time Systems (ECRTS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 335, pp. 15:1-15:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{agrawal_et_al:LIPIcs.ECRTS.2025.15,
author = {Agrawal, Kunal and Baruah, Sanjoy and Fineman, Jeremy T. and Marchetti-Spaccamela, Alberto and Zhao, Jinhao},
title = {{Analysis of EDF for Real-Time Multiprocessor Systems with Resource Sharing}},
booktitle = {37th Euromicro Conference on Real-Time Systems (ECRTS 2025)},
pages = {15:1--15:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-377-5},
ISSN = {1868-8969},
year = {2025},
volume = {335},
editor = {Mancuso, Renato},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.15},
URN = {urn:nbn:de:0030-drops-235932},
doi = {10.4230/LIPIcs.ECRTS.2025.15},
annote = {Keywords: Real-Time Scheduling, Non-Clairvoyant Scheduling, EDF, Competitive Analysis, Shared Resources}
}
Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)
Matthew K. L. Wong and Alastair F. Donaldson. WebGlitch: A Randomised Testing Tool for the WebGPU API (Experience Paper). In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 39:1-39:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{wong_et_al:LIPIcs.ECOOP.2025.39,
author = {Wong, Matthew K. L. and Donaldson, Alastair F.},
title = {{WebGlitch: A Randomised Testing Tool for the WebGPU API}},
booktitle = {39th European Conference on Object-Oriented Programming (ECOOP 2025)},
pages = {39:1--39:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-373-7},
ISSN = {1868-8969},
year = {2025},
volume = {333},
editor = {Aldrich, Jonathan and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.39},
URN = {urn:nbn:de:0030-drops-233313},
doi = {10.4230/LIPIcs.ECOOP.2025.39},
annote = {Keywords: Fuzzing, WebGPU, WGSL, API, shaders}
}
Published in: LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1
Benjamin Standaert, Fatima Raadia, Marion Sudvarg, Sanjoy Baruah, Thidapat Chantem, Nathan Fisher, and Christopher Gill. Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks. In LITES, Volume 10, Issue 1 (2025). Leibniz Transactions on Embedded Systems, Volume 10, Issue 1, pp. 3:1-3:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@Article{standaert_et_al:LITES.10.1.3,
author = {Standaert, Benjamin and Raadia, Fatima and Sudvarg, Marion and Baruah, Sanjoy and Chantem, Thidapat and Fisher, Nathan and Gill, Christopher},
title = {{Limited-Preemption EDF Scheduling for Multi-Phase Secure Tasks}},
journal = {Leibniz Transactions on Embedded Systems},
pages = {3:1--3:27},
ISSN = {2199-2002},
year = {2025},
volume = {10},
number = {1},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LITES.10.1.3},
URN = {urn:nbn:de:0030-drops-230799},
doi = {10.4230/LITES.10.1.3},
annote = {Keywords: real-time systems, limited-preemption scheduling, trusted execution environments}
}
Published in: OASIcs, Volume 128, Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)
Afonso Oliveira, Diogo Costa, Gonçalo Moreira, José Martins, and Sandro Pinto. H-MBR: Hypervisor-Level Memory Bandwidth Reservation for Mixed Criticality Systems. In Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025). Open Access Series in Informatics (OASIcs), Volume 128, pp. 4:1-4:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{oliveira_et_al:OASIcs.NG-RES.2025.4,
author = {Oliveira, Afonso and Costa, Diogo and Moreira, Gon\c{c}alo and Martins, Jos\'{e} and Pinto, Sandro},
title = {{H-MBR: Hypervisor-Level Memory Bandwidth Reservation for Mixed Criticality Systems}},
booktitle = {Sixth Workshop on Next Generation Real-Time Embedded Systems (NG-RES 2025)},
pages = {4:1--4:15},
series = {Open Access Series in Informatics (OASIcs)},
ISBN = {978-3-95977-366-9},
ISSN = {2190-6807},
year = {2025},
volume = {128},
editor = {Yomsi, Patrick Meumeu and Wildermann, Stefan},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NG-RES.2025.4},
URN = {urn:nbn:de:0030-drops-229905},
doi = {10.4230/OASIcs.NG-RES.2025.4},
annote = {Keywords: Virtualization, Multi-core Interference, Mixed-Criticality Systems, Arm, Memory Bandwidth Reservation}
}
Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
Noam Touitou. Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 74:1-74:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)
@InProceedings{touitou:LIPIcs.STACS.2025.74,
author = {Touitou, Noam},
title = {{Nearly-Optimal Algorithm for Non-Clairvoyant Service with Delay}},
booktitle = {42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
pages = {74:1--74:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-365-2},
ISSN = {1868-8969},
year = {2025},
volume = {327},
editor = {Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.74},
URN = {urn:nbn:de:0030-drops-228995},
doi = {10.4230/LIPIcs.STACS.2025.74},
annote = {Keywords: Online, Delay, Deadlines, k-server, Non-clairvoyant}
}
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shi Li, Chenyang Xu, and Ruilong Zhang. Polylogarithmic Approximations for Robust s-t Path. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 106:1-106:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ICALP.2024.106,
author = {Li, Shi and Xu, Chenyang and Zhang, Ruilong},
title = {{Polylogarithmic Approximations for Robust s-t Path}},
booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
pages = {106:1--106:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-322-5},
ISSN = {1868-8969},
year = {2024},
volume = {297},
editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.106},
URN = {urn:nbn:de:0030-drops-202497},
doi = {10.4230/LIPIcs.ICALP.2024.106},
annote = {Keywords: Approximation Algorithm, Randomized LP Rounding, Robust s-t Path}
}
Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1
Hong Wu, Zhe Wang, Kewen Wang, Pouya Ghiasnezhad Omran, and Jiangmeng Li. Rule Learning over Knowledge Graphs: A Review. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@Article{wu_et_al:TGDK.1.1.7,
author = {Wu, Hong and Wang, Zhe and Wang, Kewen and Omran, Pouya Ghiasnezhad and Li, Jiangmeng},
title = {{Rule Learning over Knowledge Graphs: A Review}},
journal = {Transactions on Graph Data and Knowledge},
pages = {7:1--7:23},
ISSN = {2942-7517},
year = {2023},
volume = {1},
number = {1},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.7},
URN = {urn:nbn:de:0030-drops-194813},
doi = {10.4230/TGDK.1.1.7},
annote = {Keywords: Rule learning, Knowledge graphs, Link prediction}
}
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Christoph Damerius, Peter Kling, Minming Li, Chenyang Xu, and Ruilong Zhang. Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{damerius_et_al:LIPIcs.ESA.2023.38,
author = {Damerius, Christoph and Kling, Peter and Li, Minming and Xu, Chenyang and Zhang, Ruilong},
title = {{Scheduling with a Limited Testing Budget: Tight Results for the Offline and Oblivious Settings}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {38:1--38:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.38},
URN = {urn:nbn:de:0030-drops-186915},
doi = {10.4230/LIPIcs.ESA.2023.38},
annote = {Keywords: scheduling, total completion time, makespan, LP rounding, competitive analysis, approximation algorithm, NP hardness, PTAS}
}