The k-sum optimization problem (KSOP) is the combinatorial problem of finding a solution such that the sum of the weights or the ii largest weighted elements of the solution is as small as possible. KSOP simultaneousl...
详细信息
The k-sum optimization problem (KSOP) is the combinatorial problem of finding a solution such that the sum of the weights or the ii largest weighted elements of the solution is as small as possible. KSOP simultaneously generalizes both bottleneck and minsum problems. We show that KSOP can be solved in polynomialtime whenever an associated minsum problem can be solved in polynomialtime. Further we show that if the minsum problem is solvable by a polynomialtime epsilon-approximation scheme then KSOP can also be solved by a polynomialtime epsilon-approximation scheme.
In this note we show that the stability number of a (4-pan, chair, K-1,K-4,P-5)-free graph which has no simplicial vertex is bounded by 3. This generalizes the case of (claw, P-5)-free graphs and leads to a very simpl...
详细信息
In this note we show that the stability number of a (4-pan, chair, K-1,K-4,P-5)-free graph which has no simplicial vertex is bounded by 3. This generalizes the case of (claw, P-5)-free graphs and leads to a very simple polynomial-time algorithm for determining the stability number of (claw, Ps)-free graphs and, more generally, of (4-pan,chair, K-1,K-4, P-5)-free graphs. (C) 1999 Elsevier Science B.V. All rights reserved.
A fundamental problem in parallel and distributed processing is the partial serialization that is imposed due to the need for mutually exclusive access to common resources. In this article, we investigate the problem ...
详细信息
A fundamental problem in parallel and distributed processing is the partial serialization that is imposed due to the need for mutually exclusive access to common resources. In this article, we investigate the problem of optimally scheduling (in terms of makespan) a set of jobs, where each job consists of the same number L of unit-duration tasks, and each task either accesses exclusively one resource from a given set of resources or accesses a fully shareable resource. We develop and establish the optimality of a fast polynomial-time algorithm to find a schedule with the shortest makespan for any number of jobs and for any number of resources for the case of L = 2. In the notation commonly used for job-shop scheduling problems, this result means that the problem J vertical bar d(ij) = 1, n(j) =2 vertical bar C-max ax is polynomially solvable, adding to the polynomial solutions known for the problems J2 vertical bar n(j) <= 2 vertical bar C-max and J2 vertical bar d(ij) = 1 vertical bar C-max (whereas other closely related versions such as J2 vertical bar n(j)<= 3 vertical bar C-max, J2 vertical bar d(ij) is an element of {1,2}C-max, J3 vertical bar d(ij) =1 vertical bar C-max, J3 vertical bar d(ij) =1 vertical bar and J vertical bar d(ij) =1, n(j) <= 3 vertical bar C-max are all known to be NP-complete). For the general case L > 2 (i.e., for the job-shop problem J vertical bar d(ij) =1, nj = L >2 vertical bar C-max) we present a competitive heuristic and provide experimental comparisons with other heuristic versions and, when possible, with the ideal integer linear programming formulation.
An efficient algorithm A with a guaranteed error estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman tours) of maximum weight in a complete weighted ...
详细信息
An efficient algorithm A with a guaranteed error estimate is presented for solving the problem of finding several edge-disjoint Hamiltonian circuits (traveling salesman tours) of maximum weight in a complete weighted undirected graph in a multidimensional Euclidean space a"e (k) . The time complexity of the algorithm is O(n (3)). The number of traveling salesman tours for which the algorithm is asymptotically optimal is established.
We study the problem of determining whether a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in genera...
详细信息
We study the problem of determining whether a graph G has an induced matching that dominates every edge of the graph, which is also known as efficient edge domination. This problem is known to be NP-complete in general graphs, but it can be solved in polynomialtime for graphs in some special classes, such as weakly chordal, P-7-free or claw-free graphs. In the present paper we extend the polynomial-time solvability of the problem from claw-free graphs to graphs without a skew star, where a skew star is a treewith exactly three vertices of degree 1 being of distance 1, 2, 3 from the only vertex of degree 3. (C) 2013 Elsevier B.V. All rights reserved.
An interior-point predictor-corrector algorithm for the P*(kappa)-matrix linear complementarity problem is proposed. The algorithm is an extension of Mizuno-Todd-Ye's predictor-corrector algorithm for linear progr...
详细信息
An interior-point predictor-corrector algorithm for the P*(kappa)-matrix linear complementarity problem is proposed. The algorithm is an extension of Mizuno-Todd-Ye's predictor-corrector algorithm for linear programming problem. The extended algorithm is quadratically convergent with iteration complexity O((kappa + 1)root nL). It is the first polynomially and quadratically convergent algorithm for a class of LCPs that are not necessarily monotone.
We present a path-following algorithm for the linear programming problem with a surprisingly simple and elegant proof of its polynomial behaviour. This is done both for the problem in standard form and for its dual pr...
详细信息
We present a path-following algorithm for the linear programming problem with a surprisingly simple and elegant proof of its polynomial behaviour. This is done both for the problem in standard form and for its dual problem. We also discuss some implementation strategies.
A theorem is proved on the structure of the group of isometries of a Hermitian map b: V X V -> W, where V and W are vector spaces over a finite field of odd order. Also a Las Vegas polynomial-time algorithm is pres...
详细信息
A theorem is proved on the structure of the group of isometries of a Hermitian map b: V X V -> W, where V and W are vector spaces over a finite field of odd order. Also a Las Vegas polynomial-time algorithm is presented which, given a Hermitian map, finds generators for, and determines the structure of its isometry group. The algorithm can be adapted to construct the intersection over a set of classical subgroups of GL(V), giving rise to the first polynomial-time solution of this old problem. The approach yields new algorithmic tools for algebras with involution, which in turn have applications to other computational problems of interest. Implementations of the various algorithms in the MAGMA system demonstrate their practicability.
A new algorithm is presented to compute the algebra of adjoints associated to a pair of forms on a common finite vector space. This algebra is used in several recent and ongoing projects to study central products, int...
详细信息
A new algorithm is presented to compute the algebra of adjoints associated to a pair of forms on a common finite vector space. This algebra is used in several recent and ongoing projects to study central products, intersections of classical groups, and automorphism groups. The implementation of the new algorithms in MAGMA greatly outperforms its predecessor and hence, in restricted yet important settings, increases the practicality of the various algorithms that use adjoint algebras. (C) 2011 Elsevier Inc. All rights reserved.
We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised ...
详细信息
We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised matching schemes that assign graduating medical students to their first hospital posts. In such a setting, weak stability is the most common solution concept, and it is known that weakly stable matchings can have different sizes. This motivates the problem of finding a maximum cardinality weakly stable matching, which is known to be NP-hard in general. We show that this problem is solvable in polynomialtime if each man's list is of length at most 2 (even for women's lists that are of unbounded length). However if each man's list is of length at most 3, we show that the problem becomes NP-hard (even if each women's list is of length at most 3) and not approximable within some delta > 1 (even if each woman's list is of length at most 4). (C) 2008 Elsevier B.V. All rights reserved.
暂无评论