UC Research Repository Community:
http://hdl.handle.net/10092/1
Sat, 25 Oct 2014 00:02:04 GMT2014-10-25T00:02:04ZCombining Shortest Paths, Bottleneck Paths and Matrix Multiplication
http://hdl.handle.net/10092/9740
Title: Combining Shortest Paths, Bottleneck Paths and Matrix Multiplication
Authors: Shinn, Tong-Wook
Abstract: We provide a formal mathematical definition of the Shortest Paths for All Flows (SP-AF) problem and provide many efficient algorithms. The SP-AF problem combines the well known Shortest Paths (SP) and Bottleneck Paths (BP) problems, and can be solved by utilising matrix multiplication. Thus in our research of the SP-AF problem, we also make a series of contributions to the underlying topics of the SP problem, the BP problem, and matrix multiplication.
For the topic of matrix multiplication we show that on an n-by-n two dimensional (2D) square mesh array, two n-by-n matrices can be multiplied in exactly 1.5n ‒ 1 communication steps. This halves the number of communication steps required by the well known Cannon’s algorithm that runs
on the same sized mesh array.
We provide two contributions for the SP problem. Firstly, we enhance the breakthrough algorithm by Alon, Galil and Margalit (AGM), which was the first algorithm to achieve a deeply sub-cubic time bound for solving the All Pairs Shortest Paths (APSP) problem on dense directed graphs. Our enhancement allows the algorithm by AGM to remain sub-cubic for larger upper bounds on integer edge costs. Secondly, we show that for graphs with n vertices, the APSP problem can be solved in exactly 3n ‒ 2 communication steps on an n-by-n 2D square mesh array. This improves on the previous result of 3.5n communication steps achieved by Takaoka and Umehara.
For the BP problem, we show that we can compute the bottleneck of the entire graph without solving the All Pairs Bottleneck Paths (APBP) problem, resulting in a much more efficient time bound.
Finally we define an algebraic structure called the distance/flow semi-ring to formally introduce the SP-AF problem, and we provide many algorithms for solving the Single Source SP-AF (SSSP-AF) problem and the All Pairs SP-AF (APSP-AF) problem. For the APSP-AF problem, algebraic algorithms are given that utilise faster matrix multiplication over a ring.Wed, 01 Jan 2014 00:00:00 GMThttp://hdl.handle.net/10092/97402014-01-01T00:00:00ZThe general mechanism of evaporation and production of saturated brine by natural evaporation of sea water in large ponds
http://hdl.handle.net/10092/9728
Title: The general mechanism of evaporation and production of saturated brine by natural evaporation of sea water in large ponds
Authors: Teplitzky, D. R.
Abstract: The principle of manufacturing salt from the sea is discussed. An examination of the literature indicates that the only relevant investigation which has been carried out is on the rate of evaporation from large bodies of water. A summary of the relevant methods of assessing the evaporation is made and it is concluded that the aerodynamic approach is the most promising. An approximate equation describing the evaporation from Lake Grassmere as a function of time and brine concentration is derived for average weather conditions. A qualitative discussion on the mechanism of natural evaporation of water from brine ponds by solar energy leads to energy balances which, it is suggested, should be completely investigated to produce an optimum depth of brine in a pond.
Material balances are set up for the general case of flow in n ponds. These can not be solved, for the variation of flow with time and a stepwise procedure is adopted to allow calculation of the output of saturated brine under average weather conditions for one, two, more than two, and an infinite number of ponds in a system. The latter calculations are based on what is proved to be an invalid assumption so that the results are erroneous. For the one and two pond cases, an estimate of output of saturated brine under average weather conditions is made and the time required to reach the stage of maximum output assessed.Fri, 01 Jan 1954 00:00:00 GMThttp://hdl.handle.net/10092/97281954-01-01T00:00:00ZThe Management of Portable Toilets in the Eastern Suburbs of Christchurch after the February 22, 2011 Earthquake.
http://hdl.handle.net/10092/9727
Title: The Management of Portable Toilets in the Eastern Suburbs of Christchurch after the February 22, 2011 Earthquake.
Authors: Potangaroa, R.; Wilkinson, S.; Zare, M.; Steinfort, P.
Abstract: The extent of liquefaction in the eastern suburbs
of Christchurch (Aranui, Bexley, Avonside,
Avonhead and Dallington) from the February 22
2011 Earthquake resulted in extensive damage to
in-ground waste water pipe systems. This caused
a huge demand for portable toilets (or port-a-loos)
and companies were importing them from outside
Canterbury and in some instances from Australia.
However, because they were deemed “assets
of importance” under legislation, their allocation
had to be coordinated by Civil Defence and
Emergency Management (CDEM). Consequently,
companies supplying them had to ignore requests
from residents, businesses and rest homes; and
commitments to large events outside of the city
such as the Hamilton 400 V8 Supercars and the
Pasifika Festival in Auckland were impacted.
Frustrations started to show as neighbourhoods
questioned the equity of the port-a-loos distribution.
The Prime Minister was reported as reassuring
citizens in the eastern suburbs in the first week
of March that1
“a report about the distribution of
port-a-loos and chemical toilets shows allocation
has been fair. Key said he has asked Civil Defence
about the distribution process and where the toilets
been sent. He said there aren’t enough for the
scale of the event but that is quickly being rectified
and the need for toilets is being reassessed all the
time.” Nonetheless, there still remained a deep
sense of frustration and exclusion over the equity
of the port-a-loos distribution.
This study took the simple approach of mapping where
those port-a-loos were on 11-12 March for several areas
in the eastern suburbs and this suggested that their
distribution was not equitable and was not well done.
It reviews the predictive tools available for estimating
damage to waste water pipes and asks the question
could this situation have been better planned so that
pot-a-loo locations could have been better prioritised?
And finally it reviews the integral roles of communication
and monitoring as part of disaster management strategy.
The impression from this study is that other New
Zealand urban centres could or would also be at risk
and that work is need to developed more rational
management approaches for disaster planning.Sat, 01 Jan 2011 00:00:00 GMThttp://hdl.handle.net/10092/97272011-01-01T00:00:00ZDensification of coke
http://hdl.handle.net/10092/9726
Title: Densification of coke
Authors: Hambleton, W. J.
Abstract: Further work has been carried out on the densification of Stockton coke to confirm Allan’s work (3), which showed that an acceptable density could be obtained by fine grinding and briquetting. The effect of particle size on this densification has now been studied. The density of -7 to +14 B.S. mesh fraction, from briquettes made from -350 mesh coke and heated to 1400°C for 1½ hours, exceeded 42lb/ft³. This was the smallest particle size tested and gave the highest density. The real specific gravity of the heated coke was found to be independent of particle size, but depended markedly on whether the sample was from heated powder or heated briquette.Fri, 01 Jan 1965 00:00:00 GMThttp://hdl.handle.net/10092/97261965-01-01T00:00:00Z