subject:( Exact Exponential Algorithm)

Kyoto University / 京都大学

1. Norhazwani, Md Yunos. Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs : 次数の制限されたグラフにおけるトラベリングセールスマン問題に対する多項式領域厳密アルゴリズム.

Degree: 博士(情報学), 2017, Kyoto University / 京都大学

URL: http://hdl.handle.net/2433/225741 ; http://dx.doi.org/10.14989/doctor.k20516

新制・課程博士

甲第20516号

情博第644号

Subjects/Keywords: Traveling Salesman Problem; Exact Exponential Algorithm; Branch-and-reduce; Measure-and-conquer

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Norhazwani, M. Y. (2017). Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs : 次数の制限されたグラフにおけるトラベリングセールスマン問題に対する多項式領域厳密アルゴリズム. (Thesis). Kyoto University / 京都大学. Retrieved from http://hdl.handle.net/2433/225741 ; http://dx.doi.org/10.14989/doctor.k20516

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Norhazwani, Md Yunos. “Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs : 次数の制限されたグラフにおけるトラベリングセールスマン問題に対する多項式領域厳密アルゴリズム.” 2017. Thesis, Kyoto University / 京都大学. Accessed January 22, 2021. http://hdl.handle.net/2433/225741 ; http://dx.doi.org/10.14989/doctor.k20516.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Norhazwani, Md Yunos. “Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs : 次数の制限されたグラフにおけるトラベリングセールスマン問題に対する多項式領域厳密アルゴリズム.” 2017. Web. 22 Jan 2021.

Vancouver:

Norhazwani MY. Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs : 次数の制限されたグラフにおけるトラベリングセールスマン問題に対する多項式領域厳密アルゴリズム. [Internet] [Thesis]. Kyoto University / 京都大学; 2017. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/2433/225741 ; http://dx.doi.org/10.14989/doctor.k20516.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Norhazwani MY. Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs : 次数の制限されたグラフにおけるトラベリングセールスマン問題に対する多項式領域厳密アルゴリズム. [Thesis]. Kyoto University / 京都大学; 2017. Available from: http://hdl.handle.net/2433/225741 ; http://dx.doi.org/10.14989/doctor.k20516

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Kyoto University

2. Norhazwani, Md Yunos. Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs .

Degree: 2017, Kyoto University

URL: http://hdl.handle.net/2433/225741

Subjects/Keywords: Traveling Salesman Problem; Exact Exponential Algorithm; Branch-and-reduce; Measure-and-conquer

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Norhazwani, M. Y. (2017). Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs . (Thesis). Kyoto University. Retrieved from http://hdl.handle.net/2433/225741

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Norhazwani, Md Yunos. “Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs .” 2017. Thesis, Kyoto University. Accessed January 22, 2021. http://hdl.handle.net/2433/225741.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Norhazwani, Md Yunos. “Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs .” 2017. Web. 22 Jan 2021.

Vancouver:

Norhazwani MY. Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs . [Internet] [Thesis]. Kyoto University; 2017. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/2433/225741.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Norhazwani MY. Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs . [Thesis]. Kyoto University; 2017. Available from: http://hdl.handle.net/2433/225741

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

3. Vieira Milreu, Paulo. Enumerating functional substructures of genome-scale metabolic networks : stories, precursors and organisations : Énumération de sous-structures fonctionnelle dans des réseaux métaboliques complets : Histoires métaboliques, précurseurs et organisations chimiques.

Degree: Docteur es, Bioinformatique, 2012, Université Claude Bernard – Lyon I

URL: http://www.theses.fr/2012LYO10267

►

Dans cette thèse, nous avons présenté trois méthodes différentes pour l’énumération de sousréseauxparticuliers d’un réseau métabolique: les histoires métaboliques, les ensembles minimaux deprécurseurs et les… (more)

▼

Dans cette thèse, nous avons présenté trois méthodes différentes pour l’énumération de sousréseauxparticuliers d’un réseau métabolique: les histoires métaboliques, les ensembles minimaux deprécurseurs et les organisations chimiques. Pour chacune de ces trois méthodes, nous avons présentédes résultats théoriques, et pour les deux premières, nous avons en outre fourni une illustration surcomment les appliquer afin d’étudier le comportement métabolique des organismes vivants. Les histoiresmétaboliques sont définies comme des graphes acycliques dirigés maximaux dont les ensemblesde sources et de cibles sont limités à un sous-ensemble des noeuds. La motivation initiale de cette définitionétait d’analyser des données expérimentales de métabolomique, mais la méthode a égalementété explorée dans un contexte différent. Les ensembles de précurseurs métaboliques sont des ensemblesminimaux de nutriments qui permettent de produire des métabolites d’intérêt. Nous présentons troisméthodes différentes pour l’énumération de tels ensembles minimaux de précurseurs, et nous illustronsleur application dans une étude des échanges métaboliques dans un système symbiotique. Les organisationschimiques sont des ensembles de métabolites qui à la fois sont fermés et s’auto-maintiennent,ce qui reflète des caractéristiques de stabilité dans le sens où aucun nouveau métabolite ne peut êtreproduit et qu’aucun des métabolites déjà présents dans le système ne peut disparaître.

In this thesis, we presented three different methods for enumerating special subnetworks containedin a metabolic network: metabolic stories, minimal precursor sets and chemical organisations. Foreach of the three methods, we gave theoretical results, and for the two first ones, we further providedan illustration on how to apply them in order to study the metabolic behaviour of living organisms.Metabolic stories are defined as maximal directed acyclic graphs whose sets of sources and targets arerestricted to a subset of the nodes. The initial motivation of this definition was to analyse metabolomicsexperimental data, but the method was also explored in a different context. Metabolic precursor setsare minimal sets of nutrients that are able to produce metabolites of interest. We present threedifferent methods for enumerating minimal precursor sets and we illustrate the application in a studyof the metabolic exchanges in a symbiotic system. Chemical organisations are sets of metabolites thatare simultaneously closed and self-maintaining, which captures some stability feature in the

Advisors/Committee Members: Sagot, Marie-France (thesis director), Gautier, Christian (thesis director), Lacroix, Vincent (thesis director).

Subjects/Keywords: Algorithme; Complexité; Graphes; Exact exponentiel; Randomisation; Biologie computationelle; Graphe acyclique dirigé maximal; Histoire métabolique; Réseau métabolique; Algorithm; Complexity; Graphs; Exact exponential; Randomisation; Computational biology; Maximal directed acyclic graph; Metabolic story; Metabolic network; 570.15

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Vieira Milreu, P. (2012). Enumerating functional substructures of genome-scale metabolic networks : stories, precursors and organisations : Énumération de sous-structures fonctionnelle dans des réseaux métaboliques complets : Histoires métaboliques, précurseurs et organisations chimiques. (Doctoral Dissertation). Université Claude Bernard – Lyon I. Retrieved from http://www.theses.fr/2012LYO10267

Chicago Manual of Style (16^th Edition):

Vieira Milreu, Paulo. “Enumerating functional substructures of genome-scale metabolic networks : stories, precursors and organisations : Énumération de sous-structures fonctionnelle dans des réseaux métaboliques complets : Histoires métaboliques, précurseurs et organisations chimiques.” 2012. Doctoral Dissertation, Université Claude Bernard – Lyon I. Accessed January 22, 2021. http://www.theses.fr/2012LYO10267.

MLA Handbook (7^th Edition):

Vieira Milreu, Paulo. “Enumerating functional substructures of genome-scale metabolic networks : stories, precursors and organisations : Énumération de sous-structures fonctionnelle dans des réseaux métaboliques complets : Histoires métaboliques, précurseurs et organisations chimiques.” 2012. Web. 22 Jan 2021.

Vancouver:

Vieira Milreu P. Enumerating functional substructures of genome-scale metabolic networks : stories, precursors and organisations : Énumération de sous-structures fonctionnelle dans des réseaux métaboliques complets : Histoires métaboliques, précurseurs et organisations chimiques. [Internet] [Doctoral dissertation]. Université Claude Bernard – Lyon I; 2012. [cited 2021 Jan 22]. Available from: http://www.theses.fr/2012LYO10267.

Council of Science Editors:

Vieira Milreu P. Enumerating functional substructures of genome-scale metabolic networks : stories, precursors and organisations : Énumération de sous-structures fonctionnelle dans des réseaux métaboliques complets : Histoires métaboliques, précurseurs et organisations chimiques. [Doctoral Dissertation]. Université Claude Bernard – Lyon I; 2012. Available from: http://www.theses.fr/2012LYO10267

University of New South Wales

4. Wang, Xubo. Efficiently Computing Exact Set Similarity Joins.

Degree: Computer Science & Engineering, 2018, University of New South Wales

URL: http://handle.unsw.edu.au/1959.4/60433 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:52219/SOURCE02?view=true

► Set similarity join, which finds all the similar set pairs from two collections of sets, is a fundamental problem with a wide range of applications… (more)

▼ Set similarity join, which finds all the similar set pairs from two collections of sets, is a fundamental problem with a wide range of applications including data cleaning, information extraction, machine learning and so on. In this thesis, we study three important problems regarding set similarity join.Firstly, we develop algorithms for static exact set similarity join problem. The existing solutions for exact set similarity join follow a filtering-verification framework, which generates a list of candidate pairs through scanning indexes in the filtering phase, and reports those similar pairs in the verification phase. Though much research has been conducted on this problem, set relations have not been well studied on improving the algorithm efficiency through computational cost sharing. Therefore, we explore the set relations in different levels to reduce the overall computational costs. It has been shown that most of the computational time is spent on the filtering phase. Thus we explore index-level set relations to reduce the filtering cost while keeping the same filtering power. We achieve this by grouping related sets into blocks in the index and skipping useless index probes in joins. Also, we explore answer-level set relations to further improve the algorithm based on the intuition that if two sets are similar, their answers may have a large overlap. We conduct extensive performance studies using 21 real datasets with various data properties from a wide range of domains. The experimental results demonstrate that our algorithm outperforms all the existing algorithms across all datasets.Secondly, we study the dynamic set similarity join problem considering that the data are usually updated dynamically in real applications. No previous study has been found on this problem. We design efficient algorithms to incrementally update the join result when any element in the sets is updated. Computational cost is analyzed on proposed algorithms. Comprehensive experiments on real-life datasets validate the effectiveness and efficiency of our algorithms.Finally, we investigate parallel set similarity join on multicore CPUs to support set similarity join on large datasets. Up to now, no research has been found on solving set similarity join problem in terms of Jaccard/Cosine similarity on a single machine with multicore CPUs. We propose record-level and element-level parallel algorithms and conduct experiments on large real-life datasets to show effectiveness and scalability of our algorithms. Advisors/Committee Members: Zhang, Wenjie, Computer Science & Engineering, Faculty of Engineering, UNSW, Lin, Xuemin, Computer Science & Engineering, Faculty of Engineering, UNSW, Qin, Lu, Computer Science & Engineering, Faculty of Engineering, UNSW.

Subjects/Keywords: Parallel Algorithm; Exact Set Similarity Join; Incremental Algorithm

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Wang, X. (2018). Efficiently Computing Exact Set Similarity Joins. (Doctoral Dissertation). University of New South Wales. Retrieved from http://handle.unsw.edu.au/1959.4/60433 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:52219/SOURCE02?view=true

Chicago Manual of Style (16^th Edition):

