Studies in Efficient Discrete Algorithms
(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 allpairs 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 polynomialtime dynamic programming algorithm for optimal partitions of a complete edgeweighted 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 allpairs 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 polynomialtime dynamic programming algorithm for optimal partitions of a complete edgeweighted 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 onedimensional geometric (Euclidean) setting.
In the third paper, we study the NPhard 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 socalled 3D histogram. We then apply it to compute the exact arithmetic matrix product of two matrices with nonnegative integer entries. The computation is timeefficient 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 quasipolynomial approximation schemes for the base of the number of triangulations of a planar point set and the base of the number of crossingfree spanning trees on a planar point set, respectively.
In the fifth paper, we study the complexity of detecting monomials with special properties in the sumproduct 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 fixedparameter 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 allpairs 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 polynomialtime dynamic programming algorithm for optimal partitions of a complete edgeweighted 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 allpairs 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 polynomialtime dynamic programming algorithm for optimal partitions of a complete edgeweighted 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 onedimensional geometric (Euclidean) setting.
In the third paper, we study the NPhard 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 socalled 3D histogram. We then apply it to compute the exact arithmetic matrix product of two matrices with nonnegative integer entries. The computation is timeefficient 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 quasipolynomial approximation schemes for the base of the number of triangulations of a planar point set and the base of the number of crossingfree spanning trees on a planar point set, respectively.
In the fifth paper, we study the complexity of detecting monomials with special properties in the sumproduct 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 fixedparameter 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:
http://lup.lub.lu.se/record/7f26796bc60f408eab529b8f2ed87b9d
 author
 SLEDNEU, DZMITRY ^{LU}
 supervisor
 opponent

 Professor Czumaj, Artur, University of Warwick, Coventry, United Kingdom
 organization
 publishing date
 201608
 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
 20160930 13:00
 ISBN
 9789176238660
 language
 English
 LU publication?
 yes
 id
 7f26796bc60f408eab529b8f2ed87b9d
 date added to LUP
 20160904 13:27:35
 date last changed
 20160919 08:45:20
@phdthesis{7f26796bc60f408eab529b8f2ed87b9d, 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 allpairs 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 polynomialtime dynamic programming algorithm for optimal partitions of a complete edgeweighted 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 onedimensional geometric (Euclidean) setting.<br/>In the third paper, we study the NPhard 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 socalled 3D histogram. We then apply it to compute the exact arithmetic matrix product of two matrices with nonnegative integer entries. The computation is timeefficient 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 quasipolynomial approximation schemes for the base of the number of triangulations of a planar point set and the base of the number of crossingfree 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 sumproduct 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 fixedparameter 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 = {9789176238660}, 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}, }