Studies in Efficient Discrete Algorithms

Abstract

This thesis consists of five papers within the design and analysis of efficient algorithms.
In the first paper, we consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. We develop a combinatorial randomized algorithm that runs in subcubic time for a special class of graphs.
In the second paper, we present a polynomial-time dynamic programming algorithm for optimal partitions of a complete edge-weighted graph, where the edges are weighted by the length of the unique shortest path connecting those vertices in the a priori given tree (shortest path metric induced by a tree). Our result resolves, in particular, the complexity status of the optimal partition problems in one-dimensional geometric (Euclidean) setting.
In the third paper, we study the NP-hard problem of partitioning an orthogonal polyhedron P into a minimum number of 3D rectangles. We present an approximation algorithm with the approximation ratio 4 for the special case of the problem in which P is a so-called 3D histogram. We then apply it to compute the exact arithmetic matrix product of two matrices with non-negative integer entries. The computation is time-efficient if the 3D histograms induced by the input matrices can be partitioned into relatively few 3D rectangles.
In the fourth paper, we present the first quasi-polynomial approximation schemes for the base of the number of triangulations of a planar point set and the base of the number of crossing-free spanning trees on a planar point set, respectively.
In the fifth paper, we study the complexity of detecting monomials with special properties in the sum-product expansion of a polynomial represented by an arithmetic circuit of size polynomial in the number of input variables and using only multiplication and addition. We present a fixed-parameter tractable algorithms for the detection of monomial having at least k distinct variables, parametrized with respect to k. Furthermore, we derive several hardness results on the detection of monomials with such properties within exact, parametrized and approximation complexity.

Abstract (Swedish)

This thesis consists of five papers within the design and analysis of efficient algorithms.
In the first paper, we consider the problem of computing all-pairs shortest paths in a directed graph with real weights assigned to vertices. We develop a combinatorial randomized algorithm that runs in subcubic time for a special class of graphs.
In the second paper, we present a polynomial-time dynamic programming algorithm for optimal partitions of a complete edge-weighted graph, where the edges are weighted by the length of the unique shortest path connecting those vertices in the a priori given tree (shortest path metric induced by a tree). Our result resolves, in particular, the complexity status of the optimal partition problems in one-dimensional geometric (Euclidean) setting.
In the third paper, we study the NP-hard problem of partitioning an orthogonal polyhedron P into a minimum number of 3D rectangles. We present an approximation algorithm with the approximation ratio 4 for the special case of the problem in which P is a so-called 3D histogram. We then apply it to compute the exact arithmetic matrix product of two matrices with non-negative integer entries. The computation is time-efficient if the 3D histograms induced by the input matrices can be partitioned into relatively few 3D rectangles.
In the fourth paper, we present the first quasi-polynomial approximation schemes for the base of the number of triangulations of a planar point set and the base of the number of crossing-free spanning trees on a planar point set, respectively.
In the fifth paper, we study the complexity of detecting monomials with special properties in the sum-product expansion of a polynomial represented by an arithmetic circuit of size polynomial in the number of input variables and using only multiplication and addition. We present a fixed-parameter tractable algorithms for the detection of monomial having at least k distinct variables, parametrized with respect to k. Furthermore, we derive several hardness results on the detection of monomials with such properties within exact, parametrized and approximation complexity.

• author: SLEDNEU, DZMITRY
• supervisor: Andrzej Lingas
• opponent: Professor Czumaj, Artur, University of Warwick, Coventry, United Kingdom
• organization: Mathematics (Faculty of Sciences)
• publishing date: 2016-08
• type: Thesis
• publication status: published
• subject: Computer Science; Discrete Mathematics
• keywords: Algorithms, Approximation algorithms, Graphs
• pages: 90 pages
• defense location: MA1, Annexet, Sölvegatan 20, Lund
• defense date: 2016-09-30 13:00:00
• ISBN: 978-91-7623-866-0
• ISBN: 978-91-7623-867-7
• language: English
• LU publication?: yes
• id: 7f26796b-c60f-408e-ab52-9b8f2ed87b9d
• date added to LUP: 2016-09-04 13:27:35
• date last changed: 2024-02-13 15:13:16