Lower bounds for testing Euclidean Minimum Spanning Trees

The Euclidean Minimum Spanning Tree problem is to decide whether a given graph G=(P,E) on a set of points in the two-dimensional plane is a minimum spanning tree with respect to the Euclidean distance. Czumaj et al. [A. Czumaj, C. Sohler, M. Ziegler, Testing Euclidean Minimum Spanning Trees in the plane, Unpublished, Part II of ESA 2000 paper, downloaded from http://web.njit.edu/~czumaj/] gave a 1-sided-error non-adaptive property-tester for this task of query complexity . We show that every non-adaptive (not necessarily 1-sided-error) property-tester for this task has a query complexity of , implying that the test in [A. Czumaj, C. Sohler, M. Ziegler, Testing Euclidean Minimum Spanning Trees in the plane, Unpublished, Part II of ESA 2000 paper, downloaded from http://web.njit.edu/~czumaj/] is of asymptotically optimal complexity. We further prove that every adaptive property-tester has query complexity of Ω(n1/3). Those lower bounds hold even when the input graph is promised to be a bounded degree tree.     

Formative Evaluation of Near-Semantic Search Interfaces

This article reports findings from a usability study of an experimental near-semantic search interface. We present user preferences for exploring semantic recommendations and model a new user interface for subject suggestions based on the results. The resulting catalog search engine (Deneb 2.0) is in public beta implementation, available at: http://dunatis.grainger.uiuc.edu/deneb-2.     

Computing instanton numbers of curve singularities

We present an algorithm for computing instanton numbers of curve singularities. A comparison is made between these and some other invariants of curve singularities. The algorithm is implemented in Macaulay2, and can be downloaded from http://www.math.nmsu.edu/~iswanson/instanton.m2 or from http://emmy.nmsu.edu/~gasparim/m2code.     

Appalachian State University Libraries' Ask A Librarian: A Reference Service for ASU Students,Faculty, Staff,and Alumni

SUMMARY

As dynamic content is filling the Internet, so are choices for implementing this service/tool for Web developers. This article concentrates on one of the solutions that offers choices and tools in a single free package. Zope delivers Web-based content using a variety of sources and Internet connections. At Appalachian State University, Ask A Librarian http://www.library.appstate.edu/reference/askref.html concentrates on using Zope, the PostgreSQL database, e-mail, and the Web to offer patrons the opportunity to receive guidance from reference librarians while at a remote location.     

HealthLinks: A ColdFusion Web Application

SUMMARY

Libraries are beginning to use Web applications as they grapple with sites of increasing complexity, and the move of more user services to the Web. This article reviews the basic concepts of a Web application, and outlines some of the features of the HealthLinks Web application and site http://healthlinks.washington.edu at the University of Washington Health Science Libraries, and the transition from a Java-based application to ColdFusion.     

An interactive satisficing approach for multi-objective optimization with uncertain parameters

Uncertain variables are used to describe the phenomenon where uncertainty appears in a complex system. For modeling the multi-objective decision-making problems with uncertain parameters, a class of uncertain optimization is suggested for the decision systems in Liu and Chen (2013), http://orsc.edu.cn/online/131020 which is called the uncertain multi-objective programming. In order to solve the proposed uncertain multi-objective programming, an interactive uncertain satisficing approach involving the decision-maker’s flexible demands is proposed in this paper. It makes an improvement in contrast to the noninteractive methods. Finally, a numerical example about the capital budget problem is given to illustrate the effectiveness of the proposed model and the relevant solving approach.     

Calculation of effective conductivity of 2D and 3D composite materials with anisotropic constituents and different inclusion shapes in Mathematica

The study of the effective properties of composite materials with anisotropic constituents and different inclusion shapes has motivated the development of the Mathematica 6.0 package “CompositeMaterials”. This package can be used to calculate the effective anisotropic conductivity tensor of two-phase composites. Any fiber cross section, even percolating ones, can be studied in the 2D composites. “Rectangular Prism” and “Ellipsoidal” inclusion shapes with arbitrary orientations can be investigated in the 3D composites. This package combines the Asymptotic Homogenization Method and the Finite Element Method in order to obtain the effective conductivity tensor. The commands and options of the package are illustrated with two sample applications for two- and three-dimensional composites.

Program summary

Program title:CompositeMaterialsCatalogue identifier:AEAU_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEAU_v1_0.htmlProgram obtainable from:CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions:Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.:132 183No. of bytes in distributed program, including test data, etc.:1 334 908Distribution format:tar.gzProgramming language:Mathematica 6.0Computer:Any that can run Mathematica 6.0 and where the open-source free C-programs Triangle (http://www.cs.cmu.edu/~quake/triangle.html) and TetGen (http://tetgen.berlios.de/) can be compiled and executed. Tested in Intel Pentium computers.Operating system:Any that can run Mathematica 6.0 and where the open-source free C-programs Triangle (http://www.cs.cmu.edu/~quake/triangle.html) and TetGen (http://tetgen.berlios.de/) can be compiled and executed. Tested in Windows XP.RAM:Small two-dimensional calculations require less than 100 MB. Large three-dimensional calculations require 500 MB or more.Classification:7.9External routines:One Mathematica Add-on and two external programs: The free Mathematica Add-On IMS (http://www.imtek.uni-freiburg.de/simulation/Mathematica/IMSweb/), The open-source free C-program Triangle (http://www.cs.cmu.edu/~quake/triangle.html). The open-source free C-program TetGen (http://tetgen.berlios.de/). The distribution file contains Windows executables for Triangle and TetGen.Nature of problem:The calculation of effective thermal conductivity tensor for two-dimensional and three-dimensional composite materials with anisotropic constituents and different inclusion shapes.Solution method:Asymptotic Homogenization Method, with the Cell Problems solved with Finite Element Method.Unusual features:Different inclusion shapes can be easily created. The constituents can be anisotropic. The intermediate stages and the final results can be graphed and analyzed with all the power of Mathematica 6.0. The use of the external meshing programs Triangle and TetGen is totally transparent for the end user. A typical calculation requires the use of only four special commands that follow standard Mathematica syntax.Additional comments:The executable binary files for Triangle and TetGen must be accessible from the directory specified by Mathematica's variable $HomeDirectory. The IMS add-on and the CompositeMaterials package, which is the package presented in this work, must be installed in the directory specified by Mathematica's variable $BaseDirectory or in the variable $UserBaseDirectory. The 2D calculations of Composite Materials will run successfully in Mathematica 5.2 and 6.0 but for the 3D calculations it is necessary to use Mathematica 6.0 or higher.Running time:Simple two-dimensional calculations can be done in less than a minute. Complex three-dimensional calculations can take an hour or more.     

yambo: An ab initio tool for excited state calculations

yambo is an ab initio code for calculating quasiparticle energies and optical properties of electronic systems within the framework of many-body perturbation theory and time-dependent density functional theory. Quasiparticle energies are calculated within the GW approximation for the self-energy. Optical properties are evaluated either by solving the Bethe-Salpeter equation or by using the adiabatic local density approximation. yambo is a plane-wave code that, although particularly suited for calculations of periodic bulk systems, has been applied to a large variety of physical systems. yambo relies on efficient numerical techniques devised to treat systems with reduced dimensionality, or with a large number of degrees of freedom. The code has a user-friendly command-line based interface, flexible I/O procedures and is interfaced to several publicly available density functional ground-state codes.

Program summary

Program title:yamboCatalogue identifier: AEDH_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEDH_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: GNU General Public Licence v2.0No. of lines in distributed program, including test data, etc.: 149 265No. of bytes in distributed program, including test data, etc.: 2 848 169Distribution format: tar.gzProgramming language: Fortran 95, CComputer: any computer architecture, running any flavor of UNIXOperating system: GNU/Linux, AIX, Irix, OS/XHas the code been vectorised or parallelized?: YesRAM: 10-1000 MbytesClassification: 7.3, 4.4, 7.2External routines:

•

BLAS (http://www.netlib.org/blas/)

•

LAPACK (http://www.netlib.org/lapack/)

•

MPI (http://www-unix.mcs.anl.gov/mpi/) is optional.

•

BLACS (http://www.netlib.org/scalapack/) is optional.

•

SCALAPACK (http://www.netlib.org/scalapack/) is optional.

•

FFTW (http://www.fftw.org/) is optional.

•

netCDF (http://www.unidata.ucar.edu/software/netcdf/) is optional.

Nature of problem: Calculation of excited state properties (quasiparticles, excitons, plasmons) from first principles.Solution method: Many body perturbation theory (Dyson equation, Bethe Salpeter equation) and time-dependent density functional theory. Quasiparticle approximation. Plasmon-pole model for the dielectric screening. Plane wave basis set with norm conserving pseudopotentials.Unusual features: During execution, yambo supplies estimates of the elapsed and remaining time for completion of each runlevel. Very friendly shell-based user-interface.Additional comments:yambo was known as “SELF” prior to GPL release. It belongs to the suite of codes maintained and used by the European Theoretical Spectroscopy Facility (ETSF) [1].Running time: The typical yambo running time can range from a few minutes to some days depending on the chosen level of approximation, and on the property and physical system under study.References:[1] The European Theoretical Spectroscopy Facility, http://www.etsf.eu.     

TIERRAS: A package to simulate high energy cosmic ray showers underground, underwater and under-ice

In this paper we present TIERRAS, a Monte Carlo simulation program based on the well-known AIRES air shower simulations system that enables the propagation of particle cascades underground, providing a tool to study particles arriving underground from a primary cosmic ray on the atmosphere or to initiate cascades directly underground and propagate them, exiting into the atmosphere if necessary. We show several cross-checks of its results against CORSIKA, FLUKA, GEANT and ZHS simulations and we make some considerations regarding its possible use and limitations. The first results of full underground shower simulations are presented, as an example of the package capabilities.

Program summary

Program title: TIERRAS for AIRESCatalogue identifier: AEFO_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEFO_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 36 489No. of bytes in distributed program, including test data, etc.: 3 261 669Distribution format: tar.gzProgramming language: Fortran 77 and CComputer: PC, Alpha, IBM, HP, Silicon Graphics and Sun workstationsOperating system: Linux, DEC Unix, AIX, SunOS, Unix System VRAM: 22 Mb bytesClassification: 1.1External routines: TIERRAS requires AIRES 2.8.4 to be installed on the system. AIRES 2.8.4 can be downloaded from http://www.fisica.unlp.edu.ar/auger/aires/eg_AiresDownload.html.Nature of problem: Simulation of high and ultra high energy underground particle showers.Solution method: Modification of the AIRES 2.8.4 code to accommodate underground conditions.Restrictions: In AIRES some processes that are not statistically significant on the atmosphere are not simulated. In particular, it does not include muon photonuclear processes. This imposes a limitation on the application of this package to a depth of 1 km of standard rock (or 2.5 km of water equivalent). Neutrinos are not tracked on the simulation, but their energy is taken into account in decays.Running time: A TIERRAS for AIRES run of a ¹⁰²⁰ eV shower with statistical sampling (thinning) below ¹⁰¹² eV and 0.2 weight factor (see [1]) uses approximately 1 h of CPU time on an Intel Core 2 Quad Q6600 at 2.4 GHz. It uses only one core, so 4 simultaneous simulations can be run on this computer. Aires includes a spooling system to run several simultaneous jobs of any type.References:

[1]

S. Sciutto, AIRES 2.6 User Manual, http://www.fisica.unlp.edu.ar/auger/aires/.

     

Rapid building detection using machine learning

This work describes algorithms for performing discrete object detection, specifically in the case of buildings, where usually only low quality RGB-only geospatial reflective imagery is available. We utilize new candidate search and feature extraction techniques to reduce the problem to a machine learning (ML) classification task. Here we can harness the complex patterns of contrast features contained in training data to establish a model of buildings. We avoid costly sliding windows to generate candidates; instead we innovatively stitch together well known image processing techniques to produce candidates for building detection that cover 80–85 % of buildings. Reducing the number of possible candidates is important due to the scale of the problem. Each candidate is subjected to classification which, although linear, costs time and prohibits large scale evaluation. We propose a candidate alignment algorithm to boost classification performance to 80–90 % precision with a linear time algorithm and show it has negligible cost. Also, we propose a new concept called a Permutable Haar Mesh (PHM) which we use to form and traverse a search space to recover candidate buildings which were lost in the initial preprocessing phase. All code and datasets from this paper are made available online (http://kdl.cs.umb.edu/w/datasets/ and https://github.com/caitlinkuhlman/ObjectDetectionCLUtility).     

Twenty years of artificial life art

This essay begins with discussion of four relatively recent works which are representative of major themes and preoccupations in Artificial Life Art: ‘Propagaciones’ by Leo Nuñez; ‘Sniff’ by Karolina Sobecka and Jim George; ‘Universal Whistling Machine’ by Marc Boehlen; and ‘Performative Ecologies’ by Ruari Glynn. This essay is an attempt to contextualise these works by providing an overview of the history and forms of Artificial Life Art as it has developed over two decades, along with some background in the ideas of the Artificial Life movement of the late 1980s and 1990s.1 A more extensive study of the theoretical history of Artificial Life can be found in my paper ‘Artificial Life Art—A Primer’, in the Proceedings of DAC09 and also at http://www.ace.uci.edu/Penny. Excerpts from that essay are included here.      

The 2-dipath chromatic number of Halin graphs

A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .