Refine
Year of publication
Document Type
- Article (31483)
- Part of Periodical (11568)
- Book (8325)
- Doctoral Thesis (5736)
- Part of a Book (3969)
- Working Paper (3387)
- Review (2940)
- Contribution to a Periodical (2368)
- Preprint (2232)
- Report (1560)
Language
- German (42872)
- English (29725)
- French (1060)
- Portuguese (840)
- Spanish (309)
- Croatian (302)
- Multiple languages (263)
- Italian (198)
- mis (174)
- Turkish (168)
Has Fulltext
- yes (76235) (remove)
Keywords
- Deutsch (1076)
- Literatur (868)
- taxonomy (768)
- Deutschland (553)
- Rezension (511)
- new species (453)
- Rezeption (354)
- Frankfurt <Main> / Universität (341)
- Übersetzung (329)
- Geschichte (300)
Institute
- Medizin (7777)
- Präsidium (5215)
- Physik (4591)
- Extern (2738)
- Wirtschaftswissenschaften (2698)
- Gesellschaftswissenschaften (2374)
- Biowissenschaften (2198)
- Biochemie und Chemie (1978)
- Frankfurt Institute for Advanced Studies (FIAS) (1774)
- Center for Financial Studies (CFS) (1630)
Algorithms for the Maximum Cardinality Matching Problem which greedily add edges to the solution enjoy great popularity. We systematically study strengths and limitations of such algorithms, in particular of those which consider node degree information to select the next edge. Concentrating on nodes of small degree is a promising approach: it was shown, experimentally and analytically, that very good approximate solutions are obtained for restricted classes of random graphs. Results achieved under these idealized conditions, however, remained unsupported by statements which depend on less optimistic assumptions.
The KarpSipser algorithm and 1-2-Greedy, which is a simplified variant of the well-known MinGreedy algorithm, proceed as follows. In each step, if a node of degree one (resp. at most two) exists, then an edge incident with a minimum degree node is picked, otherwise an arbitrary edge is added to the solution.
We analyze the approximation ratio of both algorithms on graphs of degree at most D. Families of graphs are known for which the expected approximation ratio converges to 1/2 as D grows to infinity, even if randomization against the worst case is used. If randomization is not allowed, then we show the following convergence to 1/2: the 1-2-Greedy algorithm achieves approximation ratio (D-1)/(2D-3); if the graph is bipartite, then the more restricted KarpSipser algorithm achieves the even stronger factor D/(2D-2). These guarantees set both algorithms apart from other famous matching heuristics like e.g. Greedy or MRG: these algorithms depend on randomization to break the 1/2-barrier even for paths with D=2. Moreover, for any D our guarantees are strictly larger than the best known bounds on the expected performance of the randomized variants of Greedy and MRG.
To investigate whether KarpSipser or 1-2-Greedy can be refined to achieve better performance, or be simplified without loss of approximation quality, we systematically study entire classes of deterministic greedy-like algorithms for matching. Therefore we employ the adaptive priority algorithm framework by Borodin, Nielsen, and Rackoff: in each round, an adaptive priority algorithm requests one or more edges by formulating their properties---like e.g. "is incident with a node of minimum degree"---and adds the received edges to the solution. No constraints on time and space usage are imposed, hence an adaptive priority algorithm is restricted only by its nature of picking edges in a greedy-like fashion. If an adaptive priority algorithm requests edges by processing degree information, then we show that it does not surpass the performance of KarpSipser: our D/(2D-2)-guarantee for bipartite graphs is tight and KarpSipser is optimal among all such "degree-sensitive" algorithms even though it uses degree information merely to detect degree-1 nodes. Moreover, we show that if degrees of both nodes of an edge may be processed, like e.g. the Double-MinGreedy algorithm does, then the performance of KarpSipser can only be increased marginally, if at all. Of special interest is the capability of requesting edges not only by specifying the degree of a node but additionally its set of neighbors. This enables an adaptive priority algorithm to "traverse" the input graph. We show that on general degree-bounded graphs no such algorithm can beat factor (D-1)/(2D-3). Hence our bound for 1-2-Greedy is tight and this algorithm performs optimally even though it ignores neighbor information. Furthermore, we show that an adaptive priority algorithm deteriorates to approximation ratio exactly 1/2 if it does not request small degree nodes. This tremendous decline of approximation quality happens for graphs on which 1-2-Greedy and KarpSipser perform optimally, namely paths with D=2. Consequently, requesting small degree nodes is vital to beat factor 1/2.
Summarizing, our results show that 1-2-Greedy and KarpSipser stand out from known and hypothetical algorithms as an intriguing combination of both approximation quality and conceptual simplicity.
Dokumentation von Best-Practice-Beispielen zum Umgang mit dem Fahren ohne (gültigen) Fahrschein
(2016)
In Deutschland und Europa versuchen Verkehrsunternehmen und -verbünde bereits seit längerer Zeit gegen das Fahren ohne (gültigen) Fahrschein vorzugehen, ihre Fahrgeldeinnahmen zu sichern und zu steigern sowie die Quote der Personen, die den ÖPNV ohne (gültiges) Ticket nutzen, zu minimieren. Auf Grundlage des ersten Arbeitspaketes (Literaturanalyse zum Stand der Forschung: Schwerdtfeger et al. 2016) wurden Maßnahmen untersucht, die zum Erreichen der genannten Ziele beitragen. Der Fokus liegt dabei auf Best Practice Beispielen, also Maßnahmen, die in der Praxis als erfolgreich hinsichtlich der Reduzierung des Fahrens ohne (gültigen) Fahrschein sowie hinsichtlich der Einnahmesicherung und -steigerung angesehen werden. Das Ergebnis der Untersuchung ist eine umfangreiche Auseinandersetzung mit Best Practice Beispielen in Bezug auf das Fahren ohne (gültigen) Fahrschein. Außerdem wurden aktuell diskutierte Ansätze alternativer Finanzierungsinstrumente hinsichtlich ihrer Eignung zur Finanzierung des ÖPNV untersucht. Zwar können alternative Finanzierungsinstrumente derzeit noch nicht als Best Practice eingestuft werden, allerdings stehen sie in direkter Beziehung zur Einnahmesicherung im ÖPNV-Sektor.
The Multilingual Assessment Instrument for Narratives (MAIN) was designed in order to assess narrative skills in children who acquire one or more languages from birth or from early age. MAIN is suitable for children from 3 to 10 years and evaluates both comprehension and production of narratives. Its design allows for the assessment of several languages in the same child, as well as for different elicitation modes: Model Story, Retelling, and Telling. MAIN contains four parallel stories, each with a carefully designed six-picture sequence. The stories are controlled for cognitive and linguistic complexity, parallelism in macrostructure and microstructure, as well as for cultural appropriateness and robustness. The instrument has been developed on the basis of extensive piloting with more than 550 monolingual and bilingual children aged 3 to 10, for 15 different languages and language combinations. Even though MAIN has not been norm-referenced yet, its standardized procedures can be used for evaluation, intervention and research purposes. MAIN is currently available in the following languages: English, Afrikaans, Albanian, Basque, Bulgarian, Croatian, Cypriot Greek, Danish, Dutch, Estonian, Finnish, French, German, Greek, Hebrew, Icelandic, Italian, Lithuanian, Norwegian, Polish, Russian, Spanish, Standard Arabic, Swedish, Turkish, Vietnamese, and Welsh.
BACKGROUND: Acetogenic bacteria are able to use CO2 as terminal electron acceptor of an anaerobic respiration, thereby producing acetate with electrons coming from H2. Due to this feature, acetogens came into focus as platforms to produce biocommodities from waste gases such as H2+CO2 and/or CO. A prerequisite for metabolic engineering is a detailed understanding of the mechanisms of ATP synthesis and electron-transfer reactions to ensure redox homeostasis. Acetogenesis involves the reduction of CO2 to acetate via soluble enzymes and is coupled to energy conservation by a chemiosmotic mechanism. The membrane-bound module, acting as an ion pump, was of special interest for decades and recently, an Rnf complex was shown to couple electron flow from reduced ferredoxin to NAD+ with the export of Na+ in Acetobacterium woodii. However, not all acetogens have rnf genes in their genome. In order to gain further insights into energy conservation of non-Rnf-containing, thermophilic acetogens, we sequenced the genome of Thermoanaerobacter kivui.
RESULTS: The genome of Thermoanaerobacter kivui comprises 2.9 Mbp with a G+C content of 35% and 2,378 protein encoding orfs. Neither autotrophic growth nor acetate formation from H2+CO2 was dependent on Na+ and acetate formation was inhibited by a protonophore, indicating that H+ is used as coupling ion for primary bioenergetics. This is consistent with the finding that the c subunit of the F1FO ATP synthase does not have the conserved Na+ binding motif. A search for potential H+-translocating, membrane-bound protein complexes revealed genes potentially encoding two different proton-reducing, energy-conserving hydrogenases (Ech).
CONCLUSIONS: The thermophilic acetogen T. kivui does not use Na+ but H+ for chemiosmotic ATP synthesis. It does not contain cytochromes and the electrochemical proton gradient is most likely established by an energy-conserving hydrogenase (Ech). Its thermophilic nature and the efficient conversion of H2+CO2 make T. kivui an interesting acetogen to be used for the production of biocommodities in industrial micobiology. Furthermore, our experimental data as well as the increasing number of sequenced genomes of acetogenic bacteria supported the new classification of acetogens into two groups: Rnf- and Ech-containing acetogens.
In the 1960s, theoretical concepts prepared the path to nuclear matter with proton and neutron numbers far beyond the nuclei known at that time. The new laboratory GSI was founded for research on reactions with heavy ions, in particular those for production of the predicted super-heavy nuclei. In this contribution it is presented how the interaction between experiment and theory resulted in a continuous improvement of the experimental set-ups on the one hand, and of the knowledge of the processes during the nuclear reaction and of the properties of the produced nuclei on the other hand. In the course of this work six new elements from 107 to 112 were produced and identified. An overview of the present status of experimental results and a comparison with theoretical interpretations is given.
Background: Due to the steadily increasing number of cancer patients worldwide the early diagnosis and treatment of cancer is a major field of research. The diagnosis of cancer is mostly performed by an experienced pathologist via the visual inspection of histo-pathological stained tissue sections. To save valuable time, low quality cryosections are frequently analyzed with diagnostic accuracies that are below those of high quality embedded tissue sections. Thus, alternative means have to be found that enable for fast and accurate diagnosis as the basis of following clinical decision making.
Methods: In this contribution we will show that the combination of the three label-free non-linear imaging modalities CARS (coherent anti-Stokes Raman-scattering), TPEF (two-photon excited autofluorescence) and SHG (second harmonic generation) yields information that can be translated into computational hematoxylin and eosin (HE) images by multivariate statistics. Thereby, a computational HE stain is generated resulting in pseudo-HE overview images that allow for identification of suspicious regions. The latter are analyzed further by Raman-spectroscopy retrieving the tissue’s molecular fingerprint.
Results: The results suggest that the combination of non-linear multimodal imaging and Raman-spectroscopy possesses the potential as a precise and fast tool in routine histopathology.
Conclusions: As the key advantage, both optical methods are non-invasive enabling for further pathological investigations of the same tissue section, e.g. a direct comparison with the current pathological gold-standard.
We present techniques to prove termination of cycle rewriting, that is, string rewriting on cycles, which are strings in which the start and end are connected. Our main technique is to transform cycle rewriting into string rewriting and then apply state of the art techniques to prove termination of the string rewrite system. We present three such transformations, and prove for all of them that they are sound and complete. In this way not only termination of string rewriting of the transformed system implies termination of the original cycle rewrite system, a similar conclusion can be drawn for non-termination. Apart from this transformational approach, we present a uniform framework of matrix interpretations, covering most of the earlier approaches to automatically proving termination of cycle rewriting. All our techniques serve both for proving termination and relative termination. We present several experiments showing the power of our techniques.
Profiles of CFC-11 (CCl3F) and CFC-12 (CCl2F2) of the Michelson Interferometer for Passive Atmospheric Sounding (MIPAS) aboard the European satellite Envisat have been retrieved from versions MIPAS/4.61 to MIPAS/4.62 and MIPAS/5.02 to MIPAS/5.06 level-1b data using the scientific level-2 processor run by Karlsruhe Institute of Technology (KIT), Institute of Meteorology and Climate Research (IMK) and Consejo Superior de Investigaciones Científicas (CSIC), Instituto de Astrofísica de Andalucía (IAA). These profiles have been compared to measurements taken by the balloon-borne cryosampler, Mark IV (MkIV) and MIPAS-Balloon (MIPAS-B), the airborne MIPAS-STRatospheric aircraft (MIPAS-STR), the satellite-borne Atmospheric Chemistry Experiment Fourier transform spectrometer (ACE-FTS) and the High Resolution Dynamic Limb Sounder (HIRDLS), as well as the ground-based Halocarbon and other Atmospheric Trace Species (HATS) network for the reduced spectral resolution period (RR: January 2005–April 2012) of MIPAS. ACE-FTS, MkIV and HATS also provide measurements during the high spectral resolution period (full resolution, FR: July 2002–March 2004) and were used to validate MIPAS CFC-11 and CFC-12 products during that time, as well as profiles from the Improved Limb Atmospheric Spectrometer, ILAS-II. In general, we find that MIPAS shows slightly higher values for CFC-11 at the lower end of the profiles (below ∼ 15 km) and in a comparison of HATS ground-based data and MIPAS measurements at 3 km below the tropopause. Differences range from approximately 10 to 50 pptv ( ∼ 5–20 %) during the RR period. In general, differences are slightly smaller for the FR period. An indication of a slight high bias at the lower end of the profile exists for CFC-12 as well, but this bias is far less pronounced than for CFC-11 and is not as obvious in the relative differences between MIPAS and any of the comparison instruments. Differences at the lower end of the profile (below ∼ 15 km) and in the comparison of HATS and MIPAS measurements taken at 3 km below the tropopause mainly stay within 10–50 pptv (corresponding to ∼ 2–10 % for CFC-12) for the RR and the FR period. Between ∼ 15 and 30 km, most comparisons agree within 10–20 pptv (10–20 %), apart from ILAS-II, which shows large differences above ∼ 17 km. Overall, relative differences are usually smaller for CFC-12 than for CFC-11. For both species – CFC-11 and CFC-12 – we find that differences at the lower end of the profile tend to be larger at higher latitudes than in tropical and subtropical regions. In addition, MIPAS profiles have a maximum in their mixing ratio around the tropopause, which is most obvious in tropical mean profiles. Comparisons of the standard deviation in a quiescent atmosphere (polar summer) show that only the CFC-12 FR error budget can fully explain the observed variability, while for the other products (CFC-11 FR and RR and CFC-12 RR) only two-thirds to three-quarters can be explained. Investigations regarding the temporal stability show very small negative drifts in MIPAS CFC-11 measurements. These instrument drifts vary between ∼ 1 and 3 % decade−1. For CFC-12, the drifts are also negative and close to zero up to ∼ 30 km. Above that altitude, larger drifts of up to ∼ 50 % decade−1 appear which are negative up to ∼ 35 km and positive, but of a similar magnitude, above.
The geminal frustrated Lewis pair tBu2PCH2B(Fxyl)2 (1; Fxyl=3,5-(CF3)2C6H3) is accessible in 65 % yield from tBu2PCH2Li and (Fxyl)2BF. According to NMR spectroscopy and X-ray crystallography, 1 is monomeric both in solution and in the solid state. The intramolecular P⋅⋅⋅B distance of 2.900(5) Å and the full planarity of the borane site exclude any significant P/B interaction. Compound 1 readily activates a broad variety of substrates including H2, EtMe2SiH, CO2/CS2, Ph2CO, and H3CCN. Terminal alkynes react with heterolysis of the C−H bond. Haloboranes give cyclic adducts with strong P−BX3 and weak R3B−X bonds. Unprecedented transformations leading to zwitterionic XP/BCX3 adducts occur on treatment of 1 with CCl4 or CBr4 in Et2O. In less polar solvents (C6H6, n-pentane), XP/BCX3 adduct formation is accompanied by the generation of significant amounts of XP/BX adducts. FLP 1 catalyzes the hydrogenation of PhCH=NtBu and the hydrosilylation of Ph2CO with EtMe2SiH.
In the complex network of nuclear hormone receptors, the long non-coding RNAs (lncRNAs) are emerging as critical determinants of hormone action. Here we investigated the involvement of selected cancer-associated lncRNAs in Estrogen Receptor (ER) signaling. Prior studies by Chromatin Immunoprecipitation (ChIP) Sequencing showed that in prostate cancer cells ERs form a complex with the endothelial nitric oxide synthase (eNOS) and that in turn these complexes associate with chromatin in an estrogen-dependent fashion. Among these associations (peaks) we focused our attention on those proximal to the regulatory region of HOTAIR and MALAT1. These transcripts appeared regulated by estrogens and able to control ERs function by interacting with ERα/ERβ as indicated by RNA-ChIP. Further studies performed by ChIRP revealed that in unstimulated condition, HOTAIR and MALAT1 were present on pS2, hTERT and HOTAIR promoters at the ERE/eNOS peaks. Interestingly, upon treatment with17β-estradiol HOTAIR recruitment to chromatin increased significantly while that of MALAT1 was reduced, suggesting an opposite regulation and function for these lncRNAs. Similar results were obtained in cells and in an ex vivo prostate organotypic slice cultures. Overall, our data provide evidence of a crosstalk between lncRNAs, estrogens and estrogen receptors in prostate cancer with important consequences on gene expression regulation.