185 research outputs found
Assignment Problems
No full textThis volume presents a comprehensive view of the huge area of the assignment problem, starting from the conceptual foundations laid down since the Twenties by the studies on matching problems, and examining in detail theoretical, algorithmic and practical developments of the various assignment problems. Although the covered area is wide, each of the ten chapters is essentially self contained, and the readers can easily follow a single chapter they are interested in, by encountering few pointers to the essential background given in previous parts
A general Hungarian method for the algebraic transportation problem
No full textAbstractIn this paper the algebraic transportation problem is introduced which covers besides the Hitchcock and the time transportation problem several other types of transportation problems of practical relevance. To solve this algebraic transportation problem admissible transformations are considered and characterized. Thereupon a transformation algorithm is described which is a generalization of the Hungarian method for the classical transportation problem as well as of a threshold method for time transportation problems
Finding All Essential Terms Of A Characteristic Maxpolynomial
No full textLet us denote a b = max(a; b) and b = a + b for a; b 2 R = R [ f1g and extend this pair of operations to matrices and vectors in the same way as in linear algebra. We present an O(n ) algorithm for nding all essential terms of the max-algebraic characteristic polynomial of an n n matrix over R : In the cases when all terms are essential this algorithm also solves the following problem: Given an nn matrix A and k 2 f1; :::; ng, nd a kk principal submatrix of A whose assignment problem value is maximum
On Latin Squares and the Facial Structure of Related Polytopes
No full textBy identifying all latin squares of order n with certain n²-element subsets of an n³-element ground set En a clutter Bn is obtained, which induces an independence system (En,In) in a natural way. Starting from Ryser's conditions for the completion of latin rectangles, cf. L. Mirsky [Transversal Theory, Academic Press (1971)], we present special cases of circuits of (En,In) and extend Ryser's conditions slightly. Latin squares of order n correspond to the solutions of planar 3-dimensional assignment problems and, in view of its solution via linear programming techniques, we present some first classes of facet-defining inequalities for P(In) resp. P(In), the convex hull of all those 0-1 vectors, which correspond to members of In resp. Bn
Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees
No full textAbstractThis article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(rvnlogn) time where the parameter rv is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang
Weight Reduction Problems with Bottleneck Objective
No full textThis paper is concerned with bottleneck weight reduction problems stated as follows. We are given a finite set E, a class F of nonempty subsets of E, a weight w: E ! R and a cost c: E ! R . For each e 2 E; c(e) stands for the cost of reducing weight w(e) by one unit. For each subset F 2 F , the bottleneck weight of F is w(F ) = min w(e). The weight of the family F is the maximum of w(F ) for all F in F . The problem is to determine new weights x(e) w(e) such that the weight of F is minimized under the constraint that the overall reduction cost does not exceed a given budget B. Similarl
Constrained Steiner trees in Halin graphs
No full textIn this paper, we study the problem of computing a minimum cost Steiner tree subject to a weight constraint in a Halin graph where each edge has a nonnegative integer cost and a nonnegative integer weight. We prove the NP-hardness of this problem and present a fully polynomial time approximation scheme for this NP-hard problem
Bottleneck capacity expansion problems with general budget constraints
No full textThis paper presents a unified approach for
bottleneck capacity expansion problems.
In the bottleneck capacity expansion
problem, BCEP, we are given a finite ground set E, a family F
of feasible subsets of E and a nonnegative real capacity ĉe
for all e ∈ E. Moreover, we are given monotone increasing cost functions fe for
increasing the capacity of the elements e ∈ E as well as a
budget B. The task
is to determine new capacities ce ≥ ĉe such that the
objective function given by maxF∈Fmine∈Fce
is maximized under the side
constraint that the overall expansion cost does not exceed the budget B.
We introduce an algebraic model for defining the overall expansion cost and
for formulating the budget constraint. This models allows to capture
various types of budget constraints in one general model.
Moreover, we discuss solution approaches for the general bottleneck capacity
expansion problem. For an important subclass of bottleneck capacity expansion
problems we propose algorithms which perform a strongly polynomial number of
steps. In this manner we generalize and improve a recent result of
Zhang et al. [15]
- …
