Advanced

Studies in Efficient Discrete Algorithms

SLEDNEU, DZMITRY LU (2016)
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... (More)
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. (Less)
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
supervisor
opponent
  • Professor Czumaj, Artur, University of Warwick, Coventry, United Kingdom
organization
publishing date
type
Thesis
publication status
published
subject
keywords
Algorithms, Approximation algorithms, Graphs
pages
90 pages
publisher
Lund University, Faculty of Science, Centre for Mathematical Sciences, Mathematics
defense location
MA1, Annexet, Sölvegatan 20, Lund
defense date
2016-09-30 13:00
ISBN
978-91-7623-866-0
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
2016-09-19 08:45:20
@phdthesis{7f26796b-c60f-408e-ab52-9b8f2ed87b9d,
  abstract     = {This thesis consists of five papers within the design and analysis of efficient algorithms.<br/>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.<br/>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.<br/>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.<br/>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.<br/>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},
  isbn         = {978-91-7623-866-0},
  keyword      = {Algorithms,Approximation algorithms,Graphs},
  language     = {eng},
  pages        = {90},
  publisher    = {Lund University, Faculty of Science, Centre for Mathematical Sciences, Mathematics},
  school       = {Lund University},
  title        = {Studies in Efficient Discrete Algorithms},
  year         = {2016},
}