Approximating

We prove the Minimum Vertex Cover problem to be NPhard to approximate to within a factor of 1.3606, extending on previous PCP and hardness of approximation technique. To that end, one needs to develop a new proof framework, and to borrow and extend ideas from several ﬁelds. 1. Introduction The basic purpose of computational complexity theory is to classify computational problems according to the amount of resources required to solve them. In particular, the most basic task is to classify computational problems to those that are eﬃciently solvable and those that are not. ...
48p noel_noel 17012013 32 5 Download

We prove that the classical Oka property of a complex manifold Y, concerning the existence and homotopy classiﬁcation of holomorphic mappings from Stein manifolds to Y, is equivalent to a Runge approximation property for holomorphic maps from compact convex sets in Euclidean spaces to Y . Introduction Motivated by the seminal works of Oka [40] and Grauert ([24], [25], [26]) we say that a complex manifold Y enjoys the Oka property if for every Stein manifold X, every compact O(X)convex subset K of X and every continuous map f0 : X → Y which is holomorphic in an...
20p noel_noel 17012013 29 5 Download

Sums of two squares near perfect squares by R. C. Vaughan∗∗∗ In memory of Pritish Limani (1983–2003) Abstract Let C be a nondegenerate planar curve and for a real, positive decreasing function ψ let C(ψ) denote the set of simultaneously ψapproximable points lying on C. We show that C is of Khintchine type for divergence; i.e. if a certain sum diverges then the onedimensional Lebesgue measure on C of C(ψ) is full. We also obtain the Hausdorﬀ measure analogue of the divergent Khintchine type result. ...
61p noel_noel 17012013 26 5 Download

This paper proposes a new method for approximate string search, speciﬁcally candidate generation in spelling error correction, which is a task as follows. Given a misspelled word, the system ﬁnds words in a dictionary, which are most “similar” to the misspelled word. The paper proposes a probabilistic approach to the task, which is both accurate and efﬁcient. The approach includes the use of a log linear model, a method for training the model, and an algorithm for ﬁnding the top k candidates. ...
10p hongdo_1 12042013 16 4 Download

Although adequate models of human language for syntactic analysis and semantic interpretation are of at least contextfree complexity, for applications such as speech processing in which speed is important finitestate models are often preferred. These requirements may be reconciled by using the more complex grammar to automatically derive a finitestate approximation which can then be used as a filter to guide speech recognition or to reject many hypotheses at an early stage of processing.
8p bunthai_1 06052013 19 4 Download

This paper describes the conversion of a Hidden Markov Model into a sequential transducer that closely approximates the behavior of the stochastic model. This transformation is especially advantageous for partofspeech tagging because the resulting transducer can be composed with other transducers that encode correction rules for the most frequent tagging errors. The speed of tagging is also improved. The described methods have been implemented and successfully tested on six languages.
8p bunthai_1 06052013 23 3 Download

We present a novel PCFGbased architecture for robust probabilistic generation based on widecoverage LFG approximations (Cahill et al., 2004) automatically extracted from treebanks, maximising the probability of a tree given an fstructure. We evaluate our approach using stringbased evaluation. We currently achieve coverage of 95.26%, a BLEU score of 0.7227 and string accuracy of 0.7476 on the PennII WSJ Section 23 sentences of length ≤20. grammar for generation.
8p hongvang_1 16042013 21 2 Download

This paper shows how ﬁnite approximations of long distance dependency (LDD) resolution can be obtained automatically for widecoverage, robust, probabilistic LexicalFunctional Grammar (LFG) resources acquired from treebanks. We extract LFG subcategorisation frames and paths linking LDD reentrancies from fstructures generated automatically for the PennII treebank trees and use them in an LDD resolution algorithm to parse new text.
8p bunbo_1 17042013 35 2 Download

This paper describes how to construct a finitestate machine (FSM) approximating a 'unificationbased' grammar using a leftcorner grammar transform. The approximation is presented as a series of grammar transforms, and is exact for leftlinear and rightlinear CFGs, and for trees up to a userspecified depth of centerembedding.
5p bunrieu_1 18042013 18 2 Download

