An optimal local approximation algorithm for max-min linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0 for nonnegative matrices A and C. We present a local algorithm (constant-time distributed algorithm) for approximating max-min LPs. The approximation ratio of our algorithm is the best possible for any local algorithm; there is a matching unconditional lower bound.

Locally checkable proofs

This work studies decision problems from the perspective of nondeterministic distributed algorithms. For a yes-instance there must exist a proof that can be verified with a distributed algorithm: all nodes must accept a valid proof, and at least one node must reject an invalid proof. We focus on locally checkable proofs that can be verified with a constant-time distributed algorithm. For example, it is easy to prove that a graph is bipartite: the locally checkable proof gives a 2-colouring of the graph, which only takes 1 bit per node. However, it is more difficult to prove that a graph is not bipartite—it turns out that any locally checkable proof requires Ω(log n) bits per node. In this work we classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof. We establish tight or near-tight results for classical graph properties such as the chromatic number. We show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, Θ(1), Θ(log n), or poly(n) bits per node. Among the most difficult graph properties are symmetric graphs, which require Ω(n2) bits per node, and non-3-colourable graphs, which require Ω(n2/log n) bits per node—any pure graph property admits a trivial proof of size O(n2).

FIN-CLARIN: A Framework for Depositing and Disseminating Language Resources for R&D

Researchers and developers in academia and industry would benefit from a facility that enables them to easily locate, licence and use the kind of empirical data they need for testing and refining their hypotheses and to deposit and disseminate their data e.g. to support replication and validation of reported scientific experiments. To answer these needs initially in Finland, there is an ongoing project at University of Helsinki and its collaborators to create a user-friendly web service for researchers and developers in Finland and other countries. In our talk, we describe ongoing work to create a palette of extensive but easily available Finnish language resources and technologies for the research community, including lexical resources, wordnets, morphologically tagged corpora, dependency syntactic treebanks and parsebanks, open-source finite state toolkits and libraries and language models to support text analysis and processing at customer site. Also first publicly available results are presented.

Do wordnets also improve human performance on NLP tasks?

FinnWordNet is a wordnet for Finnish that complies with the format of the Princeton WordNet (PWN) (Fellbaum, 1998). It was built by translating the PrincetonWordNet 3.0 synsets into Finnish by human translators. It is open source and contains 117000 synsets. The Finnish translations were inserted into the PWN structure resulting in a bilingual lexical database. In natural language processing (NLP), wordnets have been used for infusing computers with semantic knowledge assuming that humans already have a sufficient amount of this knowledge. In this paper we present a case study of using wordnets as an electronic dictionary. We tested whether native Finnish speakers benefit from using a wordnet while completing English sentence completion tasks. We found that using either an English wordnet or a bilingual English Finnish wordnet significantly improves performance in the task. This should be taken into account when setting standards and comparing human and computer performance on these tasks.

Open Content Licenses

The EU Directive harmonising copyright, Directive 2001/29/EC, has been implemented in all META-NORD countries. The licensing schemas of open content/open source and META-SHARE as well as CLARIN are discussed shortly. The status of the licensing of tools and resources available at the consortium partners are outlined. The aim of the article is to compare a set of open content and open source license and provide some guidance on the optimal use of licenses provided by META-NET and CLARIN for licensing the tools and resources for the benefit of the language technology community.

Load balancing algorithms for an extended hypercube

Reduction of the execution time of a job through equitable distribution of work load among the processors in a distributed system is the goal of load balancing. Performance of static and dynamic load balancing algorithms for the extended hypercube, is discussed. Threshold algorithms are very well-known algorithms for dynamic load balancing in distributed systems. An extension of the threshold algorithm, called the multilevel threshold algorithm, has been proposed. The hierarchical interconnection network of the extended hypercube is suitable for implementing the proposed algorithm. The new algorithm has been implemented on a transputer-based system and the performance of the algorithm for an extended hypercube is compared with those for mesh and binary hypercube networks

Design of some 2-D filters through the transformation technique

The transformation technique is a tool FIR designing 2-D filters, useful for the design of specially shaped filters with passband/stopband regions not centred around the origin. The authors extend this technique to design two types or filters. A notch filter has a stopband centred about a small region in the 2-D frequency plane. The authors propose an extension to the transformation technique with the windowing concept to achieve the design of notch filters. A directional filter has a passband extending fully along: a straight line pacing through the origin. The transformation technique is: further extended to yield such directional filters. Design and application examples for both these fillers are also presented.

