{"id":{"repo_id":"njit","oai_identifier":"oai:digitalcommons.njit.edu:dissertations-1777"},"canonical_url":"https://search.dev.ndltd.org/etd/njit/oai:digitalcommons.njit.edu:dissertations-1777","repository":{"repo_id":"njit","name":"NJIT","base_url":"https://digitalcommons.njit.edu/do/oai/"},"display":{"title":"Algorithms and complexity analyses for some combinational optimization problems","abstract":"The main focus of this dissertation is on classical combinatorial optimization problems in two important areas: scheduling and network design. In the area of scheduling, the main interest is in problems in the master-slave model. In this model, each machine is either a master machine or a slave machine. Each job is associated with a preprocessing task, a slave task and a postprocessing task that must be executed in this order. Each slave task has a dedicated slave machine. All the preprocessing and postprocessing tasks share a single master machine or the same set of master machines. A job may also have an arbitrary release time before which the preprocessing task is not available to be processed. The main objective in this dissertation is to minimize the total completion time or the makespan. Both the complexity and algorithmic issues of these problems are considered. It is shown that the problem of minimizing the total completion time is strongly NP-hard even under severe constraints. Various efficient algorithms are designed to minimize the total completion time under various scenarios. In the area of network design, the survivable network design problems are studied first. The input for this problem is an undirected graph G = (V, E), a non-negative cost for each edge, and a nonnegative connectivity requirement r_{uv} for every (unordered) pair of vertices u, v. The goal is to find a minimum-cost subgraph in which each pair of vertices u,v is joined by at least r_{uv} edge (vertex)-disjoint paths. A Polynomial Time Approximation Scheme (PTAS) is designed for the problem when the graph is Euclidean and the connectivity requirement of any point is at most 2. PTASs or Quasi-PTASs are also designed for 2-edge-connectivity problem and biconnectivity problem and their variations in unweighted or weighted planar graphs. Next, the problem of constructing geometric fault-tolerant spanners with low cost and bounded maximum degree is considered. The first result shows that there is a greedy algorithm which constructs fault-tolerant spanners having asymptotically optimal bounds for both the maximum degree and the total cost at the same time. Then an efficient algorithm is developed which finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bound for the total cost.","abstract_html":"The main focus of this dissertation is on classical combinatorial optimization problems in two important areas: scheduling and network design. In the area of scheduling, the main interest is in problems in the master-slave model. In this model, each machine is either a master machine or a slave machine. Each job is associated with a preprocessing task, a slave task and a postprocessing task that must be executed in this order. Each slave task has a dedicated slave machine. All the preprocessing and postprocessing tasks share a single master machine or the same set of master machines. A job may also have an arbitrary release time before which the preprocessing task is not available to be processed. The main objective in this dissertation is to minimize the total completion time or the makespan. Both the complexity and algorithmic issues of these problems are considered. It is shown that the problem of minimizing the total completion time is strongly NP-hard even under severe constraints. Various efficient algorithms are designed to minimize the total completion time under various scenarios. In the area of network design, the survivable network design problems are studied first. The input for this problem is an undirected graph G = (V, E), a non-negative cost for each edge, and a nonnegative connectivity requirement r_{uv} for every (unordered) pair of vertices u, v. The goal is to find a minimum-cost subgraph in which each pair of vertices u,v is joined by at least r_{uv} edge (vertex)-disjoint paths. A Polynomial Time Approximation Scheme (PTAS) is designed for the problem when the graph is Euclidean and the connectivity requirement of any point is at most 2. PTASs or Quasi-PTASs are also designed for 2-edge-connectivity problem and biconnectivity problem and their variations in unweighted or weighted planar graphs. Next, the problem of constructing geometric fault-tolerant spanners with low cost and bounded maximum degree is considered. The first result shows that there is a greedy algorithm which constructs fault-tolerant spanners having asymptotically optimal bounds for both the maximum degree and the total cost at the same time. Then an efficient algorithm is developed which finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bound for the total cost.","abstract_has_math":false,"creators":["Zhao, Hairong"],"institution":null,"degree_name":"Doctor of Philosophy in Computing Sciences - (Ph.D.)","degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Joseph Y-T. Leung","Artur Czumaj","Teunis J. Ott"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2005,"date_issued":"2005-05-31T07:00:00Z","date_published":"2005-05-31T07:00:00Z","updated_at":"2026-07-24T03:23:04Z","subjects":["Scheduling","Master-slave model","Approximation algorithms","Survivable network design","Planar graphs","Fault tolerant spanner","Computer Sciences"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.njit.edu/dissertations/722","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Joseph Y-T. Leung","Artur Czumaj","Teunis J. Ott"]},{"key":"dc:creator","label":"Author","values":["Zhao, Hairong"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:type","label":"Dc Type","values":["Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy in Computing Sciences - (Ph.D.)"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Scheduling","Master-slave model","Approximation algorithms","Survivable network design","Planar graphs","Fault tolerant spanner","Computer Sciences"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.njit.edu/dissertations/722"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["The main focus of this dissertation is on classical combinatorial optimization problems in two important areas: scheduling and network design. In the area of scheduling, the main interest is in problems in the master-slave model. In this model, each machine is either a master machine or a slave machine. Each job is associated with a preprocessing task, a slave task and a postprocessing task that must be executed in this order. Each slave task has a dedicated slave machine. All the preprocessing and postprocessing tasks share a single master machine or the same set of master machines. A job may also have an arbitrary release time before which the preprocessing task is not available to be processed. The main objective in this dissertation is to minimize the total completion time or the makespan. Both the complexity and algorithmic issues of these problems are considered. It is shown that the problem of minimizing the total completion time is strongly NP-hard even under severe constraints. Various efficient algorithms are designed to minimize the total completion time under various scenarios. In the area of network design, the survivable network design problems are studied first. The input for this problem is an undirected graph G = (V, E), a non-negative cost for each edge, and a nonnegative connectivity requirement r_{uv} for every (unordered) pair of vertices u, v. The goal is to find a minimum-cost subgraph in which each pair of vertices u,v is joined by at least r_{uv} edge (vertex)-disjoint paths. A Polynomial Time Approximation Scheme (PTAS) is designed for the problem when the graph is Euclidean and the connectivity requirement of any point is at most 2. PTASs or Quasi-PTASs are also designed for 2-edge-connectivity problem and biconnectivity problem and their variations in unweighted or weighted planar graphs. Next, the problem of constructing geometric fault-tolerant spanners with low cost and bounded maximum degree is considered. The first result shows that there is a greedy algorithm which constructs fault-tolerant spanners having asymptotically optimal bounds for both the maximum degree and the total cost at the same time. Then an efficient algorithm is developed which finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bound for the total cost."]},{"key":"dc:title","label":"Title","values":["Algorithms and complexity analyses for some combinational optimization problems"]}]}],"canonical_facts":{"dc:contributor":["Joseph Y-T. Leung","Artur Czumaj","Teunis J. Ott"],"dc:creator":["Zhao, Hairong"],"dc:description.abstract":["The main focus of this dissertation is on classical combinatorial optimization problems in two important areas: scheduling and network design. In the area of scheduling, the main interest is in problems in the master-slave model. In this model, each machine is either a master machine or a slave machine. Each job is associated with a preprocessing task, a slave task and a postprocessing task that must be executed in this order. Each slave task has a dedicated slave machine. All the preprocessing and postprocessing tasks share a single master machine or the same set of master machines. A job may also have an arbitrary release time before which the preprocessing task is not available to be processed. The main objective in this dissertation is to minimize the total completion time or the makespan. Both the complexity and algorithmic issues of these problems are considered. It is shown that the problem of minimizing the total completion time is strongly NP-hard even under severe constraints. Various efficient algorithms are designed to minimize the total completion time under various scenarios. In the area of network design, the survivable network design problems are studied first. The input for this problem is an undirected graph G = (V, E), a non-negative cost for each edge, and a nonnegative connectivity requirement r_{uv} for every (unordered) pair of vertices u, v. The goal is to find a minimum-cost subgraph in which each pair of vertices u,v is joined by at least r_{uv} edge (vertex)-disjoint paths. A Polynomial Time Approximation Scheme (PTAS) is designed for the problem when the graph is Euclidean and the connectivity requirement of any point is at most 2. PTASs or Quasi-PTASs are also designed for 2-edge-connectivity problem and biconnectivity problem and their variations in unweighted or weighted planar graphs. Next, the problem of constructing geometric fault-tolerant spanners with low cost and bounded maximum degree is considered. The first result shows that there is a greedy algorithm which constructs fault-tolerant spanners having asymptotically optimal bounds for both the maximum degree and the total cost at the same time. Then an efficient algorithm is developed which finds fault-tolerant spanners with asymptotically optimal bound for the maximum degree and almost optimal bound for the total cost."],"dc:identifier":["https://digitalcommons.njit.edu/dissertations/722"],"dc:subject":["Scheduling","Master-slave model","Approximation algorithms","Survivable network design","Planar graphs","Fault tolerant spanner","Computer Sciences"],"dc:title":["Algorithms and complexity analyses for some combinational optimization problems"],"dc:type":["Dissertation"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_name":["Doctor of Philosophy in Computing Sciences - (Ph.D.)"]},"updated_at":"2026-07-24T03:23:04Z"}