Wang, Xubo. “Efficiently Computing Exact Set Similarity Joins.” 2018. Doctoral Dissertation, University of New South Wales. Accessed January 22, 2021. http://handle.unsw.edu.au/1959.4/60433 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:52219/SOURCE02?view=true.

MLA Handbook (7^th Edition):

Wang, Xubo. “Efficiently Computing Exact Set Similarity Joins.” 2018. Web. 22 Jan 2021.

Vancouver:

Wang X. Efficiently Computing Exact Set Similarity Joins. [Internet] [Doctoral dissertation]. University of New South Wales; 2018. [cited 2021 Jan 22]. Available from: http://handle.unsw.edu.au/1959.4/60433 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:52219/SOURCE02?view=true.

Council of Science Editors:

Wang X. Efficiently Computing Exact Set Similarity Joins. [Doctoral Dissertation]. University of New South Wales; 2018. Available from: http://handle.unsw.edu.au/1959.4/60433 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:52219/SOURCE02?view=true

George Mason University

5. Nies, Brandi. A Comparative Test of Traveling Salesman Solutions from GIS Software Packages .

Degree: 2015, George Mason University

URL: http://hdl.handle.net/1920/9720

► The Traveling Salesman Problem (TSP) has long been studied and remains a challenge in the realm of combinatorial optimization across many disciplines. This research investigates… (more)

▼ The Traveling Salesman Problem (TSP) has long been studied and remains a challenge in the realm of combinatorial optimization across many disciplines. This research investigates the extent to which heuristic solutions for symmetric TSPs generated within geographic information systems (GIS) applications are sub-optimal, compared to exact solution procedures. The TSP is addressed in this research through multiple real-world street networks and a range of problem instances, for which a path must be generated that visits each city only once, and returns to the original point of departure, while minimizing the distance traveled. Two GIS applications were used to generate heuristic solutions for the symmetric TSP for each network dataset. These results were compared against the optimal solutions generated from an exact solution procedure for the same networks. The cumulative cost of each TSP route for all network problem instances was examined to determine the performance and level of sub-optimality where applicable. This research concludes that the heuristic solutions generated sub-optimal results averaging a combined performance measure of 17.36% above optimal, however the software that employs the tabu search (TS) heuristic significantly outperformed the software that used the genetic algorithm (GA) by consistently producing solutions nearer to the known optimum as generated by the exact solution procedure. Given the wide range in the extent of sub-optimal results from the heuristic-based GIS applications, this research suggests that careful consideration should be made prior to the use of these implementations for spatial analysis. Additionally, GIS packages could benefit from integrating additional, or more efficient heuristic or exact solution procedures within the application, and allowing the user more control of the search parameters to accommodate various network optimization problems. Keywords: network analysis; traveling salesman; TSP, route optimization; GIS; heuristic; genetic algorithm; tabu search Advisors/Committee Members: Curtin, Kevin M (advisor).

Subjects/Keywords: network analysis; traveling salesman; route optimization; GIS; heuristic; exact algorithm

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Nies, B. (2015). A Comparative Test of Traveling Salesman Solutions from GIS Software Packages . (Thesis). George Mason University. Retrieved from http://hdl.handle.net/1920/9720

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Nies, Brandi. “A Comparative Test of Traveling Salesman Solutions from GIS Software Packages .” 2015. Thesis, George Mason University. Accessed January 22, 2021. http://hdl.handle.net/1920/9720.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Nies, Brandi. “A Comparative Test of Traveling Salesman Solutions from GIS Software Packages .” 2015. Web. 22 Jan 2021.

Vancouver:

Nies B. A Comparative Test of Traveling Salesman Solutions from GIS Software Packages . [Internet] [Thesis]. George Mason University; 2015. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/1920/9720.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Nies B. A Comparative Test of Traveling Salesman Solutions from GIS Software Packages . [Thesis]. George Mason University; 2015. Available from: http://hdl.handle.net/1920/9720

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Minnesota

6. Wu, Zeyang. Fast exact algorithms for optimization problems in resource allocation and switched linear systems.

Degree: PhD, Industrial Engineering, 2019, University of Minnesota

URL: http://hdl.handle.net/11299/206239

► Discrete optimization is a branch of mathematical optimization where some of the decision variables are restricted to real values in a discrete set. The use… (more)

Subjects/Keywords: Exact algorithm; Mixed-integer program; Resource allocation; Switched linear systems

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Wu, Z. (2019). Fast exact algorithms for optimization problems in resource allocation and switched linear systems. (Doctoral Dissertation). University of Minnesota. Retrieved from http://hdl.handle.net/11299/206239

Chicago Manual of Style (16^th Edition):

Wu, Zeyang. “Fast exact algorithms for optimization problems in resource allocation and switched linear systems.” 2019. Doctoral Dissertation, University of Minnesota. Accessed January 22, 2021. http://hdl.handle.net/11299/206239.

MLA Handbook (7^th Edition):

Wu, Zeyang. “Fast exact algorithms for optimization problems in resource allocation and switched linear systems.” 2019. Web. 22 Jan 2021.

Vancouver:

Wu Z. Fast exact algorithms for optimization problems in resource allocation and switched linear systems. [Internet] [Doctoral dissertation]. University of Minnesota; 2019. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/11299/206239.

Council of Science Editors:

Wu Z. Fast exact algorithms for optimization problems in resource allocation and switched linear systems. [Doctoral Dissertation]. University of Minnesota; 2019. Available from: http://hdl.handle.net/11299/206239

7. Tejaswi, Nunna. Performance Analysis on Hybrid and ExactMethods for Solving Clustered VRP : A Comparative Study on VRP Algorithms.

Degree: 2017, , Department of Computer Science and Engineering

URL: http://urn.kb.se/resolve?urn=urn:nbn:se:bth-14112

► Context: The Vehicle Routing Problem is an NP-hard problem with a combination of varieties oftopics like logistics, optimization research and data mining. There is… (more)

▼ Context: The Vehicle Routing Problem is an NP-hard problem with a combination of varieties oftopics like logistics, optimization research and data mining. There is a vast need of vehicle routingsolutions in day to day like with different constraints. According to the requirements, this problem hasbeen a field of interest to a lot of researchers who incorporate scientific methods to combine andinnovate new solutions to optimize the routing. Being an np-hard problem, it is almost impossible tocompute the solutions to optimality but years of research on this area has paid off quite significantlyand the solutions are optimized little by little and better than before. Some applications may or maynot find slight difference in the performance as a considerable affect but some applications orscenarios heavily depend on the performance of the solution where it is very vital that the solution isoptimized to the fullest. As a data mining technique clustering has been used very prominently in caseof portioning scenarios and similarly it has also began to surface in implementing VRP solutions.Although it has recently emerged into the Vehicle Routing era and shown some significant results, ithas not yet come into an open state or awareness. The awareness regarding clustering matters in ahuge extent to be considered by most of the recent researchers who formulate new algorithms to solveVRP and help them further optimize their solution. Objectives: In this study the significance of clustering has been considered to find out how the usageof clustering techniques can alter the performance of VRP based solutions favorably. Then to test theresults of two recently proposed cluster based algorithms, a comparison has been made to other typesof algorithms which prove how the algorithms stand with various methods. Methods: A literature review is performed using various articles that have been gathered from GoogleScholar and then an empirical experiment was conducted on the results available in the papers. Thisexperiment was done by performing a comparative analysis. Results: For the literature review the results were gathered from all the articles based on theirresearch, experience, use of clustering and how their result was improved by using clustering methodsin their formulations. Considering the experiment, the results of both the algorithm were comparedwith the results of five other papers who aim to solve the VRP using exactly the same instances thatwere used in the two algorithms in order to compare valid results on the same variables. Then theresults were analyzed for the purpose of comparison and conclusions were drawn accordingly. Conclusions: From the research performed in this paper we can conclude the vast significance ofclustering techniques that were drawn based on practical test results of various authors. From theexperiment performed it is clear that the Hybrid algorithm has a much higher performance than anyother algorithm it has been compared to. This algorithm has also been proven to enhance…

Subjects/Keywords: Vehicle routing problem; logistics; clustering; genetic algorithm; exact algorithm; Computer Sciences; Datavetenskap (datalogi)

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Tejaswi, N. (2017). Performance Analysis on Hybrid and ExactMethods for Solving Clustered VRP : A Comparative Study on VRP Algorithms. (Thesis). , Department of Computer Science and Engineering. Retrieved from http://urn.kb.se/resolve?urn=urn:nbn:se:bth-14112

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Tejaswi, Nunna. “Performance Analysis on Hybrid and ExactMethods for Solving Clustered VRP : A Comparative Study on VRP Algorithms.” 2017. Thesis, , Department of Computer Science and Engineering. Accessed January 22, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:bth-14112.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Tejaswi, Nunna. “Performance Analysis on Hybrid and ExactMethods for Solving Clustered VRP : A Comparative Study on VRP Algorithms.” 2017. Web. 22 Jan 2021.

Vancouver:

Tejaswi N. Performance Analysis on Hybrid and ExactMethods for Solving Clustered VRP : A Comparative Study on VRP Algorithms. [Internet] [Thesis]. , Department of Computer Science and Engineering; 2017. [cited 2021 Jan 22]. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:bth-14112.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Tejaswi N. Performance Analysis on Hybrid and ExactMethods for Solving Clustered VRP : A Comparative Study on VRP Algorithms. [Thesis]. , Department of Computer Science and Engineering; 2017. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:bth-14112

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Delft University of Technology

8. van der Sar, Erica (author). Multi-attribute vehicle routing problems: Exploring the limits of exact methods in practice.

Degree: 2018, Delft University of Technology

URL: http://resolver.tudelft.nl/uuid:ec15c141-289b-4a8d-ae76-652bae893ab4

►

The companies CQM and EVO-it work together to help many different companies with solving their vehicle routing problems. EVO-it provides the interface of the software… (more)

▼

The companies CQM and EVO-it work together to help many different companies with solving their vehicle routing problems. EVO-it provides the interface of the software that the companies can use for route planning and CQM provides the technology that is used to solve the route planning problems, which concerns a lot of mathematical programming. The difficulty of solving these problems is that real-life problems usually deal withmulti-attribute vehicle routing problems, which are problemswith multiple characteristics, such as time windows and vehicle restrictions. These characteristics influence the solving process and the quality of the solution of the method used to solve the problem. Since these attributes can vary a lot per company, it is a difficult task for CQM to provide the best solving method for all problem types. Even though CQM has provided a very complex method that can handle many problems, it is unclear how far from the optimum solution the provided solutions are. The goal of this project was to investigate the improvement possibilities of the current method used by CQM. In this thesis many different solving methods for the vehicle routing problem are evaluated and their qualities are discussed. Furthermore, information from the companies that are using the software of EVO-it is collected. With this information an overview of the problem types occurring at these companies is provided. Such an overview had not been made before and will be very useful for CQMand EVO-it to make more problem type specific improvements to the solving method. Furthermore, this thesis describes two exact methods for solving vehicle routing problems similar to the real-life problems occurring at the clients of EVO-it. One of these methods uses a three-index flow formulation and the other one uses a set partitioning formulation and is based on the method described by Baldacci andMingozzi. It is shown that this latter method can be used to solve instances with up to 40 orders. In addition, both methods can deal with several complicated attributes, including capacity constraints, distance constraints, different type of costs and heterogeneous vehicles. Moreover, it can even deal with instances where not all orders can or need to be scheduled. In such a case, the orders that are not scheduled will get a penalty. To the best of my knowledge, no previous exact method was able to deal with such instances.