Simple Structural And Bonding Representations Of Fullerenes

Bonding in buckminsterfullerene, C60, can be described in terms of a unique canonical representation in which all six membered rings have a benzenoid Kekule structure while the pentagons are all made of exclusively single bonds. The corresponding valence bond structure reflects the full symmetry of the molecule and is consistent with the observed bond length variations. Computational support for the bonding description is provided using localized MO's obtained at the MNDO level. The requirement of benzenoid structures for all the hexagons can be used as a criterion of stability of fullerenes which complements the pentagon isolation rule. A convenient two-dimensional representation of the fullerene structures incorporating the above bonding description is suggested, especially for use in mechanistic discussions.

Robust controller for an autonomous small refrigeration unit

The authors describe the constructional features of a controller for operating an autonomous refrigeration unit powered by a field of photovoltaic panels and backed up by a generator set. The controller enables three voltage levels of operation of an inverter to meet the start, run and off cycle conditions of the refrigerator compressor. The algorithm considers several input and output parameters and status signals from each subsystem of the unit to deduce a control strategy. Such units find application for storage of vaccines and life-saving medicines requiring uninterrupted refrigeration, in medical shops, rural health centres, veterinary laboratories etc.

Optimal feature extraction for bilingual OCR

Feature extraction in bilingual OCR is handicapped by the increase in the number of classes or characters to be handled. This is evident in the case of Indian languages whose alphabet set is large. It is expected that the complexity of the feature extraction process increases with the number of classes. Though the determination of the best set of features that could be used cannot be ascertained through any quantitative measures, the characteristics of the scripts can help decide on the feature extraction procedure. This paper describes a hierarchical feature extraction scheme for recognition of printed bilingual (Tamil and Roman) text. The scheme divides the combined alphabet set of both the scripts into subsets by the extraction of certain spatial and structural features. Three features viz geometric moments, DCT based features and Wavelet transform based features are extracted from the grouped symbols and a linear transformation is performed on them for the purpose of efficient representation in the feature space. The transformation is obtained by the maximization of certain criterion functions. Three techniques : Principal component analysis, maximization of Fisher's ratio and maximization of divergence measure have been employed to estimate the transformation matrix. It has been observed that the proposed hierarchical scheme allows for easier handling of the alphabets and there is an appreciable rise in the recognition accuracy as a result of the transformations.

Biphasic composite of Tricalcium phosphate reinforced with Hydroxyapatite Whiskers

Biphasic calcium phosphates have received considerable attention due to their optimum dissolution rate in the human body after implantation. These materials are composed of hydroxyapatite (HA) and resorbable tricalcium phosphate (TCP). In the present investigation, HA whiskers are reinforced into TCP to enhance the mechanical properties of this biphasic composite. Various amounts (30-50 wt%) HA whiskers are reinforced in TCP matrix. Microstructural characterization has been carried out using field-emission scanning electron microscope. Mechanical properties have been investigated by microindentation in a universal testing machine (UTM). As TCP is resorbable, it will dissolve in body fluid and there is a strong possibility for the faceted HA whiskers to interact with functional groups present in the body fluid surroundings.

Photocatalytic activity of ZnO nanostructured film grown by activated reactive

ZnO nanostructured films were deposited at room temperature on glass substrates and cotton fabrics by activated reactive evaporation in a single step without using metal catalyst or templates. Morphological observation has shown that the nanostructured film contains seaurchin-like structures, and this seaurchin containing large number of randomly grown ZnO nanoneedles. Microstructural analysis revealed the single crystalline nature of the grown nanoneedles and their growth direction was indentified to be along [0002]. PL spectrum of nanostructured films has shown a relatively weak near-band-edge emission peak at 380 nm, and a significant broad peak at 557 nm due to the oxygen vacancy-related emission. ZnO nanostructured films grown on glass substrates and cotton fabrics have shown good photocatalytic activity against rhodamine B.

A General Route to Nanoparticle Thin Films and Coatings

Nanoparticles thin films have wide range of applications such as nanoelectronics, magnetic storage devices, SERS substrate fabrication, optical grating and antireflective coating. Present work describes a method to prepare large area nanoparticles thin film of the order of few square centimeters. Thin film deposition has been done successfully on a wide range of conducting as well as non conducting substrates such as carbon-coated copper grid, silicon, m-plane of alumina, glass and (100) plane of NaCl single crystal. SEM, TEM and AFM studies have been done for microstructural characterization of the thin films. A basic mechanism has been proposed towards the understanding of the deposition process.