In this paper, a linear-time algorithm is developed for the minmax-regret version of the continuous unbounded knapsack problem with n items and uncertain objective function coefficients, where the interval estimates f...
详细信息
In this paper, a linear-time algorithm is developed for the minmax-regret version of the continuous unbounded knapsack problem with n items and uncertain objective function coefficients, where the interval estimates for these coefficients are known. This improves the previously known bound of O(n log(n)) time for this optimization problem. (c) 2004 Elsevier B.V. All rights reserved.
In this paper, we present an efficient algorithm for minimizing an Mp-convex function under a color -induced budget constraint. The algorithm extends the algorithms by Gabow and Tarjan for finding a minimum-weight bas...
详细信息
In this paper, we present an efficient algorithm for minimizing an Mp-convex function under a color -induced budget constraint. The algorithm extends the algorithms by Gabow and Tarjan for finding a minimum-weight base of a matroid and by Gottschalk et al. for minimizing a separable discrete convex function on a polymatroid under a color-induced budget constraint. It can also be recognized as an extension of a greedy algorithm for unconstrained Mp-convex function minimization by Murota and Shioura.(c) 2023 Elsevier B.V. All rights reserved.
In this paper, we investigate the maximum traveling salesman problem (Max-TSP) on quasi-banded matrices. A matrix is quasi-banded with multiplier alpha if all its elements contained within a band of several diagonals ...
详细信息
In this paper, we investigate the maximum traveling salesman problem (Max-TSP) on quasi-banded matrices. A matrix is quasi-banded with multiplier alpha if all its elements contained within a band of several diagonals above and below the principal diagonal are non-zero, and any element in the band is at least alpha times larger than the maximal element outside the band. We investigate the properties of the Max-TSP on the quasi-banded matrices, prove that it is strongly NP-hard and derive a linear-time approximation algorithm with a guaranteed performance. (C) 2002 Elsevier Science B.V. All rights reserved.
The k-linkage problem is as follows: given a digraph D = (V, A) and a collection of k terminal pairs (s(1), t(1)),..., (s(k), t(k)) such that all these vertices are distinct;decide whether D has a collection of vertex...
详细信息
The k-linkage problem is as follows: given a digraph D = (V, A) and a collection of k terminal pairs (s(1), t(1)),..., (s(k), t(k)) such that all these vertices are distinct;decide whether D has a collection of vertex disjoint paths P-1, P-2,..., P-k such that P-i is from s(i) to t(i) for i is an element of [k]. A digraph is k-linked if it has a k-linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k-linkage problem is NP-complete already for k = 2 [11] and there exists no function f (k) such that every f (k)-strong digraph has a k-linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k-linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k-linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi-transitive digraphs and directed cographs. We also prove that the necessary condition of being (2k-1)-strong is also sufficient for round-decomposable digraphs to be k-linked, obtaining thus a best possible bound that improves a previous one of (3k-2). Finally we settle a conjecture from [3] by proving that every 5-strong locally semicomplete digraph is 2-linked. This bound is also best possible (already for tournaments) [1]. (C) 2016 Wiley Periodicals, Inc.
In the MINIMAL PERMUTATION COMPLETION problem, one is given an arbitrary graph G = (V, E) and the aim is to find a permutation super-graph H = (V, F) defined on the same vertex set and such that F superset of E is inc...
详细信息
In the MINIMAL PERMUTATION COMPLETION problem, one is given an arbitrary graph G = (V, E) and the aim is to find a permutation super-graph H = (V, F) defined on the same vertex set and such that F superset of E is inclusion-minimal among all possibilities. The graph H is then called a minimal permutation completion of G. We provide an O(n(2)) incremental algorithm computing such a minimal permutation completion. To the best of our knowledge, this result leads to the first polynomial algorithm for this problem. A preliminary extended abstract of this paper appeared as [4] in the Proceedings of WG 2015. (C) 2018 Elsevier B.V. All rights reserved.
作者：
KRIVANEK, MKKI MFF
Charles Univ. Malostranske nam. 25 118 00 Praha 1 Czechoslovakia
Partitioning of graphs has many practical applications, namely in cluster analysis and in the automated design of very large-scale integration circuits. Using one-to-one correspondence between ultrametric partitions ...
详细信息
Partitioning of graphs has many practical applications, namely in cluster analysis and in the automated design of very large-scale integration circuits. Using one-to-one correspondence between ultrametric partitions of a weighted complete graph K(w) on a finite set X and ultrametrics on X, the computational complexity of the approximation of the given weight function w by means of an ultrametric u is analyzed and systematized. As a main result, a polynomial algorithm that solves the problem under some minimum-maximum criterion is formulated. This new polynomial procedure of hierarchical clustering was used successfully in the design of multichip layouts.
We present a polynomial algorithm for a family of single-machine scheduling problems with mixed variable job processing times, -partite job precedence constraints and the maximum cost criterion, provided that job proc...
详细信息
We present a polynomial algorithm for a family of single-machine scheduling problems with mixed variable job processing times, -partite job precedence constraints and the maximum cost criterion, provided that job processing times satisfy certain assumptions.
For minmax regret versions of some basic resource allocation problems with linear cost functions and uncertain coefficients (interval-data case), we present efficient (polynomial and pseudopolynomial) algorithms. As a...
详细信息
For minmax regret versions of some basic resource allocation problems with linear cost functions and uncertain coefficients (interval-data case), we present efficient (polynomial and pseudopolynomial) algorithms. As a by-product, we obtain an 0(n log n) algorithm for the interval data minmax regret continuous knapsack problem. (C) 2003 Elsevier B.V. All rights reserved.
We revisit the problem of finding a 1-restricted simple 2-matching of maximum cardinality. Recall that, given an undirected graph G = (V, E), a simple 2-matching is a subset M subset of E of edges such that each node ...
详细信息
We revisit the problem of finding a 1-restricted simple 2-matching of maximum cardinality. Recall that, given an undirected graph G = (V, E), a simple 2-matching is a subset M subset of E of edges such that each node in V is incident to at most two edges inM. Clearly, each suchM decomposes into a node-disjoint collection of paths and circuits. M is called 1-restricted if it contains no isolated edges (i.e. paths of length one). A combinatorial polynomial algorithm for finding such M of maximum cardinality and also a min-max relation were devised by Hartvigsen. It was shown that finding such M amounts to computing a (not necessarily 1-restricted) simple 2-matching M-0 of maximum cardinality and subsequently altering it into M of the same cardinality so as to minimize the number of isolated edges. While the first phase (which computes M-0) runs in O (E root V) time, the second one (which turnsM(0) intoM) requires O(VE) time. In this paper we apply the general blocking augmentation approach (initially introduced, e.g., for bipartite matchings by Hopcroft and Karp, and also by Dinic) and present a novel algorithm that reduces the time needed for the second phase to O (E root V) thus completely closing the gap between 1-restricted and unrestricted cases.
A rational number is dyadic if it has a finite binary representation p/2k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepacka...
详细信息
A rational number is dyadic if it has a finite binary representation p/2k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p/2<^>k$$\end{document}, where p is an integer and k is a nonnegative integer. Dyadic rationals are important for numerical computations because they have an exact representation in floating-point arithmetic on a computer. A vector is dyadic if all its entries are dyadic rationals. We study the problem of finding a dyadic optimal solution to a linear program, if one exists. We show how to solve dyadic linear programs in polynomial time. We give bounds on the size of the support of a solution as well as on the size of the denominators. We identify properties that make the solution of dyadic linear programs possible: closure under addition and negation, and density, and we extend the algorithmic framework beyond the dyadic case.
暂无评论