Optimization

Applied Mathematics

Advisors/Committee Members: van Iersel, Leo (mentor), Looije, Daphne (mentor), Aardal, Karen (graduation committee), Nane, Tina (graduation committee), Delft University of Technology (degree granting institution).

Subjects/Keywords: Vehicle Routing; Exact algorithm; Exact Method; Set Partitioning; Two-index flow; Three-index flow; heterogeneous vehicles

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

van der Sar, E. (. (2018). Multi-attribute vehicle routing problems: Exploring the limits of exact methods in practice. (Masters Thesis). Delft University of Technology. Retrieved from http://resolver.tudelft.nl/uuid:ec15c141-289b-4a8d-ae76-652bae893ab4

Chicago Manual of Style (16^th Edition):

van der Sar, Erica (author). “Multi-attribute vehicle routing problems: Exploring the limits of exact methods in practice.” 2018. Masters Thesis, Delft University of Technology. Accessed January 22, 2021. http://resolver.tudelft.nl/uuid:ec15c141-289b-4a8d-ae76-652bae893ab4.

MLA Handbook (7^th Edition):

van der Sar, Erica (author). “Multi-attribute vehicle routing problems: Exploring the limits of exact methods in practice.” 2018. Web. 22 Jan 2021.

Vancouver:

van der Sar E(. Multi-attribute vehicle routing problems: Exploring the limits of exact methods in practice. [Internet] [Masters thesis]. Delft University of Technology; 2018. [cited 2021 Jan 22]. Available from: http://resolver.tudelft.nl/uuid:ec15c141-289b-4a8d-ae76-652bae893ab4.

Council of Science Editors:

van der Sar E(. Multi-attribute vehicle routing problems: Exploring the limits of exact methods in practice. [Masters Thesis]. Delft University of Technology; 2018. Available from: http://resolver.tudelft.nl/uuid:ec15c141-289b-4a8d-ae76-652bae893ab4

Université de Lorraine

9. Sayadi, Mohamed Yosri. Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive : Design and analysis of exact exponential algorithms : input-sensitive enumeration.

Degree: Docteur es, Informatique, 2019, Université de Lorraine

URL: http://www.theses.fr/2019LORR0316

►

Moon et Moser ont prouvé que le nombre maximum des ensembles stables maximaux dans un graphe de n sommets est au plus 3^n/3. Cette borne,… (more)

▼

Moon et Moser ont prouvé que le nombre maximum des ensembles stables maximaux dans un graphe de n sommets est au plus 3^n/3. Cette borne, appelée borne supérieure, est stricte vu l’existence d’une famille des graphes avec un tel nombre appelée borne inférieure. Au contraire de l’énumération des ensembles stables maximaux, avoir deux bornes qui se qui se coïncident n’est pas évident du tout. Et c’est assez courant dans l’énumération « input-sensitive » d’avoir un grand écart. Ce problème concerne même les ensembles les plus classiques comme les ensembles dominants minimaux où le meilleur algorithme connu pour énumérer ces ensembles est en O(1.7159ⁿ) et la meilleure borne inférieure connue est seulement 1.5704ⁿ. Durant cette thèse, on a proposé un algorithme « Mesurer pour Conquérir » pour énumérer tous les ensembles dominants minimaux dans les graphes cordaux en O(1.5048ⁿ). On a étudié aussi l’énumération des ensembles dominants connexes minimaux et les ensembles irredondants maximaux qui sont très proches des ensembles dominants minimaux. On a proposé un algorithme d’énumération des ensembles dominants connexes minimaux dans les graphes bipartis convexes en O(1.7254ⁿ). On a conçu aussi des algorithmes d’énumération des ensembles irredondants maximaux dans les graphes cordaux, les graphes d’intervalles et les forêts en O(1.7549ⁿ), O(1.6957ⁿ ) et O(1.6181ⁿ) respectivement au lieu de l’algorithme trivial en O*(2ⁿ). On a proposé aussi comme une borne inférieure une famille de forêts avec Omega(1.5292ⁿ) ensembles irredondants maximaux. Dans le cas des cographes, l'écart entre les deux bornes est réduit à néant en montrant que le nombre maximum de ces ensembles est Theta(15^n/6). Afin de varier, on a étudié un nouvel ensemble défini récemment : L’ensemble tropical connexe minimal. On a proposé une borne inférieure de 1.4961ⁿ, mais sans réussir à améliorer la borne supérieure de 2ⁿ. On a proposé des algorithmes d’énumération des ensembles tropicaux connexes minimaux dans les graphes cobipartis, les graphes d’intervalles et les graphes blocs en O*(3^n/3), O(1.8613ⁿ) et O*(3^n/3) respectivement. On a établi une borne inférieure de 1.4766ⁿ pour les graphes scindés et de 3^n/3 pour les graphes cobipartis, les graphes d’intervalles et les graphes blocs. Finalement, comme perspective et pour attirer l’attention de la communauté sur l’énumération des ensembles dominants totaux minimaux, on a montré que le nombre maximum de ces ensembles est Ω(1.5848ⁿ).

Moon and Moser proved that the maximum number of maximal independent sets in a graph of n vertices is at most 3^n/3. This maximum number, called upper bound, is tight given the existence of a family of graphs with such a number called lower bound. Unlike the enumeration of maximal independent sets, having a tight bounds is not obvious at all. And it’s quite common in the “input-sensitive” enumeration to have a big gap. This problem concerns even the most studied sets as minimal dominating sets where the best known algorithm to enumerate those sets runs…

Advisors/Committee Members: Colson, Loïc (thesis director).

Subjects/Keywords: Algorithmique; Exact; Exponentiel; Graphes; Énumération; Input-sensitive; Problèmes NP-difficiles; Algorithms; Exact; Exponential; Graphs; NP-hard problems; Time complexity; Enumeration; Input-sensitive; 005.1; 004.015 1

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Sayadi, M. Y. (2019). Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive : Design and analysis of exact exponential algorithms : input-sensitive enumeration. (Doctoral Dissertation). Université de Lorraine. Retrieved from http://www.theses.fr/2019LORR0316

Chicago Manual of Style (16^th Edition):

Sayadi, Mohamed Yosri. “Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive : Design and analysis of exact exponential algorithms : input-sensitive enumeration.” 2019. Doctoral Dissertation, Université de Lorraine. Accessed January 22, 2021. http://www.theses.fr/2019LORR0316.

MLA Handbook (7^th Edition):

Sayadi, Mohamed Yosri. “Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive : Design and analysis of exact exponential algorithms : input-sensitive enumeration.” 2019. Web. 22 Jan 2021.

Vancouver:

Sayadi MY. Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive : Design and analysis of exact exponential algorithms : input-sensitive enumeration. [Internet] [Doctoral dissertation]. Université de Lorraine; 2019. [cited 2021 Jan 22]. Available from: http://www.theses.fr/2019LORR0316.

Council of Science Editors:

Sayadi MY. Construction et analyse des algorithmes exacts et exponentiels : énumération input-sensitive : Design and analysis of exact exponential algorithms : input-sensitive enumeration. [Doctoral Dissertation]. Université de Lorraine; 2019. Available from: http://www.theses.fr/2019LORR0316

NSYSU

10. Liao, Hao-Chung. Construction of approximate optimal designs by exchange algorithm.

Degree: Master, Applied Mathematics, 2002, NSYSU

URL: http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0606102-142718

► In this study we will consider the construction of approximate optimal design for one-dimensional regression by exchange algorithm. Sufficient conditions under which an optimal design… (more)

Subjects/Keywords: D-optima; approximate; exact; exchange algorithm

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Liao, H. (2002). Construction of approximate optimal designs by exchange algorithm. (Thesis). NSYSU. Retrieved from http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0606102-142718

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Liao, Hao-Chung. “Construction of approximate optimal designs by exchange algorithm.” 2002. Thesis, NSYSU. Accessed January 22, 2021. http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0606102-142718.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Liao, Hao-Chung. “Construction of approximate optimal designs by exchange algorithm.” 2002. Web. 22 Jan 2021.

Vancouver:

Liao H. Construction of approximate optimal designs by exchange algorithm. [Internet] [Thesis]. NSYSU; 2002. [cited 2021 Jan 22]. Available from: http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0606102-142718.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Liao H. Construction of approximate optimal designs by exchange algorithm. [Thesis]. NSYSU; 2002. Available from: http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0606102-142718

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Universidade do Rio Grande do Norte

11. Pereira, Elder Gonçalves. O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico .

Degree: 2014, Universidade do Rio Grande do Norte

URL: http://repositorio.ufrn.br/handle/123456789/18104

► The Hiker Dice was a game recently proposed in a software designed by Mara Kuzmich and Leonardo Goldbarg. In the game a dice is responsible… (more)

Subjects/Keywords: Hiker Dice. Algoritmo Exato. Algoritmos Heurísticos; Hiker Dice. Exact Algorithm. Heuristic Algorithms

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Pereira, E. G. (2014). O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico . (Thesis). Universidade do Rio Grande do Norte. Retrieved from http://repositorio.ufrn.br/handle/123456789/18104

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Pereira, Elder Gonçalves. “O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico .” 2014. Thesis, Universidade do Rio Grande do Norte. Accessed January 22, 2021. http://repositorio.ufrn.br/handle/123456789/18104.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Pereira, Elder Gonçalves. “O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico .” 2014. Web. 22 Jan 2021.

Vancouver:

Pereira EG. O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico . [Internet] [Thesis]. Universidade do Rio Grande do Norte; 2014. [cited 2021 Jan 22]. Available from: http://repositorio.ufrn.br/handle/123456789/18104.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Pereira EG. O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico . [Thesis]. Universidade do Rio Grande do Norte; 2014. Available from: http://repositorio.ufrn.br/handle/123456789/18104

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Universidade do Rio Grande do Norte

12. Pereira, Elder Gonçalves. O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico .

Degree: 2014, Universidade do Rio Grande do Norte

URL: http://repositorio.ufrn.br/handle/123456789/18104

► The Hiker Dice was a game recently proposed in a software designed by Mara Kuzmich and Leonardo Goldbarg. In the game a dice is responsible… (more)

Subjects/Keywords: Hiker Dice. Algoritmo Exato. Algoritmos Heurísticos; Hiker Dice. Exact Algorithm. Heuristic Algorithms

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Pereira, E. G. (2014). O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico . (Masters Thesis). Universidade do Rio Grande do Norte. Retrieved from http://repositorio.ufrn.br/handle/123456789/18104

Chicago Manual of Style (16^th Edition):

Pereira, Elder Gonçalves. “O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico .” 2014. Masters Thesis, Universidade do Rio Grande do Norte. Accessed January 22, 2021. http://repositorio.ufrn.br/handle/123456789/18104.

MLA Handbook (7^th Edition):

Pereira, Elder Gonçalves. “O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico .” 2014. Web. 22 Jan 2021.

Vancouver:

Pereira EG. O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico . [Internet] [Masters thesis]. Universidade do Rio Grande do Norte; 2014. [cited 2021 Jan 22]. Available from: http://repositorio.ufrn.br/handle/123456789/18104.

Council of Science Editors:

Pereira EG. O problema do Hiker Dice em tabuleiro compacto: um estudo algorítmico . [Masters Thesis]. Universidade do Rio Grande do Norte; 2014. Available from: http://repositorio.ufrn.br/handle/123456789/18104

Wayne State University

13. Turgut, Ozgu. Exact And Representative Algorithms For Multi Objective Optimization.

Degree: PhD, Industrial and Manufacturing Engineering, 2013, Wayne State University

URL: https://digitalcommons.wayne.edu/oa_dissertations/929

► In most real-life problems, the decision alternatives are evaluated with multiple conflicting criteria. The entire set of non-dominated solutions for practical problems is impossible… (more)

▼ In most real-life problems, the decision alternatives are evaluated with multiple conflicting criteria. The entire set of non-dominated solutions for practical problems is impossible to obtain with reasonable computational effort. Decision maker generally needs only a representative set of solutions from the actual Pareto front. First algorithm we present is for efficiently generating a well dispersed non-dominated solution set representative of the Pareto front which can be used for general multi objective optimization problem. The algorithm first partitions the criteria space into grids to generate reference points and then searches for non-dominated solutions in each grid. This grid-based search utilizes achievement scalarization function and guarantees Pareto optimality. The results of our experimental results demonstrate that the proposed method is very competitive with other algorithms in literature when representativeness quality is considered; and advantageous from the computational efficiency point of view. Although generating the whole Pareto front does not seem very practical for many real life cases, sometimes it is required for verification purposes or where DM wants to run his decision making structures on the full set of Pareto solutions. For this purpose we present another novel algorithm. This algorithm attempts to adapt the standard branch and bound approach to the multi objective context by proposing to branch on solution points on objective space. This algorithm is proposed for multi objective integer optimization type of problems. Various properties of branch and bound concept has been investigated and explained within the multi objective optimization context such as fathoming, node selection, heuristics, as well as some multi objective optimization specific concepts like filtering, non-domination probability, running in parallel. Potential of this approach for being used both as a full Pareto generation or an approximation approach has been shown with experimental studies. Advisors/Committee Members: Alper E. Murat.

Subjects/Keywords: algorithm; branch-and-bound; exact; multi-objective; optimization; representative; Engineering; Operational Research

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Turgut, O. (2013). Exact And Representative Algorithms For Multi Objective Optimization. (Doctoral Dissertation). Wayne State University. Retrieved from https://digitalcommons.wayne.edu/oa_dissertations/929

Chicago Manual of Style (16^th Edition):

Turgut, Ozgu. “Exact And Representative Algorithms For Multi Objective Optimization.” 2013. Doctoral Dissertation, Wayne State University. Accessed January 22, 2021. https://digitalcommons.wayne.edu/oa_dissertations/929.

MLA Handbook (7^th Edition):

Turgut, Ozgu. “Exact And Representative Algorithms For Multi Objective Optimization.” 2013. Web. 22 Jan 2021.

Vancouver:

Turgut O. Exact And Representative Algorithms For Multi Objective Optimization. [Internet] [Doctoral dissertation]. Wayne State University; 2013. [cited 2021 Jan 22]. Available from: https://digitalcommons.wayne.edu/oa_dissertations/929.

Council of Science Editors:

Turgut O. Exact And Representative Algorithms For Multi Objective Optimization. [Doctoral Dissertation]. Wayne State University; 2013. Available from: https://digitalcommons.wayne.edu/oa_dissertations/929

14. MOTA, Alexandre Cabral. Model checking CSPZ: Techniques to overcome state explosion .

Degree: 2001, Universidade Federal de Pernambuco

URL: http://repositorio.ufpe.br/handle/123456789/1909

Cabral Mota, Alexandre; Cezar Alves Sampaio, Augusto. Model checking CSPZ: Techniques to overcome state explosion. 2001. Tese (Doutorado). Programa de Pós-Graduação em Ciência da Computação, Universidade Federal de Pernambuco, Recife, 2001. Advisors/Committee Members: Sampaio, Augusto Cezar Alves (advisor).

Subjects/Keywords: CSPz; Algorithm implementations; Exponential explosion; Theorem

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

MOTA, A. C. (2001). Model checking CSPZ: Techniques to overcome state explosion . (Thesis). Universidade Federal de Pernambuco. Retrieved from http://repositorio.ufpe.br/handle/123456789/1909

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

MOTA, Alexandre Cabral. “Model checking CSPZ: Techniques to overcome state explosion .” 2001. Thesis, Universidade Federal de Pernambuco. Accessed January 22, 2021. http://repositorio.ufpe.br/handle/123456789/1909.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

MOTA, Alexandre Cabral. “Model checking CSPZ: Techniques to overcome state explosion .” 2001. Web. 22 Jan 2021.

Vancouver:

MOTA AC. Model checking CSPZ: Techniques to overcome state explosion . [Internet] [Thesis]. Universidade Federal de Pernambuco; 2001. [cited 2021 Jan 22]. Available from: http://repositorio.ufpe.br/handle/123456789/1909.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

MOTA AC. Model checking CSPZ: Techniques to overcome state explosion . [Thesis]. Universidade Federal de Pernambuco; 2001. Available from: http://repositorio.ufpe.br/handle/123456789/1909

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Plymouth

15. Arabi, Mohamed. Improving fairness and utilisation in ad hoc networks.

Degree: PhD, 2012, University of Plymouth

URL: http://hdl.handle.net/10026.1/1167

► Ad hoc networks represent the current de-facto alternative for infrastructure-less environments, due to their self-configuring and resilience characteristics. Ad hoc networks flexibility benefits, such as… (more)

▼ Ad hoc networks represent the current de-facto alternative for infrastructure-less environments, due to their self-configuring and resilience characteristics. Ad hoc networks flexibility benefits, such as unrestrained computing, lack of centralisation, and ease of deployment at low costs, are tightly bound with relevant deficiencies such as limited resources and management difficulty. Ad hoc networks witnessed high attention from the research community due to the numerous challenges faced when deploying such a technology in real scenarios. Starting with the nature of the wireless environment, which raises significant transmission issues when compared with the wired counterpart, ad hoc networks require a different approach when addressing the data link problems. Further, the high packet loss due to wireless contention, independent of network congestion, requires a different approach when considering quality of service degradation and unfair channel resources distribution among competing flows. Although these issues have already been considered to some extent by researchers, there is still room to improve quality of service by reducing the effect of packet loss and fairly distributing the medium access among competing nodes. The aim of this thesis is to propose a set of mechanisms to alleviate the effect of packet loss and to improve fairness in ad hoc networks. A transport layer algorithm has been proposed to overcome the effects of hidden node collisions and to reduce the impact of wireless link contention by estimating the four hop delay and pacing packet transmissions accordingly. Furthermore, certain topologies have been identified, in which the standard IEEE 802.11 faces degradation in channel utilisation and unfair bandwidth allocation. Three link layer mechanisms have been proposed to tackle the challenges the IEEE 802.11 faces in the identified scenarios to impose fairness in ad hoc networks through fairly distributing channel resources between competing nodes. These mechanisms are based on monitoring the collision rate and penalising the greedy nodes where no competing nodes can be detected but interference exists, monitoring traffic at source nodes to police access to the channel where only source nodes are within transmission range of each other, and using MAC layer acknowledgements to flag unfair bandwidth allocation in topologies where only the receivers are within transmission range of each other. The proposed mechanisms have been integrated into a framework designed to adapt and to dynamically select which mechanism to adopt, depending on the network topology. It is important to note that the proposed mechanisms and framework are not alternatives to the standard MAC protocol but are an enhancement and are triggered by the failure of the IEEE 802.11 protocol to distribute the channel resources fairly. All the proposed mechanisms have been validated through simulations and the results obtained from the experiments show that the proposed schemes fairly distribute channel resources fairly and outperform the…

Subjects/Keywords: 004.68; Fairness, channel utilisation, ad hoc networks, 802.11, contention window, exponential back off algorithm.

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Arabi, M. (2012). Improving fairness and utilisation in ad hoc networks. (Doctoral Dissertation). University of Plymouth. Retrieved from http://hdl.handle.net/10026.1/1167

Chicago Manual of Style (16^th Edition):

Arabi, Mohamed. “Improving fairness and utilisation in ad hoc networks.” 2012. Doctoral Dissertation, University of Plymouth. Accessed January 22, 2021. http://hdl.handle.net/10026.1/1167.

MLA Handbook (7^th Edition):

Arabi, Mohamed. “Improving fairness and utilisation in ad hoc networks.” 2012. Web. 22 Jan 2021.

Vancouver:

Arabi M. Improving fairness and utilisation in ad hoc networks. [Internet] [Doctoral dissertation]. University of Plymouth; 2012. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/10026.1/1167.

Council of Science Editors:

Arabi M. Improving fairness and utilisation in ad hoc networks. [Doctoral Dissertation]. University of Plymouth; 2012. Available from: http://hdl.handle.net/10026.1/1167

University of New South Wales

16. Ye, Shanglin. Signal Detection and Parameter Estimation for Nuclear Magnetic Resonance Spectroscopy.

Degree: Electrical Engineering & Telecommunications, 2015, University of New South Wales

URL: http://handle.unsw.edu.au/1959.4/55307 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:37090/SOURCE02?view=true

► Nuclear Magnetic Resonance spectroscopy (NMR), as the prime technique for efficient and rapid screening of the compounds in chemical samples, represents the nuclei in molecules… (more)

▼ Nuclear Magnetic Resonance spectroscopy (NMR), as the prime technique for efficient and rapid screening of the compounds in chemical samples, represents the nuclei in molecules as resonance peaks in the spectrum. The peaks are regarded as the “fingerprints” of the chemical components in the molecules, providing necessary information for researchers to elucidate the structure of the chemicals.The time domain signal obtained in the modern NMR experiment can ideally be modelled as the superposition of multiple damped complex exponentials in additive Gaussian noise. For obtaining key information of the chemical compound being analysed, all the useful components should be successfully detected and algorithms should be applied to estimate their parameters. However, practical features including large signal size, unknown number of components, the existence of weak and overlapped peaks, and signal distortions caused by experimental artefacts, make these tasks hard to achieve. In this thesis, we focus on finding effective methods for the signal detection and parameter estimation problems for NMR signals that are capable of handling the practical signal features.To tackle the signal detection problem, we develop the Localised Capon spectral Estimator (LoCapE), which is a high resolution spectral estimator in selected regions of the spectrum. Without a priori knowledge on the number of components, LoCapE is capable of resolving extremely closely spaced components in experimental NMR signals that cannot be separated by the Discrete Fourier Transform (DFT).In terms of the parameter estimation problem, we put forward several novel frequency domain interpolation algorithms for efficiently estimating parameters of signals related to the ideal NMR signal model. We first present the 2-D version of the parameter estimation algorithm proposed by Aboutanios and Mulgrew (the A&M algorithm), for estimating the frequencies/parameters of single 2-D exponentials in noise. This is followed by the presentation of the Iterative Windowed A&M (IWAM) algorithm for the estimation of the frequency and damping factor of a 1-D damped exponential in noise, that is robust when the signal has a long noisy tail. By combining with a leakage subtraction scheme, the A&M algorithm and the IWAM algorithm are then extended to the Multi-tone A&M (MAM) algorithms which address the parameter estimation of ideal 1-D NMR signals. Theoretical analysis and simulation results show that all the proposed parameter estimators are able to achieve performance that is extremely close to the Cramer-Rao Lower Bound (CRLB).To achieve simultaneous signal detection and parameter estimation of actual NMR signals, the IWAM algorithm is finally incorporated with a generalised lineshape model and a least squares lineshape adaptation scheme. This results the Peak Extraction using Adaptive Lineshape (PEAL) algorithm which can obtain reliable component extraction and accurate parameter estimation on experimental proton NMR datasets with arbitrary lineshape distortion. Advisors/Committee Members: Aboutanios, Elias, Electrical Engineering & Telecommunications, Faculty of Engineering, UNSW.

Subjects/Keywords: Complex exponential; Nuclear magnetic resonance; Frequency estimation; Interpolation algorithm; High resolution spectral estimator; Lineshape adaptation

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Ye, S. (2015). Signal Detection and Parameter Estimation for Nuclear Magnetic Resonance Spectroscopy. (Doctoral Dissertation). University of New South Wales. Retrieved from http://handle.unsw.edu.au/1959.4/55307 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:37090/SOURCE02?view=true

Chicago Manual of Style (16^th Edition):

Ye, Shanglin. “Signal Detection and Parameter Estimation for Nuclear Magnetic Resonance Spectroscopy.” 2015. Doctoral Dissertation, University of New South Wales. Accessed January 22, 2021. http://handle.unsw.edu.au/1959.4/55307 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:37090/SOURCE02?view=true.

MLA Handbook (7^th Edition):

Ye, Shanglin. “Signal Detection and Parameter Estimation for Nuclear Magnetic Resonance Spectroscopy.” 2015. Web. 22 Jan 2021.

Vancouver:

Ye S. Signal Detection and Parameter Estimation for Nuclear Magnetic Resonance Spectroscopy. [Internet] [Doctoral dissertation]. University of New South Wales; 2015. [cited 2021 Jan 22]. Available from: http://handle.unsw.edu.au/1959.4/55307 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:37090/SOURCE02?view=true.

Council of Science Editors:

Ye S. Signal Detection and Parameter Estimation for Nuclear Magnetic Resonance Spectroscopy. [Doctoral Dissertation]. University of New South Wales; 2015. Available from: http://handle.unsw.edu.au/1959.4/55307 ; https://unsworks.unsw.edu.au/fapi/datastream/unsworks:37090/SOURCE02?view=true

17. Sultan, Ziad. Algèbre linéaire exacte, parallèle, adaptative et générique : Adaptive and generic parallel exact linear algebra.

Degree: Docteur es, Mathématiques Appliquées, 2016, Université Grenoble Alpes (ComUE)

URL: http://www.theses.fr/2016GREAM030

►

Les décompositions en matrices triangulaires sont une brique de base fondamentale en calcul algébrique. Ils sont utilisés pour résoudre des systèmes linéaires et calculer le… (more)

▼

Les décompositions en matrices triangulaires sont une brique de base fondamentale en calcul algébrique. Ils sont utilisés pour résoudre des systèmes linéaires et calculer le rang, le déterminant, l'espace nul ou les profiles de rang en ligne et en colonne d'une matrix. Le projet de cette thèse est de développer des implantations hautes performances parallèles de l'élimination de Gauss exact sur des machines à mémoire partagée.Dans le but d'abstraire le code de l'environnement de calcul parallèle utilisé, un langage dédié PALADIn (Parallel Algebraic Linear Algebra Dedicated Interface) a été implanté et est basé essentiellement sur des macros C/C++. Ce langage permet à l'utilisateur d'écrire un code C++ et tirer partie d’exécutions séquentielles et parallèles sur des architectures à mémoires partagées en utilisant le standard OpenMP et les environnements parallel KAAPI et TBB, ce qui lui permet de bénéficier d'un parallélisme de données et de taches.Plusieurs aspects de l'algèbre linéaire exacte parallèle ont été étudiés. Nous avons construit de façon incrémentale des noyaux parallèles efficaces pour les multiplication de matrice, la résolution de systèmes triangulaires au dessus duquel plusieurs variantes de l'algorithme de décomposition PLUQ sont construites. Nous étudions la parallélisation de ces noyaux en utilisant plusieurs variantes algorithmiques itératives ou récursives et en utilisant des stratégies de découpes variées.Nous proposons un nouvel algorithme récursive de l'élimination de Gauss qui peut calculer simultanément les profiles de rang en ligne et en colonne d'une matrice et de toutes ses sous-matrices principales, tout en étant un algorithme état de l'art de l'élimination de Gauss. Nous étudions aussi les conditions pour qu'un algorithme de l'élimination de Gauss révèle cette information en définissant un nouvel invariant matriciel, la matrice de profil de rang.

Triangular matrix decompositions are fundamental building blocks in computational linear algebra. They are used to solve linear systems, compute the rank, the determinant, the null-space or the row and column rank profiles of a matrix. The project of my PhD thesis is to develop high performance shared memory parallel implementations of exact Gaussian elimination.In order to abstract the computational code from the parallel programming environment, we developed a domain specific language, PALADIn: Parallel Algebraic Linear Algebra Dedicated Interface, that is based on C/C + + macros. This domain specific language allows the user to write C + + code and benefit from sequential and parallel executions on shared memory architectures using the standard OpenMP, TBB and Kaapi parallel runtime systems and thus providing data and task parallelism.Several aspects of parallel exact linear algebra were studied. We incrementally build efficient parallel kernels, for matrix multiplication, triangular system solving, on top of which several variants of PLUQ decomposition algorithm are built. We study the parallelization of these kernels using several…

Advisors/Committee Members: Dumas, Jean-Guillaume (thesis director), Pernet, Clément (thesis director).

Subjects/Keywords: Calcul parallèl; Algèbre linéaire; Calcul exact; Algorithme adaptatives; Mathématiques computationnelles; Parallèlisme de flot de données; Parallel computation; Computer algebra; Exact computation; Adaptive algorithm; Computational mathematics; Dataflow parallelism; 510

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Sultan, Z. (2016). Algèbre linéaire exacte, parallèle, adaptative et générique : Adaptive and generic parallel exact linear algebra. (Doctoral Dissertation). Université Grenoble Alpes (ComUE). Retrieved from http://www.theses.fr/2016GREAM030

Chicago Manual of Style (16^th Edition):

Sultan, Ziad. “Algèbre linéaire exacte, parallèle, adaptative et générique : Adaptive and generic parallel exact linear algebra.” 2016. Doctoral Dissertation, Université Grenoble Alpes (ComUE). Accessed January 22, 2021. http://www.theses.fr/2016GREAM030.

MLA Handbook (7^th Edition):

Sultan, Ziad. “Algèbre linéaire exacte, parallèle, adaptative et générique : Adaptive and generic parallel exact linear algebra.” 2016. Web. 22 Jan 2021.

Vancouver:

Sultan Z. Algèbre linéaire exacte, parallèle, adaptative et générique : Adaptive and generic parallel exact linear algebra. [Internet] [Doctoral dissertation]. Université Grenoble Alpes (ComUE); 2016. [cited 2021 Jan 22]. Available from: http://www.theses.fr/2016GREAM030.

Council of Science Editors:

Sultan Z. Algèbre linéaire exacte, parallèle, adaptative et générique : Adaptive and generic parallel exact linear algebra. [Doctoral Dissertation]. Université Grenoble Alpes (ComUE); 2016. Available from: http://www.theses.fr/2016GREAM030

18. Letourneur, Romain. Algorithmes exacts et exponentiels pour des problèmes de graphes : Exact exponential algorithms for solving graph problems summary.

Degree: Docteur es, Informatique, 2015, Université d'Orléans

URL: http://www.theses.fr/2015ORLE2022

►

De nombreux problèmes algorithmiques sont « difficiles », dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la… (more)

▼

De nombreux problèmes algorithmiques sont « difficiles », dans le sens où on ne sait pas les résoudre en temps polynomial par rapport à la taille de l’entrée, soit parce qu’ils sont NP-difficiles, soit, pour certains problèmes d’énumération, à cause du nombre exponentiel d'objets à énumérer. Depuis une quinzaine d’années on trouve un intérêt grandissant dans la littérature pour la conception d'algorithmes exacts sophistiqués afin de les résoudre le plus efficacement possible. Dans le cadre de cette thèse, nous nous intéressons à la conception d'algorithmes exacts exponentiels autour de trois problèmes difficiles. Nous étudions tout d'abord le problème d'optimisation Ensemble Connexe Tropical pour lequel nous décrivons un algorithme afin de le résoudre en général, puis un algorithme de branchement plus rapide pour le résoudre sur les arbres, ce problème restant difficile même dans ce cas. Nous nous intéressons ensuite au problème d'énumération Ensembles Dominants Minimaux, pour lequel nous donnons des algorithmes résolvant ce problème dans les graphes splits, cobipartis, ainsi que dans les graphes d'intervalles. Nous déduisons des bornes supérieures sur le nombre d'ensembles dominants minimaux admis par de tels graphes. La dernière étude de cette thèse concerne le problème d'optimisation Domination Romaine Faible dans lequel, étant donné un graphe nous cherchons à construire une fonction de pondération selon certaines propriétés. Le problème est NP-difficile en général, mais nous donnons un algorithme glouton linéaire calculant une telle fonction pour les graphes d'intervalles.

Many algorithmic problems are « hard », in the sense of we do not know how to solve them in polynomialtime, either because they are NP-hard, or, for some enumeration problems, because the number of objectsto be produced is exponential. During the last fifteen years there was a growing interest in the design of exact algorithms to solve such problems as efficiently as possible. In the context of this thesis, we focus on the design of exponential exact algorithms for three hard problems. First, we study the optimisation problem Tropical Connected Set for which we describe an algorithm to solve it in the general case, then a faster branch-and-reduce algorithm to solve it on trees; the problem remains difficult even in this case. Secondly we focus on the Minimal Dominating Sets enumeration problem, for which we give algorithms to solve it on split, cobipartite and intervals graphs. As a byproduct, we establish upper bounds on the number of minimal dominating sets in such graphs. The last focus of this thesis concerns the Weak Roman Domination optimisation problem for which, given a graph, the goal is to build a weight function under some properties. The problem is NP-hard in general, but we give a linear greedy algorithm which computes such a function on interval graphs.

Advisors/Committee Members: Todinca, Ioan (thesis director), Liedloff, Mathieu (thesis director).

Subjects/Keywords: Algorithmes; Algorithmes exacts exponentiels; Graphes; Ensembles dominants; Domination romaine faible; Ensemble connexe tropical; Algorithms; Exact exponential algorithms; Graphs; Dominating sets; Weak roman domination; Tropical connected set; 005.1

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Letourneur, R. (2015). Algorithmes exacts et exponentiels pour des problèmes de graphes : Exact exponential algorithms for solving graph problems summary. (Doctoral Dissertation). Université d'Orléans. Retrieved from http://www.theses.fr/2015ORLE2022

Chicago Manual of Style (16^th Edition):

Letourneur, Romain. “Algorithmes exacts et exponentiels pour des problèmes de graphes : Exact exponential algorithms for solving graph problems summary.” 2015. Doctoral Dissertation, Université d'Orléans. Accessed January 22, 2021. http://www.theses.fr/2015ORLE2022.

MLA Handbook (7^th Edition):

Letourneur, Romain. “Algorithmes exacts et exponentiels pour des problèmes de graphes : Exact exponential algorithms for solving graph problems summary.” 2015. Web. 22 Jan 2021.

Vancouver:

Letourneur R. Algorithmes exacts et exponentiels pour des problèmes de graphes : Exact exponential algorithms for solving graph problems summary. [Internet] [Doctoral dissertation]. Université d'Orléans; 2015. [cited 2021 Jan 22]. Available from: http://www.theses.fr/2015ORLE2022.

Council of Science Editors:

Letourneur R. Algorithmes exacts et exponentiels pour des problèmes de graphes : Exact exponential algorithms for solving graph problems summary. [Doctoral Dissertation]. Université d'Orléans; 2015. Available from: http://www.theses.fr/2015ORLE2022

The Ohio State University

19. Sridhar, Vijay, Sridhar. On the effect of asymmetry and dimension on computational geometric problems.

Degree: PhD, Computer Science and Engineering, 2018, The Ohio State University

URL: http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304

► We study two aspects of metric spaces that affect the computational complexity of geometric problems. First, we study directed cut problems and the associated multi-commodity… (more)

▼ We study two aspects of metric spaces that affect the computational complexity of geometric problems. First, we study directed cut problems and the associated multi-commodity flow-cut gap on different classes of directed graphs. We look at generalizations of classical metric embedding results to the case of quasimetric spaces; that is, spaces that do not necessarily satisfy symmetry. Quasimetric spaces arise naturally from the shortest-path distances on directed graphs.Random embeddings are arguably one of the most successful geometric tools in the context of algorithm design. We extend this set of tools to the quasimetric case to obtain the following results. We present a t log ^O(1) n-approximation algorithms for the Directed Non-Bipartite Sparsest-Cut and the Directed Multicut problems on n-vertex graphs of treewidth t, with running time polynomial in both n and t. We also give O(1)-approximation algorithms for the Uniform Directed Non-Bipartite Sparsest-Cut and the Directed Multicut problems on series-parallel digraphs and digraphs of bounded pathwidth. We also show that any n-point quasimetric space supported on a graph of treewidth t admits a random embedding into quasiultrametric spaces with distortion O(t log ² n), where quasiultrametrics are a natural generalization of ultrametrics. For directed cycles and directed trees we show an embedding into directed ℓ ₁ space with constant distortion.The above results are obtained by considering a generalization of random partitions to the quasimetric case, which we refer to as random quasipartitions. Using this definition and a construction of [Chuzhoy and Khanna 2009] we derive a polynomial lower bound on the distortion of random embeddings of general quasimetric spaces into quasiultrametric spaces. We also establish a lower bound for embedding the shortest-path quasimetric of a graph G into graphs that exclude G as a minor. Finally, we show an Ω(n) lower bound for random non-contracting embeddings of directed cycles into directed trees. These lower bounds are used to show that several embedding results from the metric case do not have natural analogues in the quasimetric setting.Next, we study the effect of dimension on the complexity of computational geometry problems. Specifically, we study problems on subsets of Euclidean space of low fractal dimension. There are several well-studied notions of fractal dimension for sets and measures in Euclidean space. We consider a definition of fractal dimension for finite metric spaces which agrees with standard notions used to empirically estimate the fractal dimension of various sets.We define the fractal dimension of some metric space to be the infimum δ>0, such that for any ε>0, for any ball B of radius r≥ 2ε, and for any ε-net N (that is, for any maximal ε-packing), we have |B ∩ N|=O((r/ε)^δ).Using… Advisors/Committee Members: Sidiropoulos, Anastasios (Advisor), Wang, Yusu (Advisor).

Subjects/Keywords: Computer Science; Metric-Embeddings; Quasimetrics; Random-Embeddings; Treewidth; Directed Sparsest-Cut; Directed Multi-Cut; Fractal-Dimension; Exact-Algorithms; Fixed-Parameter-Tractability; Approximation- Schemes; Spanners; Lower-Bounds; Exponential-Time-Hypothesis

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Sridhar, Vijay, S. (2018). On the effect of asymmetry and dimension on computational geometric problems. (Doctoral Dissertation). The Ohio State University. Retrieved from http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304

Chicago Manual of Style (16^th Edition):

Sridhar, Vijay, Sridhar. “On the effect of asymmetry and dimension on computational geometric problems.” 2018. Doctoral Dissertation, The Ohio State University. Accessed January 22, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304.

MLA Handbook (7^th Edition):

Sridhar, Vijay, Sridhar. “On the effect of asymmetry and dimension on computational geometric problems.” 2018. Web. 22 Jan 2021.

Vancouver:

Sridhar, Vijay S. On the effect of asymmetry and dimension on computational geometric problems. [Internet] [Doctoral dissertation]. The Ohio State University; 2018. [cited 2021 Jan 22]. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304.

Council of Science Editors:

Sridhar, Vijay S. On the effect of asymmetry and dimension on computational geometric problems. [Doctoral Dissertation]. The Ohio State University; 2018. Available from: http://rave.ohiolink.edu/etdc/view?acc_num=osu1531362300593304

Univerzitet u Beogradu

20. Kordić, Stevan Lj., 1969-. Метод седиментације и његове примјене у проблемима дискретне математике.

Degree: Matematički fakultet, 2018, Univerzitet u Beogradu

URL: https://fedorabg.bg.ac.rs/fedora/get/o:15359/bdef:Content/get

►

Математика - Дискретна математика / Mathematics - Discrete mathematics

Проблеми задовољења ограничења, којима припадају и проблеми оптимизације, спадају у веома значајне проблеме дискретне математике са… (more)

▼

Математика - Дискретна математика / Mathematics - Discrete mathematics

Проблеми задовољења ограничења, којима припадају и проблеми оптимизације, спадају у веома значајне проблеме дискретне математике са широким пољем употребе у математици и њеним примјенама. Дисертација разматра проблем оптимизације и предлаже оригиналан метод за његово тачно рјешавање. Назив алгоритма који се приказује у тези је метод седиментације и приказан је заједно са двије своје хеуристике. Спада у класу алгоритама „гранања и ограничавања“, који користе механизме „враћања по трагу“ и „провјере унапријед“. Доказана је његова тотална коректност методе седиментације. Као илустрација примијенљивости методе седиментације, у дисертацији су разматране примјене ове методе на проблеме исказне задовољивости, Вајтхедов проблем минимизације и проблем додјеле везова бродовима у контејнерским лукама. Најбоље резултате метода је показала рјешавајући проблеме додјеле везова, јер је моделовање овог проблема за рјешавање методом седиментације укључивало све оптимизацијске технике, којима метода располаже. Такође, за проблем додјеле везове, утврђена је прецизна оцјена комплексности методе седиментације. Експериментални резултати потврђују да метода седиментације може да рјешава проблеме додјеле везова на нивоу најбољих приступа овом проблему.

Advisors/Committee Members: Mijajlović, Žarko, 1948-.

Subjects/Keywords: constrain satisfaction problem; optimisation problem; discrete mathematics; combinatorial optimisation; exact solution; algorithm; Boolean satisfiability; Whitehead minimisation problem; berth Allocation problem

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Kordić, Stevan Lj., 1. (2018). Метод седиментације и његове примјене у проблемима дискретне математике. (Thesis). Univerzitet u Beogradu. Retrieved from https://fedorabg.bg.ac.rs/fedora/get/o:15359/bdef:Content/get

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Kordić, Stevan Lj., 1969-. “Метод седиментације и његове примјене у проблемима дискретне математике.” 2018. Thesis, Univerzitet u Beogradu. Accessed January 22, 2021. https://fedorabg.bg.ac.rs/fedora/get/o:15359/bdef:Content/get.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Kordić, Stevan Lj., 1969-. “Метод седиментације и његове примјене у проблемима дискретне математике.” 2018. Web. 22 Jan 2021.

Vancouver:

Kordić, Stevan Lj. 1. Метод седиментације и његове примјене у проблемима дискретне математике. [Internet] [Thesis]. Univerzitet u Beogradu; 2018. [cited 2021 Jan 22]. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:15359/bdef:Content/get.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Kordić, Stevan Lj. 1. Метод седиментације и његове примјене у проблемима дискретне математике. [Thesis]. Univerzitet u Beogradu; 2018. Available from: https://fedorabg.bg.ac.rs/fedora/get/o:15359/bdef:Content/get

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

21. Takiyama, Felipe Iwao. Algoritmos de inferência exata para modelos de primeira ordem.

Degree: Mestrado, Engenharia de Controle e Automação Mecânica, 2014, University of São Paulo

URL: http://www.teses.usp.br/teses/disponiveis/3/3152/tde-23122014-145932/ ;

►

Este trabalho descreve a implementação de algoritmos de inferência para modelos de primeira ordem. Três algoritmos foram implementados: ve, c-fove e ac-fove. Este último e… (more)

Subjects/Keywords: AC-FOVE; AC-FOVE; Algoritmo de eliminação de variáveis em primeira ordem; Algoritmo de inferência exata; Exact inference algorithm; First-order variable elimination algorithm

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Takiyama, F. I. (2014). Algoritmos de inferência exata para modelos de primeira ordem. (Masters Thesis). University of São Paulo. Retrieved from http://www.teses.usp.br/teses/disponiveis/3/3152/tde-23122014-145932/ ;

Chicago Manual of Style (16^th Edition):

Takiyama, Felipe Iwao. “Algoritmos de inferência exata para modelos de primeira ordem.” 2014. Masters Thesis, University of São Paulo. Accessed January 22, 2021. http://www.teses.usp.br/teses/disponiveis/3/3152/tde-23122014-145932/ ;.

MLA Handbook (7^th Edition):

Takiyama, Felipe Iwao. “Algoritmos de inferência exata para modelos de primeira ordem.” 2014. Web. 22 Jan 2021.

Vancouver:

Takiyama FI. Algoritmos de inferência exata para modelos de primeira ordem. [Internet] [Masters thesis]. University of São Paulo; 2014. [cited 2021 Jan 22]. Available from: http://www.teses.usp.br/teses/disponiveis/3/3152/tde-23122014-145932/ ;.

Council of Science Editors:

Takiyama FI. Algoritmos de inferência exata para modelos de primeira ordem. [Masters Thesis]. University of São Paulo; 2014. Available from: http://www.teses.usp.br/teses/disponiveis/3/3152/tde-23122014-145932/ ;

University of Waterloo

22. Simjour, Narges. A New Optimality Measure for Distance Dominating Sets.

Degree: 2006, University of Waterloo

URL: http://hdl.handle.net/10012/2941

► We study the problem of finding the smallest power of an input graph that has k disjoint dominating sets, where the ith power of an… (more)

Subjects/Keywords: Computer Science; distance dominating set; domatic number; approximation algorithm; exact algorithm; spanner

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Simjour, N. (2006). A New Optimality Measure for Distance Dominating Sets. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/2941

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Simjour, Narges. “A New Optimality Measure for Distance Dominating Sets.” 2006. Thesis, University of Waterloo. Accessed January 22, 2021. http://hdl.handle.net/10012/2941.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Simjour, Narges. “A New Optimality Measure for Distance Dominating Sets.” 2006. Web. 22 Jan 2021.

Vancouver:

Simjour N. A New Optimality Measure for Distance Dominating Sets. [Internet] [Thesis]. University of Waterloo; 2006. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/10012/2941.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Simjour N. A New Optimality Measure for Distance Dominating Sets. [Thesis]. University of Waterloo; 2006. Available from: http://hdl.handle.net/10012/2941

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

23. Mameri, Djelloul. L'indépendant faiblement connexe : études algorithmiques et polyédrales : Weakly connected independent sets : algorithmic and polyhedral studies.

Degree: Docteur es, Informatique, 2014, Université Blaise-Pascale, Clermont-Ferrand II

URL: http://www.theses.fr/2014CLF22513

►

Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé… (more)

▼

Dans ce travail, nous nous intéressons à une topologie pour les réseaux de capteurs sans fil. Un réseau de capteurs sans fil peut être modélisé comme un graphe non orienté G = (V,E). Chaque sommet de V représente un capteur et une arête e = {u, v} dans E indique une transmission directe possible entre deux capteurs u et v. Contrairement aux dispositifs filaires, les capteurs sans fil ne sont pas a priori agencé en réseau. Une topologie doit être créée en sélectionnant des noeuds "dominants" qui vont gérer les transmissions. Les architectures qui ont été examinées dans la littérature reposent essentiellement sur les ensembles dominants connexes et les ensembles dominants faiblement connexes. Cette étude est consacrée aux ensembles indépendants faiblement connexes. Un indépendant S ⊂ V est dit faiblement connexe si le graphe GS = (V, [S, V \S]) est connexe, où [S, V \S] est l’ensemble des arêtes e = {u, v} de E avec u ∈ S et v ∈ V \S. Une topologie basée sur les ensembles faiblement connexes permet de partitionner l’ensemble des capteurs en trois groupes, les esclaves, les maîtres et les intermédiaires. Les premiers effectuent les mesures, les seconds rassemblent les données collectées et les troisièmes assurent les communications inter-groupes. Nous donnons d’abord quelques propriétés de cette structure combinatoire lorsque le graphe non orienté G est connexe. Puis nous proposons des résultats de complexité pour le problème de la recherche de l’indépendant faiblement connexe de cardinalité minimale (MWCISP). Nous décrivons également un algorithme d’énumération exact de complexité O∗(1.4655|V |) pour le MWCISP. Des tests numériques de cette procédure exacte sont présentés. Nous formulons ensuite le MWCISP comme un programme linéaire en nombres entiers. Le polytope associé aux solutions de ce problème est complètement caractérisé lorsque G est un cycle impair. Nous étudions des opérations de composition de graphes et leurs conséquences polyédrales. Nous introduisons des inégalités valides notamment les contraintes dites de multibord. Par la suite, nous développons un algorithme de coupes et branchement sous CPLEX pour résoudre ce problème en utilisant des heuristiques pour la séparation de nos familles de contraintes. Des résultats expérimentaux de ce programme sont exposés.

In this work, we focus on a topology for Wireless Sensor Networks (WSN). A wireless sensor network can be modeled as an undirected graph G = (V,E). Each vertex of V represents a sensor and an edge e = {u, v} in E implies a direct transmission between the two sensors u and v. Unlike wired devices, wireless sensors are not a priori arranged in a network. Topology should be made by selecting some sensor as dominators nodes who manage transmissions. Architectures that have been studied in the literature are mainly based on connected dominating sets and weakly connected dominating sets.This study is devoted to weakly connected independent sets. An independent set S ⊂ V is said Weakly Connected if the graph GS = (V, [S, V \S]) is connected, where [S, V…

Advisors/Committee Members: Bendali-Mailfert, Fatiha (thesis director).

Subjects/Keywords: Ensembles dominants; Indépendant faiblement connexe; Réseaux sans fil; Algorithme d’énumération exact; Polytope; Algorithme de coupes et branchement; Dominating set; Weakly connected independent set; Wireless networks; Exact algorithm; Branch-and-cut algorithm

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Mameri, D. (2014). L'indépendant faiblement connexe : études algorithmiques et polyédrales : Weakly connected independent sets : algorithmic and polyhedral studies. (Doctoral Dissertation). Université Blaise-Pascale, Clermont-Ferrand II. Retrieved from http://www.theses.fr/2014CLF22513

Chicago Manual of Style (16^th Edition):

Mameri, Djelloul. “L'indépendant faiblement connexe : études algorithmiques et polyédrales : Weakly connected independent sets : algorithmic and polyhedral studies.” 2014. Doctoral Dissertation, Université Blaise-Pascale, Clermont-Ferrand II. Accessed January 22, 2021. http://www.theses.fr/2014CLF22513.

MLA Handbook (7^th Edition):

Mameri, Djelloul. “L'indépendant faiblement connexe : études algorithmiques et polyédrales : Weakly connected independent sets : algorithmic and polyhedral studies.” 2014. Web. 22 Jan 2021.

Vancouver:

Mameri D. L'indépendant faiblement connexe : études algorithmiques et polyédrales : Weakly connected independent sets : algorithmic and polyhedral studies. [Internet] [Doctoral dissertation]. Université Blaise-Pascale, Clermont-Ferrand II; 2014. [cited 2021 Jan 22]. Available from: http://www.theses.fr/2014CLF22513.

Council of Science Editors:

Mameri D. L'indépendant faiblement connexe : études algorithmiques et polyédrales : Weakly connected independent sets : algorithmic and polyhedral studies. [Doctoral Dissertation]. Université Blaise-Pascale, Clermont-Ferrand II; 2014. Available from: http://www.theses.fr/2014CLF22513

Anna University

24. Kalpana M. Design and evaluation of energy efficient hierarchical energy tree based routing and exponential congestion control algorithms for wireless sensor networks;.

Degree: 2013, Anna University

URL: http://shodhganga.inflibnet.ac.in/handle/10603/13410

►

The vision of ubiquitous computing requires the development of devices and technologies which can be pervasive without being intrusive. The basic components of such a… (more)

Subjects/Keywords: Energy efficient; hierarchical energy tree; wireless sensor networks; additive increase and multiplicative decrease; Transmission Control Protocol/Exponential algorithm

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

M, K. (2013). Design and evaluation of energy efficient hierarchical energy tree based routing and exponential congestion control algorithms for wireless sensor networks;. (Thesis). Anna University. Retrieved from http://shodhganga.inflibnet.ac.in/handle/10603/13410

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

M, Kalpana. “Design and evaluation of energy efficient hierarchical energy tree based routing and exponential congestion control algorithms for wireless sensor networks;.” 2013. Thesis, Anna University. Accessed January 22, 2021. http://shodhganga.inflibnet.ac.in/handle/10603/13410.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

M, Kalpana. “Design and evaluation of energy efficient hierarchical energy tree based routing and exponential congestion control algorithms for wireless sensor networks;.” 2013. Web. 22 Jan 2021.

Vancouver:

M K. Design and evaluation of energy efficient hierarchical energy tree based routing and exponential congestion control algorithms for wireless sensor networks;. [Internet] [Thesis]. Anna University; 2013. [cited 2021 Jan 22]. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/13410.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

M K. Design and evaluation of energy efficient hierarchical energy tree based routing and exponential congestion control algorithms for wireless sensor networks;. [Thesis]. Anna University; 2013. Available from: http://shodhganga.inflibnet.ac.in/handle/10603/13410

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

University of Waterloo

25. Shahab, Mohamad T. A New Approach to Multi-Model Adaptive Control.

Degree: 2020, University of Waterloo

URL: http://hdl.handle.net/10012/15766

► Adaptive control is an approach used to deal with systems with uncertain or time-varying parameters. A classical adaptive controller typically consists of a linear time-invariant… (more)

▼ Adaptive control is an approach used to deal with systems with uncertain or time-varying parameters. A classical adaptive controller typically consists of a linear time-invariant (LTI) control law together with a tuning mechanism which adjusts its parameters. Usually, though not exclusively, discrete-time adaptive controllers provide only asymptotic stability and possibly bounded-noise bounded-state stability; neither exponential stability nor a bounded noise gain is typically proven. Recently it has been shown that if we employ a parameter estimator based on the original Projection Algorithm together with projecting the parameter estimates onto a given compact and convex set, then the adaptive controller guarantees linear-like closed-loop behavior: exponential stability, a bounded noise gain and a convolution bound on the exogenous inputs. In this thesis, the overarching objective is to show that we can prove these same desirable linear-like properties in a wide range of adaptive control problems without the convexity assumption: the main idea is to use multiple estimators and a switching algorithm. Indeed, we show that those properties arise in a surprisingly natural way. We first prove a general result that exponential stability and a convolution bound on the closed-loop behavior can be leveraged to show tolerance to a degree of time-variations and unmodelled dynamics, i.e. such closed-loop properties guarantee robustness. After reviewing the original Projection Algorithm and introducing the reader to our slightly revised version, we turn our attention to controller design, with a focus on a non-convex set of plant uncertainty. As a starting point, we first consider first-order plants incorporating a simple switching algorithm. We then extend the approach to a class of nonlinear plants (which have stable zero dynamics); we consider both cases of convex and non-convex sets of parameter uncertainty. Afterwards, we turn to possibly non-minimum phase LTI plants; first we consider the stabilization problem for which we have two convex sets of uncertainty; then, we turn to the problem of tracking the sum of a finite number of sinusoids of known frequencies subject to an unknown plant order and a general compact set of uncertainty.

Subjects/Keywords: adaptive control; switching adaptive control; exponential stability; robust adaptive control; control theory; projection algorithm; multi-model; Adaptive control systems; Control theory

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Shahab, M. T. (2020). A New Approach to Multi-Model Adaptive Control. (Thesis). University of Waterloo. Retrieved from http://hdl.handle.net/10012/15766

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Shahab, Mohamad T. “A New Approach to Multi-Model Adaptive Control.” 2020. Thesis, University of Waterloo. Accessed January 22, 2021. http://hdl.handle.net/10012/15766.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Shahab, Mohamad T. “A New Approach to Multi-Model Adaptive Control.” 2020. Web. 22 Jan 2021.

Vancouver:

Shahab MT. A New Approach to Multi-Model Adaptive Control. [Internet] [Thesis]. University of Waterloo; 2020. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/10012/15766.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Shahab MT. A New Approach to Multi-Model Adaptive Control. [Thesis]. University of Waterloo; 2020. Available from: http://hdl.handle.net/10012/15766

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

26. Morad, Farhad. Non-linear Curve Fitting.

Degree: Culture and Communication, 2019, Mälardalen University

URL: http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-43600

►

The work done in this thesis is to examine various methods for curve fitting. Linear least squares and non-linear least squares will be described… (more)

Subjects/Keywords: Curve Fitting; Power-exponential function; Gauss-Newton algorithm; Levenberg-Marquardt algorithm; Linear and non-linear curve fitting; Kurvanpassning; Potens-exponential funktion; Gauss-Newton-algoritm; Levenberg-Marquardt-algoritm; Linjär och ickelinjär kurvanpassning; Other Mathematics; Annan matematik

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Morad, F. (2019). Non-linear Curve Fitting. (Thesis). Mälardalen University. Retrieved from http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-43600

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Morad, Farhad. “Non-linear Curve Fitting.” 2019. Thesis, Mälardalen University. Accessed January 22, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-43600.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Morad, Farhad. “Non-linear Curve Fitting.” 2019. Web. 22 Jan 2021.

Vancouver:

Morad F. Non-linear Curve Fitting. [Internet] [Thesis]. Mälardalen University; 2019. [cited 2021 Jan 22]. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-43600.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Morad F. Non-linear Curve Fitting. [Thesis]. Mälardalen University; 2019. Available from: http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-43600

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

27. Momège, Benjamin. Autour de la connexité dans les graphes avec conflits : On the Connectivity of Graphs with Conflicts.

Degree: Docteur es, Informatique, 2015, Université Blaise-Pascale, Clermont-Ferrand II

URL: http://www.theses.fr/2015CLF22588

►

Nous nous intéresserons aux graphes avec conflits (un conflit est une paire d’arêtes ne pouvant pas simultanément faire partie d’un même sous-graphe), dans lesquels nous… (more)

Subjects/Keywords: Graphe; Conflit; Transition Interdite; Connexité; Chemin; Parcours; Arbre; Condition Hamiltonienne; Algorithme Exact; \mathcal{N P}-Complétude; Graph; Conflict; Forbidden Transition; Connectivity; Path; Walk; Tree; Hamiltonian Condition; Exact Algorithm; \mathcal{N P}-Completeness

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Momège, B. (2015). Autour de la connexité dans les graphes avec conflits : On the Connectivity of Graphs with Conflicts. (Doctoral Dissertation). Université Blaise-Pascale, Clermont-Ferrand II. Retrieved from http://www.theses.fr/2015CLF22588

Chicago Manual of Style (16^th Edition):

Momège, Benjamin. “Autour de la connexité dans les graphes avec conflits : On the Connectivity of Graphs with Conflicts.” 2015. Doctoral Dissertation, Université Blaise-Pascale, Clermont-Ferrand II. Accessed January 22, 2021. http://www.theses.fr/2015CLF22588.

MLA Handbook (7^th Edition):

Momège, Benjamin. “Autour de la connexité dans les graphes avec conflits : On the Connectivity of Graphs with Conflicts.” 2015. Web. 22 Jan 2021.

Vancouver:

Momège B. Autour de la connexité dans les graphes avec conflits : On the Connectivity of Graphs with Conflicts. [Internet] [Doctoral dissertation]. Université Blaise-Pascale, Clermont-Ferrand II; 2015. [cited 2021 Jan 22]. Available from: http://www.theses.fr/2015CLF22588.

Council of Science Editors:

Momège B. Autour de la connexité dans les graphes avec conflits : On the Connectivity of Graphs with Conflicts. [Doctoral Dissertation]. Université Blaise-Pascale, Clermont-Ferrand II; 2015. Available from: http://www.theses.fr/2015CLF22588

University of Georgia

28. ZHOU, JIN. Bifurcating time series models for cell lineage data.

Degree: 2014, University of Georgia

URL: http://hdl.handle.net/10724/21737

► This dissertation studies bifurcating time series models. Our motivation comes from cell lineage data, in which each individual in a generation gives rise to two… (more)

Subjects/Keywords: Cell Lineage Data; Tree-Indexed Data; Bifurcating Autoregressive Models; Least Squares Estimation; Maximum Likelihood Estimation; Quasilikelihood Estimation; Exponential Innovations; Exact Distribution; Limit Distribution; Asymptotic Property; Non-Gaussian Models; Integer-valued Autoregression.

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

ZHOU, J. (2014). Bifurcating time series models for cell lineage data. (Thesis). University of Georgia. Retrieved from http://hdl.handle.net/10724/21737

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

ZHOU, JIN. “Bifurcating time series models for cell lineage data.” 2014. Thesis, University of Georgia. Accessed January 22, 2021. http://hdl.handle.net/10724/21737.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

ZHOU, JIN. “Bifurcating time series models for cell lineage data.” 2014. Web. 22 Jan 2021.

Vancouver:

ZHOU J. Bifurcating time series models for cell lineage data. [Internet] [Thesis]. University of Georgia; 2014. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/10724/21737.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

ZHOU J. Bifurcating time series models for cell lineage data. [Thesis]. University of Georgia; 2014. Available from: http://hdl.handle.net/10724/21737

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

29. Al Kharboutly, Mira. Résolution d’un problème quadratique non convexe avec contraintes mixtes par les techniques de l’optimisation D.C. : Solving a binary quadratic problem with mixed constraints by D.C. optimization techniques.

Degree: Docteur es, Mathématiques appliquées, 2018, Normandie

URL: http://www.theses.fr/2018NORMLH06

►

Notre objectif dans cette thèse est de résoudre un problème quadratique binaire sous contraintes mixtes par les techniques d'optimisation DC. Puisque l'optimisation DC a prouvé… (more)

▼

Notre objectif dans cette thèse est de résoudre un problème quadratique binaire sous contraintes mixtes par les techniques d'optimisation DC. Puisque l'optimisation DC a prouvé son efficacité pour résoudre des problèmes de grandes tailles dans différents domaines, nous avons décidé d'appliquer cette approche d'optimisation pour résoudre ce problème. La partie la plus importante de l'optimisation DC est le choix d'une décomposition adéquate qui facilite la détermination et accélère la convergence de deux suites construites. La première suite converge vers la solution optimale du problème primal et la seconde converge vers la solution optimale du problème dual. Dans cette thèse, nous proposons deux décompositions DC efficaces et simples à manipuler. L'application de l'algorithme DC (DCA) nous conduit à résoudre à chaque itération un problème quadratique convexe avec des contraintes mixtes, linéaires et quadratiques. Pour cela, il faut trouver une méthode efficace et rapide pour résoudre ce dernier problème à chaque itération. Pour cela, nous appliquons trois méthodes différentes: la méthode de Newton, la programmation semi-définie positive et la méthode de points intérieurs. Nous présentons les résultats numériques comparatifs sur les mêmes repères de ces trois approches pour justifier notre choix de la méthode la plus rapide pour résoudre efficacement ce problème.

Our objective in this work is to solve a binary quadratic problem under mixed constraints by the techniques of DC optimization. As DC optimization has proved its efficiency to solve large-scale problems in different domains, we decided to apply this optimization approach to solve this problem. The most important part of D.C. optimization is the choice of an adequate decomposition that facilitates determination and speeds convergence of two constructed suites where the first converges to the optimal solution of the primal problem and the second converges to the optimal solution of the dual problem. In this work, we propose two efficient decompositions and simple to manipulate. The application of the DC Algorithm (DCA) leads us to solve at each iteration a convex quadratic problem with mixed, linear and quadratic constraints. For it, we must find an efficient and fast method to solve this last problem at each iteration. To do this, we apply three different methods: the Newton method, the semidefinite programing and interior point method. We present the comparative numerical results on the same benchmarks of these three approaches to justify our choice of the fastest method to effectively solve this problem.

Advisors/Committee Members: Yassine, Adnan (thesis director).

Subjects/Keywords: Optimisation DC; Algorithmes DC (DCA); Programmation semi-définie positive; Pénalité exacte; DC optimization; DC algorithm (DCA); Exact penalty; Quadratic programming; Nonsmooth Newton method; Semidefinite programming; Interior points methods

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Al Kharboutly, M. (2018). Résolution d’un problème quadratique non convexe avec contraintes mixtes par les techniques de l’optimisation D.C. : Solving a binary quadratic problem with mixed constraints by D.C. optimization techniques. (Doctoral Dissertation). Normandie. Retrieved from http://www.theses.fr/2018NORMLH06

Chicago Manual of Style (16^th Edition):

Al Kharboutly, Mira. “Résolution d’un problème quadratique non convexe avec contraintes mixtes par les techniques de l’optimisation D.C. : Solving a binary quadratic problem with mixed constraints by D.C. optimization techniques.” 2018. Doctoral Dissertation, Normandie. Accessed January 22, 2021. http://www.theses.fr/2018NORMLH06.

MLA Handbook (7^th Edition):

Al Kharboutly, Mira. “Résolution d’un problème quadratique non convexe avec contraintes mixtes par les techniques de l’optimisation D.C. : Solving a binary quadratic problem with mixed constraints by D.C. optimization techniques.” 2018. Web. 22 Jan 2021.

Vancouver:

Al Kharboutly M. Résolution d’un problème quadratique non convexe avec contraintes mixtes par les techniques de l’optimisation D.C. : Solving a binary quadratic problem with mixed constraints by D.C. optimization techniques. [Internet] [Doctoral dissertation]. Normandie; 2018. [cited 2021 Jan 22]. Available from: http://www.theses.fr/2018NORMLH06.

Council of Science Editors:

Al Kharboutly M. Résolution d’un problème quadratique non convexe avec contraintes mixtes par les techniques de l’optimisation D.C. : Solving a binary quadratic problem with mixed constraints by D.C. optimization techniques. [Doctoral Dissertation]. Normandie; 2018. Available from: http://www.theses.fr/2018NORMLH06

Kyoto University / 京都大学

30. Bhusiri, Narath. EXACT SOLUTIONS FOR VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH FULL SOFT TIME WINDOWS USING COLUMN GENERATION AND LABELING ALGORITHMS : 列生成法およびラべリングアルゴリズムを用いたフルソフトタイムウィンドウ付配車配送計画の厳密解.

Degree: 博士(工学), 2013, Kyoto University / 京都大学

URL: http://hdl.handle.net/2433/180484 ; http://dx.doi.org/10.14989/doctor.k17871

新制・課程博士

甲第17871号

工博第3780号

Subjects/Keywords: Freight transport; routing problem; exact solutions; column generation; labeling algorithm

Record Details Similar Records Cite « Share

❌

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

APA (6^th Edition):

Bhusiri, N. (2013). EXACT SOLUTIONS FOR VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH FULL SOFT TIME WINDOWS USING COLUMN GENERATION AND LABELING ALGORITHMS : 列生成法およびラべリングアルゴリズムを用いたフルソフトタイムウィンドウ付配車配送計画の厳密解. (Thesis). Kyoto University / 京都大学. Retrieved from http://hdl.handle.net/2433/180484 ; http://dx.doi.org/10.14989/doctor.k17871

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Chicago Manual of Style (16^th Edition):

Bhusiri, Narath. “EXACT SOLUTIONS FOR VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH FULL SOFT TIME WINDOWS USING COLUMN GENERATION AND LABELING ALGORITHMS : 列生成法およびラべリングアルゴリズムを用いたフルソフトタイムウィンドウ付配車配送計画の厳密解.” 2013. Thesis, Kyoto University / 京都大学. Accessed January 22, 2021. http://hdl.handle.net/2433/180484 ; http://dx.doi.org/10.14989/doctor.k17871.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

MLA Handbook (7^th Edition):

Bhusiri, Narath. “EXACT SOLUTIONS FOR VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH FULL SOFT TIME WINDOWS USING COLUMN GENERATION AND LABELING ALGORITHMS : 列生成法およびラべリングアルゴリズムを用いたフルソフトタイムウィンドウ付配車配送計画の厳密解.” 2013. Web. 22 Jan 2021.

Vancouver:

Bhusiri N. EXACT SOLUTIONS FOR VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH FULL SOFT TIME WINDOWS USING COLUMN GENERATION AND LABELING ALGORITHMS : 列生成法およびラべリングアルゴリズムを用いたフルソフトタイムウィンドウ付配車配送計画の厳密解. [Internet] [Thesis]. Kyoto University / 京都大学; 2013. [cited 2021 Jan 22]. Available from: http://hdl.handle.net/2433/180484 ; http://dx.doi.org/10.14989/doctor.k17871.

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Council of Science Editors:

Bhusiri N. EXACT SOLUTIONS FOR VEHICLE ROUTING AND SCHEDULING PROBLEMS WITH FULL SOFT TIME WINDOWS USING COLUMN GENERATION AND LABELING ALGORITHMS : 列生成法およびラべリングアルゴリズムを用いたフルソフトタイムウィンドウ付配車配送計画の厳密解. [Thesis]. Kyoto University / 京都大学; 2013. Available from: http://hdl.handle.net/2433/180484 ; http://dx.doi.org/10.14989/doctor.k17871

Note: this citation may be lacking information needed for this citation format:
Not specified: Masters Thesis or Doctoral Dissertation

Open Access Theses and Dissertations