A {0, 1}-matrix M has the consecutive-retrieval property if there exists a tree T such that the vertices of T are indexed on the rows of M and the columns of M are the incidence vectors of the vertex sets of paths of ...
详细信息
A {0, 1}-matrix M has the consecutive-retrieval property if there exists a tree T such that the vertices of T are indexed on the rows of M and the columns of M are the incidence vectors of the vertex sets of paths of T. If such a T exists, then T is a realization for M. In this paper, an O(r2c) algorithm is presented to determine whether a given standard, r x c matrix has the consecutive-retrieval property and, if so, to construct a realization.
Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomialtime by solving a polynomial number of linear programs of polynomial size. We...
详细信息
Answering a question of Haugland, we show that the pooling problem with one pool and a bounded number of inputs can be solved in polynomialtime by solving a polynomial number of linear programs of polynomial size. We also give an overview of known complexity results and remaining open problems to further characterize the border between (strongly) NP-hard and polynomially solvable cases of the pooling problem.
Several countries successfully use centralized matching schemes for school or higher education assignment, or for entry-level labour markets. In this paper we explore the computational aspects of a. possible similar s...
详细信息
Several countries successfully use centralized matching schemes for school or higher education assignment, or for entry-level labour markets. In this paper we explore the computational aspects of a. possible similar scheme for assigning teachers to schools. Our model, is motivated by a particular characteristic of the education system in many countries where each teacher specializes in two subjects. We seek stable matchings, which ensure that no teacher and school have the incentive to deviate from their assignments. Indeed we propose two stability definitions depending on the precise format of schools' preferences. If the schools' ranking of applicants is independent of their subjects of specialism, we show that the problem of deciding whether a stable matching exists is NP-complete, even if there are only three subjects, unless there are master lists of applicants or of schools. By contrast, if the schools may order applicants differently in each of their specialization subjects, the problem of deciding whether a stable matching exists is NP-complete even in the presence of subject-specific master lists plus a master list of schools. Finally, we prove a strong inapproximability result for the problem of finding a matching with the minimum number of blocking pairs with respect to both stability definitions. (C) 2016 The Author(s). Published by Elsevier B.V.
The problem of recovering the structure of crystalline materials from their discrete X-rays is of fundamental interest in many practical applications. An important special case concerns determining the position of ato...
详细信息
The problem of recovering the structure of crystalline materials from their discrete X-rays is of fundamental interest in many practical applications. An important special case concerns determining the position of atoms of several different types in the integer lattice, given the number of each type lying on each line parallel to some lattice directions. We show that the corresponding consistency problem is NP-complete for any two (or more) different (fixed) directions when six (or more) types of atoms are involved. (C) 2000 Elsevier Science B.V. All rights reserved.
This paper deals with the independent even factor problem. For odd-cycle-symmetric digraphs, in which each arc in any odd dicycle has the reverse arc, a min-max formula is established as a common generalization of the...
详细信息
This paper deals with the independent even factor problem. For odd-cycle-symmetric digraphs, in which each arc in any odd dicycle has the reverse arc, a min-max formula is established as a common generalization of the Tutte-Berge formula for matchings and the min-max formula of Edmonds [Submodular functions, matroids, and certain polyhedra, in Combinatorial Structures and Their Applications, R. Guy et al., eds., Gordon and Breach, New York, 1970, pp. 69-87] for matroid intersection. We devise a combinatorial efficient algorithm to find a maximum independent even factor in an odd-cycle-symmetric digraph accompanied by general matroids, which commonly extends two of the alternating-path-type algorithms, the even factor algorithm of Pap [Math. Program., 110 (2007), pp. 57-69], and the matroid intersection algorithms. This algorithm gives a proof of the min-max formula and contains a new operation on matroids, which corresponds to shrinking factor-critical components in the matching algorithm of Edmonds [Canad. J. Math., 17 (1965), pp. 449-467]. The running time of the algorithm is O(n(4)Q), where n is the number of vertices and Q is the time for an independence test. The algorithm also gives a common generalization of the Edmonds-Gallai decomposition for matchings and the principal partition for matroid intersection.
We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomialtime. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running...
详细信息
We study the design of fixed-parameter algorithms for problems already known to be solvable in polynomialtime. The main motivation is to get more efficient algorithms for problems with unattractive polynomial running times. Here, we focus on a fundamental graph problem: LONGEST PATH, that is, given an undirected graph, find a maximum-length path in G. LONGEST PATH is NP-hard in general but known to be solvable in O (n(4)) time on n-vertex interval graphs. We show how to solve LONGEST PATH ON INTERVAL GRAPHS, parameterized by vertex deletion number k to proper interval graphs, in 0 (k(9)n) time. Notably, LONGEST PATH is trivially solvable in linear time on proper interval graphs, and the parameter value k can be approximated up to a factor of 4 in linear time. From a more general perspective, we believe that using parameterized complexity analysis may enable a refined understanding of efficiency aspects for polynomial-time solvable problems similarly to what classical parameterized complexity analysis does for NP-hard problems. (C) 2017 Elsevier B.V. All rights reserved.
Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we s...
详细信息
Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if the rank of the covariance matrix is a fixed value, then there is an algorithm that solves sparse PCA to global optimality, whose running time is polynomial in the number of features. We also prove a similar result for the version of sparse PCA which requires the principal components to have disjoint supports.
This paper proposes two algorithms, namely Server-User Matching (SUM) algorithm and Extended Server-User Matching (ESUM) algorithm, for the distributed server allocation problem. The server allocation problem is to de...
详细信息
This paper proposes two algorithms, namely Server-User Matching (SUM) algorithm and Extended Server-User Matching (ESUM) algorithm, for the distributed server allocation problem. The server allocation problem is to determine the matching between servers and users to minimize the maximum delay, which is the maximum time to complete user synchronization. We analyze the computational time complexity. We prove that the SUM algorithm obtains the optimal solutions in polynomialtime for the special case that all server-server delay values are the same and constant. We provide the upper and lower bounds when the SUM algorithm is applied to the general server allocation problem. We show that the ES UM algorithm is a fixed-parameter tractable algorithm that can attain the optimal solution for the server allocation problem parameterized by the number of servers. Numerical results show that the computation time of ESUM follows the analyzed complexity while the ESUM algorithm outperforms the approach of integer linear programming solved by our examined solver.
The recognition of 3-colorable graphs is an NP-complete problem, while 2-colorable (i.e., bipartite) graphs can be recognized in polynomialtime. To make the complexity gap more precise, we study intermediate graph cl...
详细信息
The recognition of 3-colorable graphs is an NP-complete problem, while 2-colorable (i.e., bipartite) graphs can be recognized in polynomialtime. To make the complexity gap more precise, we study intermediate graph classes and respective problems. This note proposes a conjecture that separates difficult instances of the problem from polynomially solvable ones and proves the "polynomial" part of the conjecture. (c) 2005 Elsevier B.V. All rights reserved.
In a finite undirected graph G, a vertex v dominates itself and its neighbors. A vertex set D is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Ef...
详细信息
In a finite undirected graph G, a vertex v dominates itself and its neighbors. A vertex set D is an efficient dominating set (e.d.s. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Effiderit Domination (ED) problem, which asks for the existence of an e.d.s. in G, is well known to be NP-complete for graphs of maximum degree 3. We say that an e.d.s. D of G is k-bounded (k-b.e.d.s. for short) if the degree of every vertex in D is at most k in G. The task of the k-Bounded Weighted Efficient Domination (k-BWED) problem is to determine whether a given vertex-weighted graph G admits a k-b.e.d.s., and if so, to compute one of minimum weight. It easily follows from the NIA-completeness of ED for graphs of maximum degree 3 that the k-BWED problem is NP-complete for every k > 3, and clearly, the k-BWED problem is solvable in linear time for k < 1. In this note, we show that the 2-BWED problem is solvable in time 0(1V(G)1(11/(G)1+ IE(G)I)), thus obtaining a dichotomy of the complexity status of k-BWED over all k > 0. (C) 2018 Elsevier B.V. All rights reserved.
暂无评论