dorsal/arxiv
View SchemaAlgorithmic Reductions: Network Flow and NP-Completeness in Real-World Scheduling Problems
| Authors | Anay Sinhal, Arpana Sinhal, Amit Sinhal, Amit Hirawat |
|---|---|
| Categories | |
| ArXiv ID | 2601.06737vv1 |
| URL | https://arxiv.org/abs/2601.06737 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
This paper presents two real-world scheduling problems and their algorithmic solutions through polynomial-time reductions. First, we address the Hospital Patient-to-Bed Assignment problem, demonstrating its reduction to Maximum Bipartite Matching and solution via Network Flow algorithms. Second, we tackle the University Course Scheduling problem, proving its NP-Completeness through reduction from Graph Coloring and providing greedy approximation algorithms. Both problems are implemented in Python, with experimental results validating theoretical complexity analyses. Our Network Flow solution achieves O(n2.51) empirical complexity, while the greedy coloring algorithms demonstrate O(n2) behavior with approximation ratios consistently below the theoretical delta + 1 bound.
{
"annotation_id": "e9a32de2-4210-4554-b4d5-6ad887ebac1c",
"date_created": "2026-02-17T05:53:08.096000Z",
"date_modified": "2026-02-17T05:53:08.096000Z",
"file_hash": "f45b1b05d2d0c2c5f71d495df7f9a8abbdadcb445ef558eaf6b1e739d3c944e9",
"private": false,
"record": {
"abstract": "This paper presents two real-world scheduling problems and their algorithmic solutions through polynomial-time reductions. First, we address the Hospital Patient-to-Bed Assignment problem, demonstrating its reduction to Maximum Bipartite Matching and solution via Network Flow algorithms. Second, we tackle the University Course Scheduling problem, proving its NP-Completeness through reduction from Graph Coloring and providing greedy approximation algorithms. Both problems are implemented in Python, with experimental results validating theoretical complexity analyses. Our Network Flow solution achieves O(n2.51) empirical complexity, while the greedy coloring algorithms demonstrate O(n2) behavior with approximation ratios consistently below the theoretical delta + 1 bound.",
"arxiv_id": "2601.06737",
"authors": [
"Anay Sinhal",
"Arpana Sinhal",
"Amit Sinhal",
"Amit Hirawat"
],
"categories": [
"cs.DS"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Algorithmic Reductions: Network Flow and NP-Completeness in Real-World Scheduling Problems",
"url": "https://arxiv.org/abs/2601.06737",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "b2684773-2d71-44cb-8f60-f36d9b0e16b6",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}