Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of New Brunswick

$38,000.00

Approximation algorithm design and analysis for submodular optimization

EF 2024-25

Résumé
This research proposal is not qualified as indigenous research according to the NSERC's definition. The objective of the research program is to develop general methodological and algorithmic principles in approximation algorithm design and analysis in non-convex and non-concave optimization problems, in particular combinatorial optimization and submodular problems that are expected to have a significant impact on such applications as machine learning/artificial intelligence, supply chain management, production/operations management, location and routing, scheduling, telecommunication, transportation, health, bioinformatics, and others. Approximation algorithm with provable performance is a valuable option for solving large-scale NP-hard combinatorial optimization problems. However, the current state consists of usually ad hoc results, which are highly problem specific. This proposed project believes the entire optimization field is at a stage where general algorithmic principles can be distilled to unify and simplify existing approximation algorithms; provide a guideline to design and analyze new approximation algorithms; and offer new perspectives to potentially improve existing approximation algorithms. We will use the rapid developing subfield of submodular optimization as running examples to test new ideas along this line. Submodular optimization itself, historically an active field in combinational optimization, nowadays find wide applications in numerous fields, including machine learning and artificial intelligence, economy, risk management, decision science, and optimal transport among others. Therefore, the developed principles will find huge application in real-world problems via the lens of submodular optimization. We wish to study some specific problems related to approximation algorithm and submodular optimization. These specific problems are carefully chosen such that they are representative, basic, fundamental, and possess great potential in advancing the knowledge of the corresponding subjective areas in particular and spawning new methodologies at large. Moreover, the problems to be investigated are not only of theoretical importance, but also of great practical significance. We have selected problems that span the subjective areas of submodular optimization, facility location theory, network flow, supply chain management, finance optimization, and scheduling. The proposed research builds upon our previous work and our past success in attacking some of the aforementioned problems is an indicator that we have the necessary mathematical groundings and proper tools to work on them. The results of this investigation will not only lead to efficient algorithms and enhanced understanding for the particular problems under consideration but will also build foundations to innovate potential new mechanisms that are of great practical significance and importance to the management of Canadian and international business and economics.
Programme
Discovery Grants Program - Individual
Emplacement
New Brunswick, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2024-03840
Name nom
Du, Donglei
Department département
Business Administration, Faculty of - Business Administration, Faculty of
Organization id
75
Institution établissement
University of New Brunswick
Province en
New Brunswick
Province fr
Nouveau-Brunswick
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
38000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1509
Committee name en
Civil, Industrial and Systems Engineering
Committee name fr
Génie civil, industriel et des systèmes
Area of application code
1206
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Engineering
Area of application fr
Génie
Research subject code
1601
Research subject group en
Industrial engineering
Research subject group fr
Génie industriel
Research subject en
Operations research and management science
Research subject fr
Recherche opérationnelle et science de la gestion
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Approximation algorithm design and analysis for submodular optimization
Keywords
submodular; optimization; approximation algorithm; lattice; infinite domain; algorithm design framework; lyapunov and potential function; extensions and rounding
Application summary
This research proposal is not qualified as indigenous research according to the NSERC's definition. The objective of the research program is to develop general methodological and algorithmic principles in approximation algorithm design and analysis in non-convex and non-concave optimization problems, in particular combinatorial optimization and submodular problems that are expected to have a significant impact on such applications as machine learning/artificial intelligence, supply chain management, production/operations management, location and routing, scheduling, telecommunication, transportation, health, bioinformatics, and others. Approximation algorithm with provable performance is a valuable option for solving large-scale NP-hard combinatorial optimization problems. However, the current state consists of usually ad hoc results, which are highly problem specific. This proposed project believes the entire optimization field is at a stage where general algorithmic principles can be distilled to unify and simplify existing approximation algorithms; provide a guideline to design and analyze new approximation algorithms; and offer new perspectives to potentially improve existing approximation algorithms. We will use the rapid developing subfield of submodular optimization as running examples to test new ideas along this line. Submodular optimization itself, historically an active field in combinational optimization, nowadays find wide applications in numerous fields, including machine learning and artificial intelligence, economy, risk management, decision science, and optimal transport among others. Therefore, the developed principles will find huge application in real-world problems via the lens of submodular optimization. We wish to study some specific problems related to approximation algorithm and submodular optimization. These specific problems are carefully chosen such that they are representative, basic, fundamental, and possess great potential in advancing the knowledge of the corresponding subjective areas in particular and spawning new methodologies at large. Moreover, the problems to be investigated are not only of theoretical importance, but also of great practical significance. We have selected problems that span the subjective areas of submodular optimization, facility location theory, network flow, supply chain management, finance optimization, and scheduling. The proposed research builds upon our previous work and our past success in attacking some of the aforementioned problems is an indicator that we have the necessary mathematical groundings and proper tools to work on them. The results of this investigation will not only lead to efficient algorithms and enhanced understanding for the particular problems under consideration but will also build foundations to innovate potential new mechanisms that are of great practical significance and importance to the management of Canadian and international business and economics.