School of Mathematics and Statistics - Research Publications

Permanent URI for this collection

http://hdl.handle.net/11343/294

Filters

2015 3
2 1
Reset filters

Settings
Statistics
Citations
Author: Rubinstein, Joachim × End date: 2015 × Start date: 2015 ×

Search Results

Now showing 1 - 3 of 3
  • Item
    Thumbnail Image
    Maximizing the net present value of a Steiner tree
    Sirinanda, KG ; Brazil, M ; Grossman, PA ; Rubinstein, JH ; Thomas, DA (Springer US, 2015)
    The theory of Steiner trees has been extensively applied in physical network design problems to locate a Steiner point that minimizes the total length of a tree. However, maximizing the total generated cash flows of a tree has not been investigated. Such a tree has costs associated with its edges and values associated with nodes. In order to reach the nodes in the tree, the edges need to be constructed. The edges are constructed in a particular order and the costs of constructing the edges and the values at the nodes are discounted over time. These discounted costs and values generate cash flows. In this paper, we study the problem of optimally locating a single Steiner point so as to maximize the sum of all the discounted cash flows, known as the net present value (NPV). An application of this problem occurs in underground mining where, we want to optimally locate a junction point in the underground access network to maximize the NPV. We propose an efficient iterative algorithm to optimally locate a single degree-3 Steiner point. We show this algorithm converges quickly and the Steiner point is unique subject to realistic design parameters.
  • Item
    No Preview Available
    Optimal curvature and gradient-constrained directional cost paths in 3-space
    Chang, AJ ; BRAZIL, M ; Rubinstein, JH ; Thomas, DA (Springer Verlag, 2015-07-01)
  • Item
    No Preview Available
    Bounding Embeddings of VC Classes into Maximum Classes
    Rubinstein, JH ; RUBINSTEIN, B ; Bartlett, PL ; Vovk, V ; Papadopoulos, H ; Gammerman, A (Springer, 2015)
    One of the earliest conjectures in computational learning theory-the Sample Compression conjecture-asserts that concept classes (equivalently set systems) admit compression schemes of size linear in their VC dimension. To-date this statement is known to be true for maximum classes---those that possess maximum cardinality for their VC dimension. The most promising approach to positively resolving the conjecture is by embedding general VC classes into maximum classes without super-linear increase to their VC dimensions, as such embeddings would extend the known compression schemes to all VC classes. We show that maximum classes can be characterised by a local-connectivity property of the graph obtained by viewing the class as a cubical complex. This geometric characterisation of maximum VC classes is applied to prove a negative embedding result which demonstrates VC-d classes that cannot be embedded in any maximum class of VC dimension lower than 2d. On the other hand, we show that every VC-d class C embeds in a VC-(d+D) maximum class where D is the deficiency of C, i.e., the difference between the cardinalities of a maximum VC-d class and of C. For VC-2 classes in binary n-cubes for 4 <= n <= 6, we give best possible results on embedding into maximum classes. For some special classes of Boolean functions, relationships with maximum classes are investigated. Finally we give a general recursive procedure for embedding VC-d classes into VC-(d+k) maximum classes for smallest k.