The computational complexity of dominating set problems for instances with bounded minors of constraint matrices
We consider boolean linear programming formulations of the vertex and edge dominating set problems and prove their polynomial-time solvability for classes of graphs with constraint matrices having bounded minors in the absolute value.
In this paper, we will show that the width of simplices defined by systems of linear inequalities can be computed in polynomial time if some minors of their constraint matrices are bounded. Additionally, we present some quasi-polynomial-time and polynomial-time algorithms to solve the integer linear optimization problem defined on simplices minus all their integer vertices assuming that some minors of the constraint matrices of the simplices are bounded.
In this paper, we present FPT algorithms for special cases of the shortest vector problem (SVP) and the integer linear programming problem (ILP), when matrices included in the problems’ formulations are near square. The main parameter is the maximal absolute value of rank minors of matrices included in the problem formulation. Additionally, we present FPT algorithms with respect to the same main parameter for the problems, when the matrices have no singular rank sub-matrices.
The notion of a tolerance of an element of a combinatorial optimization problem is often used for stability analysis of an optimal solution and it is a base for design branch-and-bound algorithms solving such problems. In this paper we show that for the weighted independent set problem on trees with n vertices all upper and lower tolerances related to this solution can be computed with O(n) time.
We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.
We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.
We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.