On the connectivity interdiction problem, the geometry of data structures and Eulerian circuits

Thumbnail Image
Files
isbn9789526418230.pdf (1.84 MB)
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (article-based) | Defence date: 2024-05-17
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Author
Date
2024
Department
Tietotekniikan laitos
Department of Computer Science
Major/Subject
Mcode
Degree programme
Language
en
Pages
119 + app. 83
Series
Aalto University publication series DOCTORAL THESES, 103/2024
Abstract
Over the last century and since the introduction practical computers, the study of algorithms for optimization problems has become one of the main areas in theoretical computer science. Computer algorithms are nowadays an ubiquitous tool in optimization applications like food production, voting systems, route scheduling, transportation, protein synthesis and drug delivery. However, the progress of these area has faced big theoretical and practical challenges, like the lack of computing resources, the increasing volume of data in big networks and theoretical and structural barriers like NP-hardness. In order to by-pass some of the theoretical barriers, this thesis explores several graph and optimization problems through approximation algorithms, data structures, extremal combinatorics and geometry, establishing new state-of-the-art theoretical results in the following problems: The Connectivity Interdiction Problem. For a given weighted undirected connected graph G and integer k, this problem asks to find the optimal set of edges of cost at most k such that the min-cut of the graph G is minimzed after the deletion of these edges from G. We establish new graph-theoretic structural results relating this problem to a variant of graph cut problems called the Normalized Min-cut problem, which allows us to design new exact and approximate algorithms for the unit-cost case establishing a trade-off between running time and solution quality. Furthermore, we answer an open question from Zenklusen [Zenklusen 2014] by showing that this problem admits an FPTAS (Fully Polynomial-Time Approximation Scheme). The Geometry of the Minimum-cost Online Binary Search Tree Problem. In this problem, we want to find the optimum cost online self-adjusting binary search tree which searches any sequence of keys in the tree, a problem related to the Dynamic Optimality Conjecture [Sleator & Tarjan 1985]. We study the Greedy algorithm as one of the two main candidates for this conjecture in a geometric setting, using the theory of forbidden submatrices and introducing a novel matrix decomposition technique. This allows us to improve known upper-bounds in special cases like the pre-order traversal, deque, split and k-increasing sequences and operations, and to settle completely the conjecture for post-order traversal sequences. Furthermore, we show the NP-hardness of a newly introduced generalization of this problem and efficient approximation algorithms for its general case and special cases. Unique Eulerian Circuits. We study the graph theoretical characterization of directed connected graphs with a unique Eulerian circuit. We show a new characterization of these graphs in terms of cut nodes and degrees of a graph, allowing a simple and efficient algorithm to determine if a given graph has a unique Eulerian circuit. Most importantly, this allows us to characterize and develop efficient algorithms to compute the so called maximal safe solutions for the Eulerian Circuit Problem, a concept arising in bioinformatics applications like genome assembly.
Description
Supervising professor
Chalermsook, Parinya, Prof., Aalto University, Department of Computer Science, Finland
Keywords
algorithms, min-cut, FPTAS, eulerian circuits, data structures, approximation
Other note
Parts
  • [Publication 1]: Chien-Chung Huang, Nidia Obscura Acosta, Sorrachai Yingchareonthawornchai. An FPTAS for Connectivity Interdiction. Submitted to a conference, October 2023.
  • [Publication 2]: Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Nidia Obscura Acosta, Akash Pareek, Sorrachai Yingchareonthawornchai. Improved Pattern-Avoidance Bounds for Greedy BSTs via Matrix Decomposition. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Pages 509 - 534, January 2023.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202311016740
    DOI: 10.1137/1.9781611977554.ch22 View at publisher
  • [Publication 3]: Antonios Antoniadis, Margarita Capretto, Parinya Chalermsook, Christoph Damerius, Peter Kling, Lukas Nölke, Nidia Obscura Acosta, Joachim Spoerhase. On Minimum Generalized Manhattan Connections. In Lubiw, A., Salavatipour, M., He, M. (eds) Algorithms and Data Structures. WADS 2021. Lecture Notes in Computer Science, vol 12808, pages 85-100, July 2021.
    DOI: 10.1007/978-3-030-83508-8_7 View at publisher
  • [Publication 4]: Nidia Obscura Acosta, Alexandru I. Tomescu. Simplicity in Eulerian circuits: Uniqueness and safety. Information Processing Letters, Volume 183, 106421, January 2024.
    Full text in Acris/Aaltodoc: https://urn.fi/URN:NBN:fi:aalto-202308014657
    DOI: 10.1016/j.ipl.2023.106421 View at publisher
Citation
Permanent link to this item
https://urn.fi/URN:ISBN:978-952-64-1823-0
Collections
[diss] Perustieteiden korkeakoulu / SCI