In this paper we extend the maximum spanning tree (MST) dependency parsing framework of McDonald et al. (2005c) to incorporate higherorder feature representations and allow dependency structures with multiple parents per word. We show that those extensions can make the MST framework computationally intractable, but that the intractability can be circumvented with new approximate parsing algorithms. We conclude with experiments showing that discriminative online learning using those approximate algorithms achieves the best reported parsing accuracy for Czech and Danish. ...
8p bunthai_1 06052013 21 2 Download

This book presents a mathematical development of a recent approach to the modeling and simulation of turbulent flows based on methods for the approximate solution of inverse problems. The resulting Approximate Deconvolution Models or ADMs have some advantages (as well as some disadvantages) over more commonly used turbulence models: ADMs are supported by a mathematically rigorous theoretical foundation. ADMs are a family of models of increasing accuracy O(δ2N+2), where δ is the averaging (or filter) radius...
190p hotmoingay 04012013 17 1 Download

We present a novel framework for automated extraction and approximation of numerical object attributes such as height and weight from the Web. Given an objectattribute pair, we discover and analyze attribute information for a set of comparable objects in order to infer the desired value. This allows us to approximate the desired numerical values even when no exact values can be found in the text.
10p hongdo_1 12042013 14 1 Download

We present a linguisticallymotivated algorithm for reconstructing nonlocal dependency in broadcoverage contextfree parse trees derived from treebanks. We use an algorithm based on loglinear classiﬁers to augment and reshape contextfree trees so as to reintroduce underlying nonlocal dependencies lost in the contextfree approximation. We ﬁnd that our algorithm compares favorably with prior work on English using an existing evaluation metric, and also introduce and argue for a new dependencybased evaluation metric. ...
8p bunbo_1 17042013 21 1 Download

Phrasestructure grammars are an effective representation for important syntactic and semantic aspects of natural languages, but are computationally too demanding for use as language models in realtime speech recognition. An algorithm is described that computes finitestate approximations for contextfree grammars and equivalent augmented phrasestructure grammar formalisms. The approximation is exact for certain contextfree grammars generating regular languages, including all leftlinear and rightlinear contextfree grammars. ...
10p bunmoc_1 20042013 10 1 Download

We introduce cube summing, a technique that permits dynamic programming algorithms for summing over structures (like the forward and inside algorithms) to be extended with nonlocal features that violate the classical structural independence assumptions. It is inspired by cube pruning (Chiang, 2007; Huang and Chiang, 2007) in its computation of nonlocal features dynamically using scored kbest lists, but also maintains additional residual quantities used in calculating approximate marginals. ...
9p bunthai_1 06052013 18 1 Download

Chapter 11 "Approximation Algorithms" include all of the following: Load balancing, center selection, pricing method: vertex cover, LP rounding: vertex cover, generalized load balancing, knapsack problem.
62p youcanletgo_03 14012016 11 1 Download

This chapter examines methods of deriving approximate solutions to problems or of approximating exact solutions, which allow us to develop concise and precise estimates of quantities of interest when analyzing algorithms.
43p allbymyself_08 22022016 8 1 Download

In this paper, the authors analyze and compare two existing approximation approaches that are considered as the most suitable for the sensor network, namely the gridbased and the convexhullbased approaches.
20p dieutringuyen 07062017 1 1 Download

Top 200 Words in the GRE and other words which are related or similar in meaning to them are grouped together so that you can learn it easier. The words are given along with it's meaning, a sentence in which it is used and also the words similar in meaning are given. A total of approximately 1500 words will be covered in just this one article. You must learn this if you want to do well... ABATE: to reduce in amount, degree, or severity As the hurricane's force ABATED, the winds dropped and the sea became calm. Words with similar meanings: EBB LAPSE LET...
34p luatgd 13062011 194 61 Download

Many problems of practical significance are NPcomplete but are too important to abandon merely because obtaining an optimal solution is intractable (khó). If a problem is NPcomplete, we are unlikely to find a polynomial time algorithm for solving it exactly, but it may still be possible to find nearoptimal solution in polynomial time.
22p lucky156 04062010 126 18 Download