The linkedness of cubical polytopes : beyond the cube
- Authors: Bui, Hoa , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2024
- Type: Text , Journal article
- Relation: Discrete Mathematics Vol. 347, no. 3 (2024), p.
- Relation: https://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least 2k vertices is k-linked if, for every set of k disjoint pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is k-linked if its graph is k-linked. In a previous paper [3] we proved that every cubical d-polytope is ⌊d/2⌋-linked. Here we strengthen this result by establishing the ⌊(d+1)/2⌋-linkedness of cubical d-polytopes, for every d≠3. A graph G is strongly k-linked if it has at least 2k+1 vertices and, for every vertex v of G, the subgraph G−v is k-linked. We say that a polytope is (strongly) k-linked if its graph is (strongly) k-linked. In this paper, we also prove that every cubical d-polytope is strongly ⌊d/2⌋-linked, for every d≠3. These results are best possible for this class of polytopes.
- Description: A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. The paper is concerned with the linkedness of the graphs of cubical polytopes. A graph with at least 2k vertices is k-linked if, for every set of k disjoint pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We say that a polytope is k-linked if its graph is k-linked. In a previous paper [3] we proved that every cubical d-polytope is
Characterization theorem for best polynomial spline approximation with free knots, variable degree and fixed tails
- Authors: Crouzeix, Jean-Pierre , Sukhorukova, Nadezda , Ugon, Julien
- Date: 2017
- Type: Text , Journal article
- Relation: Journal of Optimization Theory and Applications Vol. 172, no. 3 (2017), p. 950-964
- Full Text:
- Reviewed:
- Description: In this paper, we derive a necessary condition for a best approximation by piecewise polynomial functions of varying degree from one interval to another. Based on these results, we obtain a characterization theorem for the polynomial splines with fixed tails, that is the value of the spline is fixed in one or more knots (external or internal). We apply nonsmooth nonconvex analysis to obtain this result, which is also a necessary and sufficient condition for inf-stationarity in the sense of Demyanov-Rubinov. This paper is an extension of a paper where similar conditions were obtained for free tails splines. The main results of this paper are essential for the development of a Remez-type algorithm for free knot spline approximation.
Finite alternation theorems and a constructive approach to piecewise polynomial approximation in chebyshev norm
- Authors: Crouzeix, Jean-Pierre , Sukhorukova, Nadezda , Ugon, Julien
- Date: 2020
- Type: Text , Journal article
- Relation: Set-Valued and Variational Analysis Vol. 28, no. 1 (2020), p. 123-147. http://purl.org/au-research/grants/arc/DP180100602
- Full Text: false
- Reviewed:
- Description: One of the purposes in this paper is to provide a better understanding of the alternance property which occurs in Chebyshev polynomial approximation and continuous piecewise polynomial approximation problems. In the first part of this paper, we prove that alternating sequences of any continuous function are finite in any given segment and then propose an original approach to obtain new proofs of the well known necessary and sufficient optimality conditions. There are two main advantages of this approach. First of all, the proofs are intuitive and easy to understand. Second, these proofs are constructive and therefore they lead to new alternation-based algorithms. In the second part of this paper, we develop new local optimality conditions for free knot polynomial spline approximation. The proofs for free knot approximation are relying on the techniques developed in the first part of this paper. The piecewise polynomials are required to be continuous on the approximation segment. © 2020, Springer Nature B.V.
On the reconstruction of polytopes
- Authors: Doolittle, Joseph , Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2019
- Type: Text , Journal article
- Relation: Discrete and Computational Geometry Vol. 61, no. 2 (2019), p. 285-302. http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: Blind and Mani, and later Kalai, showed that the face lattice of a simple polytope is determined by its graph, namely its 1-skeleton. Call a vertex of a d-polytope nonsimple if the number of edges incident to it is more than d. We show that (1) the face lattice of any d-polytope with at most two nonsimple vertices is determined by its 1-skeleton; (2) the face lattice of any d-polytope with at most d- 2 nonsimple vertices is determined by its 2-skeleton; and (3) for any d> 3 there are two d-polytopes with d- 1 nonsimple vertices, isomorphic (d- 3) -skeleta and nonisomorphic face lattices. In particular, the result (1) is best possible for 4-polytopes. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
Multivariate approximation by polynomial and generalized rational functions
- Authors: Díaz Millán, Reinier , Peiris, Vinesha , Sukhorukova, Nadezda , Ugon, Julien
- Date: 2022
- Type: Text , Journal article
- Relation: Optimization Vol. 71, no. 4 (2022), p. 1171-1187
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: In this paper, we develop an optimization-based approach to multivariate Chebyshev approximation on a finite grid. We consider two models: multivariate polynomial approximation and multivariate generalized rational approximation. In the second case, the approximations are ratios of linear forms and the basis functions are not limited to monomials. It is already known that in the case of multivariate polynomial approximation on a finite grid the corresponding optimization problems can be reduced to solving a linear programming problem, while the area of multivariate rational approximation is not so well understood. In this paper we demonstrate that in the case of multivariate generalized rational approximation the corresponding optimization problems are quasiconvex. This statement remains true even when the basis functions are not limited to monomials. Then we apply a bisection method, which is a general method for quasiconvex optimization. This method converges to an optimal solution with given precision. We demonstrate that the convex feasibility problems appearing in the bisection method can be solved using linear programming. Finally, we compare the deviation error and computational time for multivariate polynomial and generalized rational approximation with the same number of decision variables. © 2022 Informa UK Limited, trading as Taylor & Francis Group.
Solving Euclidian travelling salesman problem using discrete-gradient based clustering and kohonen neural network
- Authors: Ghosh, Moumita , Ugon, Julien , Ghosh, Ranadhir , Bagirov, Adil
- Date: 2004
- Type: Text , Conference paper
- Relation: Paper presented at ICOTA6: 6th International Conference on Optimization - Techniques and Applications, Ballarat, Victoria : 9th December, 2004
- Full Text: false
- Reviewed:
- Description: E1
- Description: 2003000864
Linkedness of cartesian products of complete graphs
- Authors: Jorgensen, Leif , Pineda-Villavicencio, Guillermo , Ugon, Julien
- Date: 2022
- Type: Text , Journal article
- Relation: Ars Mathematica Contemporanea Vol. 22, no. 2 (2022), p.
- Relation: http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: This paper is concerned with the linkedness of Cartesian products of complete graphs. A graph with at least 2k vertices is k-linked if, for every set of 2k distinct vertices organised in arbitrary k pairs of vertices, there are k vertex-disjoint paths joining the vertices in the pairs. We show that the Cartesian product Kd1+1 × Kd2+1 of complete graphs Kd1+1 and Kd2+1 is
A new algorithm for the placement of WLAN access point based on nonsmooth optimization technique
- Authors: Kouhbor, Shahnaz , Ugon, Julien , Kruger, Alexander , Rubinov, Alex , Branch, Philip
- Date: 2005
- Type: Text , Conference paper
- Relation: Paper presented at the 7th International Conference on Advanced Communication Technology, Phoenix Park, Korea : 21st February, 2005
- Full Text:
- Reviewed:
- Description: In wireless local area network (WLAN), signal coverage is obtained by proper placement of access points (APs). The impact of incorrect placement of APs is significant. If they are placed too far apart, they generate a coverage gap but if they are too close to each other, this leads to excessive co-channel interferences. In this paper, we describe a mathematical model we have developed to find the optimal number and location of APs. To solve the problem, we use an optimization algorithm developed at the University of Ballarat called discrete gradient algorithm. Results indicate that our model is able to solve optimal coverage problems for different numbers of users.
- Description: E1
- Description: 2003001376
Optimal placement of access point in WLAN based on a new algorithm
- Authors: Kouhbor, Shahnaz , Ugon, Julien , Kruger, Alexander , Rubinov, Alex
- Date: 2005
- Type: Text , Conference paper
- Relation: Paper presented at ICMB 2005, International Conference on Mobile Business, Sydney, Australia, 11-13 July 2005, Sydney : 11th - 13th July, 2005
- Full Text:
- Reviewed:
- Description: When designing wireless communication systems, it is very important to know the optimum numbers and locations for the access points (APs). The impact of incorrect placement of APs is significant. If they are placed too far apart, they will generate a coverage gap, but if they are too close to each other, this will lead to excessive co-channel interferences. In this paper we describe a mathematical model developed to find the optimal number and location of APs. To solve the problem, we use the Discrete Gradient optimization algorithm developed at the University of Ballarat. Results indicate that our model is able to solve optimal coverage problems for different numbers of users.
- Description: 2003001377
Coverage in WLAN : Optimization model and algorithm
- Authors: Kouhbor, Shahnaz , Ugon, Julien , Mammadov, Musa , Rubinov, Alex , Kruger, Alexander
- Date: 2006
- Type: Text , Conference paper
- Relation: Paper presented at the First International Conference on Wireless Broadband and Ultra Wideband Communications, AusWireless 2006, Sydney : 13th March, 2006
- Full Text:
- Reviewed:
- Description: When designing wireless communication systems, it is very important to know the optimum numbers of access points (APs) in order to provide a reliable design. In this paper we describe a mathematical model developed for finding the optimal number and location of APs. A new Global Optimization Algorithm (AGOP) is used to solve the problem. Results obtained demonstrate that the model and software are able to solve optimal coverage problems for design areas with different types of obstacles and number of users.
- Description: 2003001757
Optimization in wireless local area network
- Authors: Kouhbor, Shahnaz , Ugon, Julien , Kruger, Alexander , Rubinov, Alex , Branch, Philip
- Date: 2004
- Type: Text , Conference paper
- Relation: Paper presented at ICOTA6: 6th International Conference on Optimization - Techniques and Applications, Ballarat, Victoria : 9th December, 2004
- Full Text: false
- Reviewed:
- Description: 2003000886
Coverage in WLAN with minimum number of access points
- Authors: Kouhbor, Shahnaz , Ugon, Julien , Rubinov, Alex , Kruger, Alexander , Mammadov, Musa
- Date: 2006
- Type: Text , Conference paper
- Relation: Paper presented at VTC 2006 - Spring, 2006 IEEE 63rd Vehicular Technology Conference, Melbourne : 7th May, 2006
- Full Text:
- Reviewed:
- Description: E1
- Description: 2003001610
Analysis and comparison of co-occurrence matrix and pixel n-gram features for mammographic images
- Authors: Kulkarni, Pradnya , Stranieri, Andrew , Kulkarni, Sid , Ugon, Julien , Mittal, Manish
- Date: 2015
- Type: Text , Conference paper
- Relation: International Conference on Communication and Computing p. 7-14
- Full Text: false
- Reviewed:
- Description: Mammography is a proven way of detecting breast cancer at an early stage. Various feature extraction techniques such as histograms, co-occurrence matrix, local binary patterns, Gabor filters, wavelet transforms are used for analysing mammograms. The novel pixel N-gram feature extraction technique has been inspired from the character N-gram concept of text retrieval. In this paper, we have compared the novel N-gram feature extraction technique with the co-occurrence matrix feature extraction technique. The experiments were conducted on the benchmark miniMIAS mammography database. Classification of mammograms into normal and abnormal category using N-gram features showed promising results with greater classification accuracy, sensitivity and specificity compared to classification using co-occurrence matrix features. Moreover, N-gram features computation are found to be considerably faster than co-occurrence matrix feature computation
Visual character N-grams for classification and retrieval of radiological images
- Authors: Kulkarni, Pradnya , Stranieri, Andrew , Kulkarni, Siddhivinayak , Ugon, Julien , Mittal, Manish
- Date: 2014
- Type: Text , Journal article
- Relation: International Journal of Multimedia & Its Applications Vol. 6, no. 2 (April 2014), p. 35-49
- Full Text:
- Reviewed:
- Description: Diagnostic radiology struggles to maintain high interpretation accuracy. Retrieval of past similar cases would help the inexperienced radiologist in the interpretation process. Character n-gram model has been effective in text retrieval context in languages such as Chinese where there are no clear word boundaries. We propose the use of visual character n-gram model for representation of image for classification and retrieval purposes. Regions of interests in mammographic images are represented with the character n-gram features. These features are then used as input to back-propagation neural network for classification of regions into normal and abnormal categories. Experiments on miniMIAS database show that character n-gram features are useful in classifying the regions into normal and abnormal categories. Promising classification accuracies are observed (83.33%) for fatty background tissue warranting further investigation. We argue that Classifying regions of interests would reduce the number of comparisons necessary for finding similar images from the database and hence would reduce the time required for retrieval of past similar cases.
Pixel N-grams for mammographic lesion classification
- Authors: Kulkarni, Pradnya , Stranieri, Andrew , Ugon, Julien , Mittal, Manish , Kulkarni, Siddhivinayak
- Date: 2017
- Type: Text , Conference proceedings
- Relation: 2017 2nd International Conference on Communication Systems, Computing and IT Applications, CSCITA , Mumbai; 7th-8th April, 2017; published in CSCITA 2017 - Proceedings p. 107-111
- Full Text: false
- Reviewed:
- Description: Automated classification algorithms have been applied to breast cancer diagnosis in order to improve the diagnostic accuracy and turnover time. However, classification accuracy, sensitivity and specificity could still be improved further. Moreover, reducing computational cost is another challenge as the number of images to be analyzed is typically large. In this paper, a novel Pixel N-gram approach inspired from character N-grams in the text retrieval context has been applied for mammographic lesion classification. The experiments on real world database demonstrate that the Pixel N-grams outperform the existing histogram as well as Haralick features with respect to classification accuracy as well as sensitivity. Effect of varying N and using various classifiers is also analyzed in this paper. Results show that optimum value of N is equal to 3 and MLP classifier performs better than SVM and KNN classifier using 3-gram features.
Texture image classification using pixel N-grams
- Authors: Kulkarni, Pradnya , Stranieri, Andrew , Ugon, Julien
- Date: 2016
- Type: Text , Conference proceedings
- Relation: 2016 IEEE International Conference on Signal and Image Processing (ICSIP); Beijing, China; 13-15 Aug, 2016 p. 137-141
- Full Text: false
- Reviewed:
- Description: Various statistical methods such as co-occurrence matrix, local binary patterns and spectral approaches such as Gabor filters have been used for generating global features for image classification. However, global image features fail to distinguish between local variations within an image. Bag-of-visual-words (BoVW) model do capture local variations in an image, but typically do not consider spatial relationships between the visual words. Here, a novel image representation ‘Pixel N-grams’, inspired from the character N-gram concept in text retrieval has been applied for texture classification purpose. Texture is an important property for image classification. Experiments on the benchmark texture database (UIUC) demonstrates that the overall classification accuracy resulting from Pixel N-gram approach (89.5%) is comparable with that achieved using BoVW approach (84.4%) with the added advantage of simplicity and reduced computational cost.
Compiling and using input-output frameworks through collaborative virtual laboratories
- Authors: Lenzen, Manfred , Geschke, Arne , Wiedmann, Thomas , Lane, Joe , Anderson, Neal , Baynes, Timothy , Boland, John , Daniels, Peter , Dey, Christopher , Fry, Jacob , Hadjikakou, Michalis , Kenway, Steven , Malik, Arunima , Moran, Daniel , Murray, Joy , Nettleton, Stuart , Poruschi, Lavinia , Reynolds, Christian , Rowley, Hazel , Ugon, Julien , Webb, Dean , West, James
- Date: 2014
- Type: Text , Journal article
- Relation: Science of the Total Environment Vol. 485-486, no. 1 (July 2014), p. 241-251
- Full Text: false
- Reviewed:
- Description: Compiling, deploying and utilising large-scale databases that integrate environmental and economic data have traditionally been labour- and cost-intensive processes, hindered by the large amount of disparate and misaligned data that must be collected and harmonised. The Australian Industrial Ecology Virtual Laboratory (IELab) is a novel, collaborative approach to compiling large-scale environmentally extended multi-region input-output (MRIO) models.The utility of the IELab product is greatly enhanced by avoiding the need to lock in an MRIO structure at the time the MRIO system is developed. The IELab advances the idea of the "mother-daughter" construction principle, whereby a regionally and sectorally very detailed "mother" table is set up, from which "daughter" tables are derived to suit specific research questions. By introducing a third tier - the "root classification" - IELab users are able to define their own mother-MRIO configuration, at no additional cost in terms of data handling. Customised mother-MRIOs can then be built, which maximise disaggregation in aspects that are useful to a family of research questions.The second innovation in the IELab system is to provide a highly automated collaborative research platform in a cloud-computing environment, greatly expediting workflows and making these computational benefits accessible to all users.Combining these two aspects realises many benefits. The collaborative nature of the IELab development project allows significant savings in resources. Timely deployment is possible by coupling automation procedures with the comprehensive input from multiple teams. User-defined MRIO tables, coupled with high performance computing, mean that MRIO analysis will be useful and accessible for a great many more research applications than would otherwise be possible. By ensuring that a common set of analytical tools such as for hybrid life-cycle assessment is adopted, the IELab will facilitate the harmonisation of fragmented, dispersed and misaligned raw data for the benefit of all interested parties.
Detecting K-complexes for sleep stage identification using nonsmooth optimization
- Authors: Moloney, David , Sukhorukova, Nadezda , Vamplew, Peter , Ugon, Julien , Li, Gang , Beliakov, Gleb , Philippe, Carole , Amiel, Hélène , Ugon, Adrien
- Date: 2012
- Type: Text , Journal article
- Relation: ANZIAM Journal Vol. 52, no. 4 (2012), p. 319-332
- Full Text:
- Reviewed:
- Description: The process of sleep stage identification is a labour-intensive task that involves the specialized interpretation of the polysomnographic signals captured from a patient's overnight sleep session. Automating this task has proven to be challenging for data mining algorithms because of noise, complexity and the extreme size of data. In this paper we apply nonsmooth optimization to extract key features that lead to better accuracy. We develop a specific procedure for identifying K-complexes, a special type of brain wave crucial for distinguishing sleep stages. The procedure contains two steps. We first extract "easily classified" K-complexes, and then apply nonsmooth optimization methods to extract features from the remaining data and refine the results from the first step. Numerical experiments show that this procedure is efficient for detecting K-complexes. It is also found that most classification methods perform significantly better on the extracted features. © 2012 Australian Mathematical Society.
Almost simplicial polytopes : the lower and upper bound theorems
- Authors: Nevo, Eran , Pineda-Villavicencio, Guillermo , Ugon, Julien , Yost, David
- Date: 2020
- Type: Text , Journal article
- Relation: Canadian Journal of Mathematics Vol. 72, no. 2 (2020), p. 537-556. http://purl.org/au-research/grants/arc/DP180100602
- Full Text:
- Reviewed:
- Description: We study -vertex -dimensional polytopes with at most one nonsimplex facet with, say, vertices, called almost simplicial polytopes. We provide tight lower and upper bound theorems for these polytopes as functions of, and, thus generalizing the classical Lower Bound Theorem by Barnette and the Upper Bound Theorem by McMullen, which treat the case where s = 0. We characterize the minimizers and provide examples of maximizers for any. Our construction of maximizers is a generalization of cyclic polytopes, based on a suitable variation of the moment curve, and is of independent interest. © 2018 Canadian Mathematical Society.
Generalised rational approximation and its application to improve deep learning classifiers
- Authors: Peiris, V , Sharon, Nir , Sukhorukova, Nadezda , Ugon, Julien
- Date: 2021
- Type: Text , Journal article
- Relation: Applied Mathematics and Computation Vol. 389, no. (2021), p.
- Relation: https://purl.org/au-research/grants/arc/DP180100602
- Full Text: false
- Reviewed:
- Description: A rational approximation (that is, approximation by a ratio of two polynomials) is a flexible alternative to polynomial approximation. In particular, rational functions exhibit accurate estimations to nonsmooth and non-Lipschitz functions, where polynomial approximations are not efficient. We prove that the optimisation problems appearing in the best uniform rational approximation and its generalisation to a ratio of linear combinations of basis functions are quasiconvex even when the basis functions are not restricted to monomials. Then we show how this fact can be used in the development of computational methods. This paper presents a theoretical study of the arising optimisation problems and provides results of several numerical experiments. We apply our approximation as a preprocessing step to deep learning classifiers and demonstrate that the classification accuracy is significantly improved compared to the classification of the raw signals. © 2020
- Description: This research was supported by the Australian Research Council (ARC), Solving hard Chebyshev approximation problems through nonsmooth analysis (Discovery Project DP180100602 ). This research was partially sponsored by Tel Aviv-Swinburne Research Collaboration Grant (2019).