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.

Local approximability of max-min and min-max linear programs

In a max-min LP, the objective is to maximise ω subject to Ax ≤ 1, Cx ≥ ω1, and x ≥ 0. In a min-max LP, the objective is to minimise ρ subject to Ax ≤ ρ1, Cx ≥ 1, and x ≥ 0. The matrices A and C are nonnegative and sparse: each row ai of A has at most ΔI positive elements, and each row ck of C has at most ΔK positive elements. We study the approximability of max-min LPs and min-max LPs in a distributed setting; in particular, we focus on local algorithms (constant-time distributed algorithms). We show that for any ΔI ≥ 2, ΔK ≥ 2, and ε > 0 there exists a local algorithm that achieves the approximation ratio ΔI (1 − 1/ΔK) + ε. We also show that this result is the best possible: no local algorithm can achieve the approximation ratio ΔI (1 − 1/ΔK) for any ΔI ≥ 2 and ΔK ≥ 2.

"Kyl mä varmaan kohta ymmärrän." : Asunnon suunnittelu -opetusohjelma oppilaiden ajattelun ja oppimisen haastajana peruskoulun kotitalousopetuksessa

"I will soon understand." The House Planning Program as an Enhancer of Pupils´ Thinking Skills and Learning in Home Economics at Comprehensive School The aim of the research was to build a study program for home economics education in order to enhance pupils´ thinking skills. The program was based on the intervention programs or strategies known as Cognitive Acceleration (CA), which are founded on the theories of Jean Piaget, Lev Vygotsky, and Reuven Feuerstein. In addition, Carl Bereiter s theory of knowledge building was integrated to the research. The viewpoint of home economics was based on the multidimensional foundation of home economics science, particularly household technology and house planning. I first analyzed the kind of body of knowledge home economics science and home economics education provides for enhancing thinking skills in home economics. For the study, a CATE (Cognitive Acceleration through Technology Education) program was adapted and modified and a House Planning program was created for home economics classes. The house planning program consisted of five lessons during which pupils learned how to make functional floor plans as well as choose furniture, household appliances and materials for the home. In order to obtain the required data, various classroom experiments were arranged in 2005 with grade 9 pupils at a comprehensive school in Helsinki. All the experiments were videotaped, and five hours of the videotaped material was edited and transcribed for closer examination. The material consisted of all the video-recorded activity of the selected study group. Interaction study and content analysis were used to analyze the data. Following the experiments, a small survey was conducted to solicit pupils´ and teacher´s opinions of the program. The analysis sheds light on the nature of pupils´ interaction and knowledge building in small group activity. Special attention was given to tracking pupils´ interaction during the socalled construction zone activity. The models and qualities of teacher´s aid and support during the lessons were examined as well. The results revealed the versatility of the pupils social interaction and common knowledge building that occurred during the small group activity. The pupils discussions, including their arguments, their sharing of ideas, and the multiple perspectives that emerged reflected home economics knowledge building. The construction zone activity appeared through expressions of cognitive conflict and metacognition. Cognitive conflict was evident in the pupils´ words and involved questioning, doubting and disputing. The metacognitive activity emerged by thinking aloud, choosing the strategies, and negotiating the results. The pupils also coordinated their activity, allocated the responsibility, and systematized their work. The teacher assisted by preparing new themes for the pupils and by participating in the small group work. The teacher´s help during the small group sessions strengthened the pupils activity in the construction zone. The results showed that one can utilize the wide multidisciplinary basis of home economics, which includes scientific knowledge but also the knowledge derived from practical activity and experience. In this study practical activity was undertaken as a planning project the result of which was a plan or a new vision for the house planning situation. The study showed that the House Planning program was able to enhance the pupils´ social interaction and collaboration. The learning environment challenged the pupils in a way that could be a gateway to further developing their thinking skills. The method of analysis created in the study could be a potential tool for examining social interaction, construction zone activity, and knowledge building in other learning environments as well. Key words: home economics, house planning, classroom experiment, thinking skills,cognitive conflict, metacognition, social interaction, knowledge building

A note on resolving infeasibility in linear programs by constraint relaxation

We study the problem of finding a set of constraints of minimum cardinality which when relaxed in an infeasible linear program, make it feasible. We show the problem is NP-hard even when the constraint matrix is totally unimodular and prove polynomial-time solvability when the constraint matrix and the right-hand-side together form a totally unimodular matrix.

Forest policies and programs affecting vulnerability and adaptation to climate change

Due to large scale afforestation programs and forest conservation legislations, India's total forest area seems to have stabilized or even increased. In spite of such efforts, forest fragmentation and degradation continues, with forests being subject to increased pressure due to anthropogenic factors. Such fragmentation and degradation is leading to the forest cover to change from very dense to moderately dense and open forest and 253 km(2) of very dense forest has been converted to moderately dense forest, open forest, scrub and non-forest (during 2005-2007). Similarly, there has been a degradation of 4,120 km(2) of moderately dense forest to open forest, scrub and non-forest resulting in a net loss of 936 km(2) of moderately dense forest. Additionally, 4,335 km(2) of open forest have degraded to scrub and non-forest. Coupled with pressure due to anthropogenic factors, climate change is likely to be an added stress on forests. Forest sector programs and policies are major factors that determine the status of forests and potentially resilience to projected impacts of climate change. An attempt is made to review the forest policies and programs and their implications for the status of forests and for vulnerability of forests to projected climate change. The study concludes that forest conservation and development policies and programs need to be oriented to incorporate climate change impacts, vulnerability and adaptation.

Intracellular Pathogen Sensor NOD2 Programs Macrophages to Trigger Notch1 Activation

Intracellular pathogen sensor, NOD2, has been implicated in regulation of wide range of anti-inflammatory responses critical during development of a diverse array of inflammatory diseases; however, underlying molecular details are still imprecisely understood. In this study, we demonstrate that NOD2 programs macrophages to trigger Notch1 signaling. Signaling perturbations or genetic approaches suggest signaling integration through cross-talk between Notch1-PI3K during the NOD2-triggered expression of a multitude of immunological parameters including COX-2/PGE(2) and IL-10. NOD2 stimulation enhanced active recruitment of CSL/RBP-Jk on the COX-2 promoter in vivo. Intriguingly, nitric oxide assumes critical importance in NOD2-mediated activation of Notch1 signaling as iNOS(-/-) macrophages exhibited compromised ability to execute NOD2-triggered Notch1 signaling responses. Correlative evidence demonstrates that this mechanism operates in vivo in brain and splenocytes derived from wild type, but not from iNOS(-/-) mice. Importantly, NOD2-driven activation of the Notch1-PI3K signaling axis contributes to its capacity to impart survival of macrophages against TNF-alpha or IFN-gamma-mediated apoptosis and resolution of inflammation. Current investigation identifies Notch1-PI3K as signaling cohorts involved in the NOD2-triggered expression of a battery of genes associated with anti-inflammatory functions. These findings serve as a paradigm to understand the pathogenesis of NOD2-associated inflammatory diseases and clearly pave a way toward development of novel therapeutics.

Toeplitz Operators with Special Symbols on Segal-Bargmann Spaces

We study the boundedness of Toeplitz operators on Segal-Bargmann spaces in various contexts. Using Gutzmer's formula as the main tool we identify symbols for which the Toeplitz operators correspond to Fourier multipliers on the underlying groups. The spaces considered include Fock spaces, Hermite and twisted Bergman spaces and Segal-Bargmann spaces associated to Riemannian symmetric spaces of compact type.