Approximation Algorithms for Survivable Multicommodity Flow Problems with Applications to Network Design

Multicommodity flow (MF) problems have a wide variety of applications in areas such as VLSI circuit design, network design, etc., and are therefore very well studied. The fractional MF problems are polynomial time solvable while integer versions are NP-complete. However, exact algorithms to solve the fractional MF problems have high computational complexity. Therefore approximation algorithms to solve the fractional MF problems have been explored in the literature to reduce their computational complexity. Using these approximation algorithms and the randomized rounding technique, polynomial time approximation algorithms have been explored in the literature. In the design of high-speed networks, such as optical wavelength division multiplexing (WDM) networks, providing survivability carries great significance. Survivability is the ability of the network to recover from failures. It further increases the complexity of network design and presents network designers with more formidable challenges. In this work we formulate the survivable versions of the MF problems. We build approximation algorithms for the survivable multicommodity flow (SMF) problems based on the framework of the approximation algorithms for the MF problems presented in [1] and [2]. We discuss applications of the SMF problems to solve survivable routing in capacitated networks.

EC94-852 Cash Flow Planning Form

This extension circular covers the following areas of a cash flow planning form: Beginning Cash Balance, Operating Sales (crop and hay, market livestock, livestock product, custom work); Capital Sales (breeding livestock, machinery and equipment); Personal Income (wages, interest); Operating Expenses (car/truck, chemicals, conservation, custom hire, feed purchased, fertilizers and lime, freight and trucking, gasoline, fuel and oil, insurance, labor hired, rents and leases, repairs and maintenance, seeds and plants, storage, warehousing, supplies, taxes, utilities, veterinary, breeding fees and medicine, feeder livestock); Capital Purchases (breeding livestock, machinery and equipment, family living withdrawals, personal investments, income and social security, term loan payments); Net Cash Available (operating loan borrowings, operating loan payments); and Ending Operating Loan Balance. Along with the Cash Flow Planning Form is a Projected Income Statement Form which covers Projected Business Income (operating sales, breeding livestock, estimated cash income adjustments, estimated gross revenues, estimated value of production); Project Business Expenses (cash operating, esimated operating, prepaid and supplies, cash investment in growing crops, accounts payable); Projected Net Income Summary (estimated net income from operations, estimated net business income, estimated net income after taxes, estimated earned net worth change); and a Physical Inventory Flows Worksheet.