Asset-Backed Securitization (ABS) is an emerging sector of today banks' business. It represents an effective tool to turn unrated assets, such as commercial papers or lease contracts, into marketable financial pro...
详细信息
Asset-Backed Securitization (ABS) is an emerging sector of today banks' business. It represents an effective tool to turn unrated assets, such as commercial papers or lease contracts, into marketable financial products through the issuance of special notes, namely the asset-backed securities. In this paper we analyze the problem of optimally selecting the assets to be converted into notes with respect to scenarios motivated by real-world problems. In particular, we study the case in which the assets amortization rule is characterized by constant periodic principal installments instead of the more classical amortization rule based on constant general ( principal plus interests) installments. We show the computational advantages and the practical implications of this choice. The particular shape of the outstanding principal for the case of constant principal installments is exploited in the solution of a general model which selects assets at different dates. Four approximation algorithms, based on LP-relaxation and on the implicit knapsack structure of the problem, are proposed for this general model. From a theoretical point of view we analyze the exact worst-case behavior of these algorithms compared to the optimal solution. Computational experiments are performed for a practical scenario suggested by a leasing bank. The results show that the proposed approximation algorithms are, on average, highly efficient and effective.
Given an undirected graph G = (V, E) with |V| = n and |E| = m, nonnegative integers c(e) and d(e) for each edge e is an element of E, and a bound D, the constrained minimum spanning tree problem (CST) is to find a spa...
详细信息
Given an undirected graph G = (V, E) with |V| = n and |E| = m, nonnegative integers c(e) and d(e) for each edge e is an element of E, and a bound D, the constrained minimum spanning tree problem (CST) is to find a spanning tree T = (V, E-T) such that (Sigmaeis an element ofET) d(e) less than or equal to D and (Sigmaeis an element ofET) c(e) is minimized. We present an efficient polynomial time approximation scheme (EPTAS) for this problem. Specifically, for every is an element of > 0 we present a (1 + is an element of)-approximation algorithm with time complexity O((1/is an element of)(O(1/is an element of)) n(4)). Our method is based on Lagrangian relaxation and matroid intersection.
The problems dealt with in this paper are generalizations of the set cover problem, min{cx \ Ax greater than or equal to b, x is an element of {0, 1}(n)}, where c is an element of Q(n)(+), A is an element of {0, 1}(mx...
详细信息
The problems dealt with in this paper are generalizations of the set cover problem, min{cx \ Ax greater than or equal to b, x is an element of {0, 1}(n)}, where c is an element of Q(n)(+), A is an element of {0, 1}(mxn), b is an element of (1) over right arrow. The covering 0-1 integer program is the one, in this formulation, with arbitrary nonnegative entries of A and b, while the partial set cover problem requires only m - K constrains (or more) in Ax greater than or equal to b to be satisfied when integer K is additionall specified. While many approximation algorithms have been recently developed for these problems and their special cases, using computationally rather expensive (albeit polynomial) LP-rounding (or SDP-rounding), we present a more efficient purely combinatorial algorithm and investigate its approximation capability for them. It will be shown that, when compared with the best performance known today and obtained by rounding methods, although its performance comes short in some special cases, it is at least equally good in general, extends for partial vertex cover, and improves for weighted multicover partial set cover, and further generalizations.
We consider a linear programming problem with unknown objective function. Random observations related to the unknown objective function are sequentially available. We define a stochastic algorithm, based on the simple...
详细信息
We consider a linear programming problem with unknown objective function. Random observations related to the unknown objective function are sequentially available. We define a stochastic algorithm, based on the simplex method, that estimates an optimal solution of the linear programming problem. It is shown that this algorithm converges with probability one to the set of optimal solutions and that its failure probability is of order inversely proportional to the sample size. We also introduce stopping criteria for the algorithm. The asymptotic normality of some suitably defined residuals is also analyzed. The proposed estimation algorithm is motivated by the stochastic approximation algorithms but it introduces a generalization of these techniques when the linear programming problem has several optimal solutions. The proposed algorithm is also close to the stochastic quasi-gradient procedures, though their usual assumptions are weakened.
Let G = (V, E) be a connected graph with a weight function w : V → Z+, and let q ≥ 2 be a positive integer. For X ⊆ V, let w (X) denote the sum of the weights of the vertices in X. We consider the following problem ...
详细信息
Given a hypergraph and a set of colors, we want to find a vertex coloring to minimize the size of any monochromatic set in an edge. We give a deterministic polynomial time approximation algorithm with performance clos...
详细信息
Given a hypergraph and a set of colors, we want to find a vertex coloring to minimize the size of any monochromatic set in an edge. We give a deterministic polynomial time approximation algorithm with performance close to the best bound guaranteed by an existential argument. This can be applied to support divide and conquer approaches to various problems. We give two examples. For deterministic DNF approximate counting, this helps us explore the importance of a previously ignored parameter, the maximum number of appearances of any variable, and we construct algorithms that are particularly good when this parameter is small. For partially ordered sets, we are able to constructivize the dimension bound given by Furedi and Kahn [Order, 3 (1986), pp. 15 - 20].
Given a set P of points in the plane, a geometric minimum-diameter spanning tree (GMDST) of P is a spanning tree of P such that the longest path through the tree is minimized. For several years, the best upper bound o...
详细信息
Given a set P of points in the plane, a geometric minimum-diameter spanning tree (GMDST) of P is a spanning tree of P such that the longest path through the tree is minimized. For several years, the best upper bound on the time to compute a GMDST was cubic with respect to the number of points in the input set. Recently, Timothy Chan introduced a subcubic time algorithm. In this paper we present an algorithm that generates a tree whose diameter is no more than (1 + E) times that of a GMDST, for any e > 0. Our algorithm reduces the problem to several grid-aligned versions of the problem and runs within time 0(e(-3) + n) and space 0(n).
In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to ...
详细信息
In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.
We address the two-dimensional Knapsack Problem (2YP), aimed at packing a maximum-profit subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the on...
详细信息
We address the two-dimensional Knapsack Problem (2YP), aimed at packing a maximum-profit subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the one-dimensional KP with item weights equal to the rectangle areas, proving the worst-case performance of the associated upper bound, and present and compare computationally four exact algorithms based on the above relaxation, showing their effectiveness. (C) 2003 Elsevier B.V. All rights reserved.
We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge (u, v) is labeled either+or- depending on whether u and v have been deemed to be similar or different. The ...
详细信息
We consider the following clustering problem: we have a complete graph on n vertices (items), where each edge (u, v) is labeled either+or- depending on whether u and v have been deemed to be similar or different. The goal is to produce a partition of the vertices (a clustering) that agrees as much as possible with the edge labels. That is, we want a clustering that maximizes the number of + edges within clusters, plus the number of - edges between clusters (equivalently, minimizes the number of disagreements: the number of + edges inside clusters plus the number of + edges between clusters). This formulation is motivated from a document clustering problem in which one has a pairwise similarity function f learned from past data, and the goal is to partition the current set of documents in a way that correlates with f as much as possible;it can also be viewed as a kind of "agnostic learning" problem. An interesting feature of this clustering formulation is that one does not need to specify the number of clusters k as a separate parameter, as in measures such as k-median or min-sum or min-max clustering. Instead, in our formulation, the optimal number of clusters could be any value between 1 and n, depending on the edge labels. We look at approximation algorithms for both minimizing disagreements and for maximizing agreements. For minimizing disagreements, we give a constant factor approximation. For maximizing agreements we give a PTAS, building on ideas of Goldreich, Goldwasser, and Ron (1998) and de la Vega (1996). We also show how to extend some of these results to graphs with edge labels in [-1, +1], and give some results for the case of random noise.
暂无评论