Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older editNewer edit →
mNo edit summary
mNo edit summary
Line 1: Line 1:
{{About|scientific estimates of the age of the universe|religious and other non-scientific estimates|Dating creation}}
The '''set covering problem''' ('''SCP''') is a classical question in [[combinatorics]], [[computer science]] and [[Computational complexity theory|complexity theory]].
{{Cosmology}}


In [[physical cosmology]], the '''age of the universe''' is the [[cosmological time|time]] elapsed since the [[Big Bang]]. The [[Planck (spacecraft)#2013 data release|best measurement]] of the age of the universe is {{val|13.798|0.037}} billion years ({{val|13.798|0.037|e=9}} years or {{val|4.354|0.012|e=17}} seconds) within the [[Lambda-CDM model|Lambda-CDM concordance model]].<ref name='planck_overview'>
It is a problem "whose study has led to the development of fundamental techniques for the entire field" of [[approximation algorithms]].<ref>{{harvtxt|Vazirani|2001|p=15}}</ref> It was also one of [[Karp's 21 NP-complete problems]] shown to be [[NP-complete]] in 1972.
{{cite arXiv
|author=Planck Collaboration
|year=2013
|title=Planck 2013 results. I. Overview of products and scientific results
|class=astro-ph.CO
|eprint=1303.5062
}}</ref><ref name="arxiv-20121220">
{{cite arXiv
|last=Bennett |first=C.L.
|author2=''et al.''
|year=2013
|title=Nine-Year Wilkinson Microwave Anisotropy Probe (WMAP) Observations: Final Maps and Results
|eprint=1212.5225
|class=astro-ph.CO
}}</ref> The [[measurement uncertainty|uncertainty]] of 37 million years has been obtained by the agreement of a number of scientific research projects, such as [[microwave background radiation]] [[measurement]]s by the [[Planck satellite]], the [[Wilkinson Microwave Anisotropy Probe]] and other probes. Measurements of the cosmic background radiation give the cooling time of the [[universe]] since the Big Bang,<ref name="arxiv-20121220" /> and measurements of the [[Red shift#Extragalactic observations|expansion rate]] of the universe can be used to calculate its approximate age by extrapolating backwards in time.


== Explanation ==
Given a set of elements <math>\{1,2,...,m\}</math> (called the universe) and a set <math>S</math> of <math>n</math> sets whose union equals the universe, the set cover problem is to identify the smallest subset of <math>S</math> whose union equals the universe. For example, consider the universe <math>U = \{1, 2, 3, 4, 5\}</math> and the set of sets <math>S = \{\{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\}\}</math>. Clearly the union of <math>S</math> is <math>U</math>. However, we can cover all of the elements with the following, smaller number of sets: <math>\{\{1, 2, 3\}, \{4, 5\}\}</math>.
The [[Lambda-CDM model|Lambda-CDM concordance model]] describes the evolution of the universe from a very uniform, hot, dense primordial state to its present state over a span of about 13.8 billion years<ref>{{cite web
|date=2 April 2013
|title=Cosmic Detectives
|url=http://www.esa.int/Our_Activities/Space_Science/Cosmic_detectives
|publisher=[[European Space Agency]]
|accessdate=2013-04-15
}}</ref> of [[cosmological time]]. This model is well understood theoretically and strongly supported by recent high-precision astronomical observations such as [[WMAP]]. In contrast, theories of the origin of the primordial state remain very speculative. If one extrapolates the Lambda-CDM model backward from the earliest well-understood state, it quickly (within a small fraction of a second) reaches a [[Gravitational singularity|singularity]] called the "Big Bang singularity." This singularity is not understood as having a physical significance in the usual sense, but it is convenient to quote times measured "since the Big Bang" even though they do not correspond to a physically measurable time. For example, "10<sup>−6</sup> seconds after the Big Bang" is a well-defined era in the universe's evolution. If one referred to the same era as "13.8 billion years minus 10<sup>−6</sup> seconds ago," the precision of the meaning would be lost because the minuscule latter time interval is swamped by uncertainty in the former.


Though the universe might in theory have a longer history, the [[International Astronomical Union]]<ref>
More formally, given a universe <math>\mathcal{U}</math> and a family <math>\mathcal{S}</math> of subsets of <math>\mathcal{U}</math>,
{{cite news
a ''cover'' is a subfamily <math>\mathcal{C}\subseteq\mathcal{S}</math> of sets whose union is <math>\mathcal{U}</math>. In the set covering [[decision problem]], the input is a pair <math>(\mathcal{U},\mathcal{S})</math> and an integer <math>k</math>; the question is whether
|last=Chang |first=K.
there is a set covering of size <math>k</math> or less. In the set covering [[optimization problem]], the input is a pair <math>(\mathcal{U},\mathcal{S})</math>, and the task is to find a set covering that uses the fewest sets.
|date=9 March 2008
|title=Gauging Age of Universe Becomes More Precise
|url=http://www.nytimes.com/2008/03/09/science/space/09cosmos.html?_r=1&oref=slogin
|work=[[The New York Times]]
|accessdate=
}}</ref> presently use "age of the universe" to mean the duration of the Lambda-CDM expansion, or equivalently the elapsed time since the Big Bang in the current [[observable universe]].


==Observational limits==
The decision version of set covering is [[NP-complete]], and the optimization version of set cover is [[NP-hard]] .{{sfn |Korte|Vygen|2012|p=414}}
Since the universe must be at least as old as the oldest thing in it, there are a number of observations which put a lower limit on the age of the universe; these include the temperature of the coolest [[white dwarf]]s, which gradually cool as they age, and the dimmest [[turnoff point]] of [[main sequence]] [[stars]] in clusters (lower-mass stars spend a greater amount of time on the main sequence, so the lowest-mass stars that have evolved off of the main sequence set a minimum age).


==Cosmological parameters==
If additionally, you want to minimize the cost of the sets, it becomes Weighted Set Cover Problem. Otherwise, its an Un-weighted Set Cover Problem with all costs equal to one.
[[Image:Universe.svg|thumb|400px|The age of the universe can be determined by measuring the [[Hubble constant]] today and extrapolating back in time with the observed value of density parameters (Ω). Before the discovery of [[dark energy]], it was believed that the universe was matter-dominated, and so Ω on this graph corresponds to Ω<sub>''m''</sub>. Note that the [[accelerating universe]] has the greatest age, while the [[Big Crunch]] universe has the least age.]]
[[File:Age Universe Planck 2013.png|thumb|400px|The value of the age correction factor, ''F'', is shown as a function of two [[cosmology|cosmological parameters]]: the current fractional matter density Ω<sub>''m''</sub> and cosmological constant density Ω<sub>''Λ''</sub>.  The [[Lambda-CDM model|best-fit values]] of these parameters are shown by the box in the upper left; the matter-dominated universe is shown by the star in the lower right.]]


The problem of determining the age of the universe is closely tied to the problem of determining the values of the cosmological parameters. Today this is largely carried out in the context of the [[Lambda CDM model|ΛCDM]] model, where the universe is assumed to contain normal (baryonic) matter, cold [[dark matter]], radiation (including both [[photon]]s and [[neutrino]]s), and a [[cosmological constant]].  The fractional contribution of each to the current energy density of the universe is given by the [[density parameter]]s Ω<sub>''m''</sub>, Ω<sub>''r''</sub>, and Ω<sub>Λ</sub>.  The full ΛCDM model is described by a number of other parameters, but for the purpose of computing its age these three, along with the [[Hubble constant|Hubble parameter]] <math>H_0</math>, are the most important.
{{Covering-Packing Problem Pairs}}


If one has accurate measurements of these parameters, then the age of the universe can be determined by using the [[Friedmann equations|Friedmann equation]].  This equation relates the rate of change in the [[scale factor (cosmology)|scale factor]] ''a''(''t'') to the matter content of the universe.  Turning this relation around, we can calculate the change in time per change in scale factor and thus calculate the total age of the universe by [[Integral|integrating]] this formula. The age ''t''<sub>0</sub> is then given by an expression of the form
==Integer linear program formulation==
:<math>t_0 = \frac{1}{H_0} F(\Omega_r,\Omega_m,\Omega_\Lambda,\dots) </math>
The minimum set cover problem can be formulated as the following [[integer linear program]] (ILP).<ref>{{harvtxt|Vazirani|2001|p=108}}</ref>
where <math>H_0</math> is the [[Hubble's law|Hubble parameter]] and the function ''F'' depends only on the fractional contribution to the universe's energy content that comes from various components. The first observation that one can make from this formula is that it is the Hubble parameter that controls that age of the universe, with a correction arising from the matter and energy content. So a rough estimate of the age of the universe comes from the [[Hubble time]], the inverse of the Hubble parameter. With a value for <math>H_0</math> around {{val|68|u=km/s/Mpc}}, the Hubble time evaluates to <math>1/H_0</math> = {{val|14.4}} billion years.<ref>
{|
{{Cite book
| minimize
|last=Liddle |first=A. R.
| <math>\sum_{S \in \mathcal S} x_S</math>
|year=2003
|
|title=An Introduction to Modern Cosmology
| (minimize the number of sets)
|edition=2nd |page=57
|-
|publisher=[[John Wiley & Sons|Wiley]]
| subject to
|isbn=0-470-84835-9
| <math>\sum_{S\colon e \in S} x_S \geqslant 1 </math>
}}</ref>
| for all <math>e\in \mathcal U</math>
 
| (cover every element of the universe)
To get a more accurate number, the correction factor ''F'' must be computed. In general this must be done numerically, and the results for a range of cosmological parameter values are shown in the figure. For the [[Lambda CDM model|Planck values]] (Ω<sub>''m''</sub>, Ω<sub>''Λ''</sub>) = (0.3086, 0.6914), shown by the box in the upper left corner of the figure, this correction factor is about ''F'' = 0.956. For a flat universe without any cosmological constant, shown by the star in the lower right corner, ''F'' = {{Frac|2|3}} is much smaller and thus the universe is younger for a fixed value of the Hubble parameter. To make this figure, Ω<sub>''r''</sub> is held constant (roughly equivalent to holding the [[Cosmic Microwave Background|CMB]] temperature constant) and the curvature density parameter is fixed by the value of the other three.
|-
 
|
Apart from the Planck satellite, the Wilkinson Microwave Anisotropy Probe ([[WMAP]]) was instrumental in establishing an accurate age of the universe, though other measurements must be folded in to gain an accurate number.  [[CMB]] measurements are very good at constraining the matter content Ω<sub>''m''</sub><ref>
| <math>x_S \in \{0,1\}</math>
{{cite web
| for all <math>S\in \mathcal S</math>.
|last=Hu |first=W.
| (every set is either in the set cover or not)
|title=Animation: Matter Content Sensitivity. The matter-radiation ratio is raised while keeping all other parameters fixed.
|}
|url=http://background.uchicago.edu/%7Ewhu/physics/anim2.html
This ILP belongs to the more general class of ILPs for [[covering problem]]s.
|publisher=[[University of Chicago]]
The [[Linear programming relaxation#Approximation and integrality gap|integrality gap]] of this ILP is at most <math>\scriptstyle \log n</math>, so its [[Linear programming relaxation|relaxation]] gives a factor-<math>\scriptstyle \log n</math> [[approximation algorithm]] for the minimum set cover problem (where <math>\scriptstyle n</math> is the size of the universe).<ref>{{harvtxt|Vazirani|2001|pp=110–112}}</ref>
|accessdate=2008-02-23
|archiveurl=http://web.archive.org/web/20080223184613/http://background.uchicago.edu/%7Ewhu/physics/anim2.html
|archivedate=23 February 2008 <!--DASHBot-->
|deadurl=no
}}</ref> and curvature parameter Ω<sub>''k''</sub>.<ref name="anim3">
{{cite web
|last=Hu |first=W.
|title=Animation: Angular diameter distance scaling with curvature and lambda
|url=http://background.uchicago.edu/%7Ewhu/physics/anim3.html
|publisher=[[University of Chicago]]
|accessdate=2008-02-23
|archiveurl=http://web.archive.org/web/20080223184618/http://background.uchicago.edu/%7Ewhu/physics/anim3.html
|archivedate=23 February 2008 <!--DASHBot-->
|deadurl=no
}}</ref> It is not as sensitive to Ω<sub>Λ</sub> directly,<ref name="anim3"/> partly because the cosmological constant becomes important only at low redshift.  The most accurate determinations of the Hubble parameter ''H''<sub>0</sub> come from [[Type Ia supernova]]e.  Combining these measurements leads to the generally accepted value for the age of the universe quoted above.


The cosmological constant makes the universe "older" for fixed values of the other parameters. This is significant, since before the cosmological constant became generally accepted, the Big Bang model had difficulty explaining why [[globular cluster]]s in the Milky Way appeared to be far older than the age of the universe as calculated from the Hubble parameter and a matter-only universe.<ref>
== Hitting set formulation ==
{{cite web
Set covering is equivalent to the '''hitting set problem'''. It is easy to see this by observing that an instance of set covering can
|date=1 July 2011
be viewed as an arbitrary [[bipartite graph]], with sets represented by vertices on the left, the universe represented by vertices on the
|title=Globular Star Clusters
right, and edges representing the inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices.
|url=http://www.seds.org/messier/glob.html
|publisher=[[SEDS]]
|accessdate=2013-07-19
|archiveurl=http://web.archive.org/web/20080224064318/http://seds.org/messier/glob.html
|archivedate=24 February 2008 <!--DASHBot-->
|deadurl=no
}}</ref><ref>
{{cite web
|last=Iskander |first=E.
|date=11 January 2006
|title=Independent age estimates
|url=http://www.astro.ubc.ca/people/scott/bbage.html
|publisher=[[University of British Columbia]]
|accessdate=2008-02-23
|archiveurl=http://web.archive.org/web/20080306024809/http://www.astro.ubc.ca/people/scott/bbage.html
|archivedate=6 March 2008 <!--DASHBot-->
|deadurl=no
}}</ref>  Introducing the cosmological constant allows the universe to be older than these clusters, as well as explaining other features that the matter-only cosmological model could not.<ref>
{{cite arXiv
|title=Cosmic Concordance
|last1=Ostriker |first1=J. P.
|last2=Steinhardt |first2=P. J.
|year=1995
|class=astro-ph
|eprint=astro-ph/9505066
}}</ref>


==WMAP==
== Greedy algorithm ==
[[NASA]]'s [[Wilkinson Microwave Anisotropy Probe]] (WMAP) project's [[Wilkinson Microwave Anisotropy Probe#Nine-year data release|nine-year data release]] in 2012 estimated the age of the universe to be {{val|13.772|0.059|e=9}} years (13.772 billion years, with an uncertainty of plus or minus 59 million years).<ref name="arxiv-20121220" />


However, this age is based on the assumption that the project's underlying model is correct; other methods of estimating the age of the universe could give different ages. Assuming an extra background of relativistic particles, for example, can enlarge the error bars of the WMAP constraint by one order of magnitude.<ref>
The [[greedy algorithm]] for set covering chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. It can be shown<ref>Chvatal, V. [http://www.jstor.org/stable/3689577 A Greedy Heuristic for the Set-Covering Problem]. Mathematics of Operations Research
{{cite journal
Vol. 4, No. 3 (Aug., 1979), pp. 233-235</ref> that this algorithm achieves an approximation ratio of <math>H(s)</math>, where <math>s</math> is the size of the set to be covered, <math>H(n)</math> is the <math>n</math>-th [[harmonic number]]:
|last1=de Bernardis |first1=F.
|last2=Melchiorri |first2=A.
|last3=Verde |first3=L.
|last4=Jimenez |first4=R.
|year=2008
|title=The Cosmic Neutrino Background and the Age of the Universe
|journal=[[Journal of Cosmology and Astroparticle Physics]]
|volume=2008 |issue=3 |pages=20
|arxiv=0707.4170
|bibcode=2008JCAP...03..020D
|doi=10.1088/1475-7516/2008/03/020
}}</ref>


This measurement is made by using the location of the first acoustic peak in the [[cosmic microwave background radiation|microwave background]] power spectrum to determine the size of the decoupling surface (size of the universe at the time of recombination).  The light travel time to this surface (depending on the geometry used) yields a reliable age for the universe.  Assuming the validity of the models used to determine this age, the residual accuracy yields a margin of error near one percent.<ref name="wmap">
:<math> H(n) = \sum_{k=1}^{n} \frac{1}{k} \le \ln{n} +1</math>
{{cite journal
|first=D. N. |last=Spergel
|author2=''et al.''
|year=2003
|title=First-Year Wilkinson Microwave Anisotropy Probe (WMAP) Observations: Determination of Cosmological Parameters
|journal=[[The Astrophysical Journal Supplement Series]]
|volume=148 |issue=1 |pages=175–194
|arxiv=astro-ph/0302209
|bibcode=2003ApJS..148..175S
|doi=10.1086/377226
}}</ref>


==Planck==
This greedy algorithm actually achieves an approximation ratio of <math>H(s^\prime)</math> where <math>s^\prime</math> is the maximum cardinality set of <math>S</math>.
In 2013, the [[European Space Agency]]'s [[Planck (spacecraft)|Planck spacecraft]] team estimated the age of the universe to be {{val|13.82}} billion years,<ref name="ESA-20130321">
{{cite web
|author=Staff
|title=Planck Reveals An Almost Perfect Universe
|url=http://www.esa.int/Our_Activities/Space_Science/Planck/Planck_reveals_an_almost_perfect_Universe
|publisher=[[European Space Agency]]
|date=21 March 2013
|accessdate=2013-03-21
}}</ref><ref name="NASA-20130321">
{{cite web
|last1=Clavin |first1=W.
|last2=Harrington |first2=J. D.
|title=Planck Mission Brings Universe Into Sharp Focus
|url=http://www.jpl.nasa.gov/news/news.php?release=2013-109&rn=news.xml&rst=3739
|date=21 March 2013
|publisher=[[NASA]]
|accessdate=2013-03-21
}}</ref><ref name="NYT-20130321">
{{cite news
|last=Overbye |first=D.
|date=21 March 2013
|title=An Infant Universe, Born Before We Knew
|url=http://www.nytimes.com/2013/03/22/science/space/planck-satellite-shows-image-of-infant-universe.html
|work=[[New York Times]]
|accessdate=2013-03-21
}}</ref><ref name="NBC-20130321">
{{cite web
|last=Boyle |first=A.
|date=21 March 2013
|title=Planck probe's cosmic 'baby picture' revises universe's vital statistics
|url=http://cosmiclog.nbcnews.com/_news/2013/03/21/17397298-planck-probes-cosmic-baby-picture-revises-universes-vital-statistics
|work=[[NBC News]]
|accessdate=2013-03-21
}}</ref> slightly higher but within the uncertainties of the earlier number derived from the WMAP data. By combining the Planck data with previous missions, the best combined estimate of the age of the universe is [[Planck (spacecraft)#2013 data release|{{val|13.798|0.037|e=9|u=years}} old]].<ref name="planck_overview" />


<center>
[[Image:SetCoverGreedy.gif|frame|Tight example for the greedy algorithm with k=3]]
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 70%; text-align:center;"
There is a standard example on which the greedy algorithm achieves an approximation ratio of <math>\log_2(n)/2</math>.
|- bgcolor="#B0C4DE" align="center"
The universe consists of <math>n=2^{(k+1)}-2</math> elements. The set system consists of <math>k</math> pairwise disjoint sets
|+ [[Lambda-CDM model|Cosmological parameters]] from 2013 Planck results<ref name="planck_overview" /><ref name='planck_cosmological_parameters'>
<math>S_1,\ldots,S_k</math> with sizes <math>2,4,8,\ldots,2^k</math> respectively, as well as two additional disjoint sets <math>T_0,T_1</math>,
{{cite arXiv
each of which contains half of the elements from each <math>S_i</math>. On this input, the greedy algorithm takes the sets
|author=Planck collaboration
<math>S_k,\ldots,S_1</math>, in that order, while the optimal solution consists only of <math>T_0</math> and <math>T_1</math>.
|year=2013
An example of such an input for <math>k=3</math> is pictured on the right.
|title=Planck 2013 results. XVI. Cosmological parameters
|class=astro-ph.CO
|eprint=1303.5076
}}</ref>
! Parameter !! Symbol !! Planck<br> Best fit !! Planck<br> 68% limits !! Planck+lensing<br> Best fit !! Planck+lensing<br> 68% limits !! Planck+WP<br> Best fit !! Planck+WP<br> 68% limits !! Planck+WP<br> +HighL<br> Best fit !! Planck+WP<br> +HighL<br> 68% limits !! Planck+lensing<br> +WP+highL<br> Best fit !! Planck+lensing<br> +WP+highL<br> 68% limits !! Planck+[[WMAP|WP]]<br> +highL+[[baryon acoustic oscillations|BAO]]<br> Best fit !! Planck+[[WMAP|WP]]<br> +highL+[[baryon acoustic oscillations|BAO]]<br> 68% limits
|-
| Age of the universe<br> (Ga) || <math>t_0</math> || 13.819 || {{val|13.813|0.058}} || 13.784 || {{val|13.796|0.058}} || 13.8242 || {{val|13.817|0.048}} || 13.8170 || {{val|13.813|0.047}} || 13.7914 || {{val|13.794|0.044}} || 13.7965 || {{val|13.798|0.037}}
|-
| [[Hubble's constant]]<br> ( {{frac|km|Mpc·s}} ) || <math>H_0</math> || 67.11 || {{val|67.4|1.4}} || 68.14 || {{val|67.9|1.5}} || 67.04 || {{val|67.3|1.2}} || 67.15 || {{val|67.3|1.2}} || 67.94 || {{val|67.9|1.0}}|| 67.77 || {{val|67.80|0.77}}
|}
</center>
{{-}}


==Assumption of strong priors==
Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover
Calculating the age of the universe is accurate only if the assumptions built into the models being used to estimate it are also accurate. This is referred to as [[strong priors]] and essentially involves stripping the potential errors in other parts of the model to render the accuracy of actual observational data directly into the concluded result.  Although this is not a valid procedure in all contexts (as noted in the accompanying caveat: "based on the fact we have assumed the underlying model we used is correct"), the age given is thus accurate to the specified error (since this error represents the error in the instrument used to gather the raw data input into the model).
(see [[Set cover problem#Inapproximability results|Inapproximability results]] below), under plausible complexity assumptions.


The age of the universe based on the best fit to [[Planck (spacecraft)#2013 data release|Planck 2013 data]] alone is {{val|13.813|0.058}} billion years (the other estimate of {{val|13.798|0.037}} billion years uses Gaussian [[Prior probability|prior]]s based on earlier estimates from other studies to determine the combined uncertainty). This number represents the first accurate "direct" measurement of the age of the universe (other methods typically involve [[Hubble's law]] and the age of the oldest stars in globular clusters, etc.). It is possible to use different methods for determining the same parameter (in this case – the age of the universe) and arrive at different answers with no overlap in the "errors". To best avoid the problem, it is common to show two sets of uncertainties; one related to the actual measurement and the other related to the systematic errors of the model being used.
== Low-frequency systems ==


An important component to the analysis of data used to determine the age of the universe (e.g. from [[Planck (spacecraft)|Planck]]) therefore is to use a [[Bayesian statistics|Bayesian statistical]] analysis, which normalizes the results based upon the priors (i.e. the model).<ref name="wmap" /> This quantifies any uncertainty in the accuracy of a measurement due to a particular model used.<ref>
If each element occurs in at most ''f'' sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of ''f'' using [[Linear programming relaxation|LP relaxation]].<ref>{{harvtxt|Vazirani|2001|pp=118–119}}</ref>
{{cite conference
|last=Loredo |first=T. J.
|year=1992
|title=The Promise of Bayesian Inference for Astrophysics
|url=http://www.astro.cornell.edu/staff/loredo/bayes/promise.pdf
|editor1-last=Feigelson |editor1-first=E. D.
|editor2-last=Babu |editor2-first=G. J.
|booktitle=Statistical Challenges in Modern Astronomy
|pages=275–297
|publisher=[[Springer-Verlag]]
|bibcode=1992scma.conf..275L
|doi=10.1007/978-1-4613-9290-3_31
|isbn=978-1-4613-9292-7
}}</ref><ref>
{{cite journal
|last1=Colistete |first1=R.
|last2=Fabris |first2=J. C.
|last3=Concalves |first3=S. V. B.
|year=2005
|title=Bayesian Statistics and Parameter Constraints on the Generalized Chaplygin Gas Model Using SNe ia Data
|journal=[[International Journal of Modern Physics D]]
|volume=14 |issue=5 |pages=775–796
|arxiv=astro-ph/0409245
|bibcode=2005IJMPD..14..775C
|doi=10.1142/S0218271805006729
}}</ref>


==History==
== Inapproximability results ==
{{Expand section|date=February 2014|1= The estimated age of the universe for certain crucial points in history, e.g.:
* before Einstein
* after Einstein
* before Hubble
* after Hubble
* etc}}
In the 18th century, the concept that the [[age of the Earth]] was millions, if not billions, of years began to appear. However, most scientists throughout the 19th century and into the first decades of the 20th century presumed that the universe itself was [[Steady State theory|Steady State]] and eternal, with maybe stars coming and going but no changes occurring at the largest scale known at the time.


The first scientific theories indicating that the age of the universe might be finite were the studies of [[thermodynamics]], formalized in the mid-19th century. The concept of [[entropy]] dictates that if the universe (or any other closed system) were infinitely old, then everything inside would be at the same temperature, and thus there would be no stars and no life. No scientific explanation for this contradiction was put forth at the time. In 1915 [[Albert Einstein]] published the theory of [[general relativity]].<ref>
When <math> n</math> refers to the size of the universe, {{harvtxt |Lund|Yannakakis|1994}} showed that set covering cannot be approximated in polynomial time to within a factor of <math>\tfrac{1}{2}\log_2{n} \approx 0.72\ln{n}</math>, unless '''NP''' has [[quasi-polynomial time]] algorithms. Feige (1998) improved this lower bound to <math>\bigl(1-o(1)\bigr)\cdot\ln{n}</math> under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. {{harvtxt |Raz|Safra|1997}} established a lower bound
{{cite journal
of <math>c\cdot\ln{n}</math>, where <math>c</math> is a constant, under the weaker assumption that '''P'''<math>\not=</math>'''NP'''.
|last=Einstein |first=A.
A similar result with a higher value of <math>c</math> was recently proved by {{harvtxt |Alon|Moshkovitz|Safra|2006}}.
|year=1915
|title=Zur allgemeinen Relativitätstheorie
|journal=[[Sitzungsberichte der Königlich Preußischen Akademie der Wissenschaften]]
|pages=778–786
|language=German
|bibcode=1915SPAW.......778E
}}</ref> Based on Einstein's theory, [[Georges Lemaître]]'s work showed that the universe cannot be static and must be either expanding or contracting. Einstein himself did not believe this result and so he added what he called a [[cosmological constant]] to his equations in an unsuccessful attempt to produce a theory consistent with a steady state universe.


The first direct observational evidence that the universe has a finite age came from the observations of astronomer [[Edwin Hubble]] published in 1929.<ref>
== Related problems ==
{{cite journal
* Hitting set is an equivalent reformulation of Set Cover.
|last=Hubble |first=E.
* [[Vertex cover problem|Vertex cover]] is a special case of Hitting Set.
|year=1929
* [[Edge cover problem|Edge cover]] is a special case of Set Cover.
|title=A relation between distance and radial velocity among extra-galactic nebulae
* [[Set packing]] is the dual problem of Set Cover.
|journal=[[Proceedings of the National Academy of Sciences]]
* [[Maximum coverage problem]] is to choose at most k sets to cover as many elements as possible.
|volume=15 |issue=3 |pages=168&ndash;173
* [[Dominating set]] is the problem of selecting a set of vertices (the dominating set) in a graph such that all other vertices are adjacent to at least one vertex in the dominating set. The Dominating set problem was shown to be NP complete through a reduction from Set cover.
|url=http://www.pnas.org/cgi/reprint/15/3/168
* [[Exact cover problem]] is to choose a set cover with no element included in more than one covering set.
|bibcode=1929PNAS...15..168H
* [[Closest pair of points problem]]
|doi=10.1073/pnas.15.3.168
* [[Nearest neighbor search]]
|pmid=16577160
|pmc=522427
}}</ref> Earlier in the 20th century, Hubble and others resolved individual stars within certain [[nebula]]e, thus determining that they were [[Galaxy|galaxies]], similar to, but external to, our [[Milky Way Galaxy]]. In addition, these galaxies were very large and very far away. [[electromagnetic spectrum|Spectra]] taken of these distant galaxies showed a [[red shift]] in their [[spectral lines]] presumably caused by the [[Doppler effect]], thus indicating that these galaxies were moving away from the Earth. In addition, the farther away these galaxies seemed to be, the greater the redshift and thus the faster they seemed to be moving away. This was the first direct evidence that the universe is not static but expanding. The first estimate of the age of the universe came from the calculation of when all of the objects must have started speeding out from the same point. Hubble's initial value for the universe's age was very low, as the galaxies were assumed to be much closer than later observations found them to be.


The first reasonably accurate measurement of the rate of expansion of the universe, a numerical value now known as the [[Hubble constant]], was made in 1958 by astronomer [[Allan Sandage]].<ref>
==See also==
{{cite journal
*[[MinHash]]
|last1=Sandage |first1=A. R.
*[[Sequence assembly]]
|title=Current Problems in the Extragalactic Distance Scale
|year=1958
|journal=[[The Astrophysical Journal]]
|volume=127 |issue=3 |pages=513–526
|bibcode=1958ApJ...127..513S
|doi=10.1086/146483
}}</ref> His measured value for the Hubble constant came very close to the value range generally accepted today.


However Sandage, like Einstein, did not believe his own results at the time of discovery. His value for the age of the universe{{Elucidate|date=February 2014|reason=What was his value for the age of the universe?}} was too short to reconcile with the 25-billion-year age estimated at that time for the oldest known [[star]]s. Sandage and other astronomers repeated these measurements numerous times, attempting to reduce the Hubble constant and thus increase the resulting age for the universe. Sandage even proposed new theories of [[cosmogony]] to explain this discrepancy. This issue was finally resolved by improvements in the theoretical models used for estimating the ages of stars. As of 2013, using the latest models for stellar evolution, the estimated age of the [[HD 140283|oldest known star]] is {{val|14.46|0.8}} billion years.<ref name=arxiv>
==Notes==
{{cite journal
|last1=Bond |first1=H. E.
|last2=Nelan |first2=E. P.
|last3=Vandenberg|first3=D. A.
|last4=Schaefer|first4=G. H.
|last5=Harmer |first5=D.
|title=HD 140283: A Star in the Solar Neighborhood that Formed Shortly After the Big Bang
|year=2013
|journal=[[The Astrophysical Journal]]
|volume=765 |pages=L12 |issue=12
|arxiv=1302.3180
|bibcode=2013ApJ...765L..12B
|doi=10.1088/2041-8205/765/1/L12
}}</ref>


The discovery of [[microwave]] [[cosmic background radiation]] announced in 1965<ref name="apj142:419">
{{reflist}}
{{cite journal
|last=Penzias |first=A. A.
|last2=Wilson |first2=R .W.
|year=1965
|title=A Measurement of Excess Antenna Temperature at 4080 Mc/s
|journal=[[The Astrophysical Journal]]
|volume=142 |pages=419–421
|doi=10.1086/148307
|bibcode=1965ApJ...142..419P
}}</ref> finally brought an effective end to the remaining scientific uncertainty over the expanding universe. The recently launched space probes WMAP, launched in 2001, and Planck, launched in 2009, produced data that determines the Hubble constant and the age of the universe independent of galaxy distances, removing the largest source of error.<ref name="wmap"/>


== See also ==
== References ==
{{Portal|Astronomy}}
* [[Age crisis]]
* [[Age of the Earth]]
* [[Anthropic principle]]
* [[Cosmology]]
* [[Hubble Deep Field]]
* [[Metric expansion of space]]
* [[Multiverse]]
* [[Observable universe]]
* [[Red Shift#Observations in astronomy|Red shift observations in astronomy]]
* [[Static universe]]
* [[The First Three Minutes: A Modern View of the Origin of the Universe]] an essay written by [[Steven Weinberg]] and published in 1977
* [[Dark Ages Radio Explorer (DARE)]]


==References==
* {{Citation | last1=Alon | first1=Noga | author1-link=Noga Alon | last2=Moshkovitz | first2=Dana | last3=Safra | first3=Shmuel | author3-link=Shmuel Safra | title=Algorithmic construction of sets for k-restrictions | publisher=ACM | year=2006 | journal=ACM Trans. Algorithms | issn=1549-6325 | volume=2 | issue=2 | pages=153–177 | doi=10.1145/1150334.1150336}}.
{{Reflist|30em}}
* {{Citation
| last=Cormen    | first=Thomas H.  | authorlink=Thomas H. Cormen
| last2=Leiserson | first2=Charles E. | authorlink2=Charles E. Leiserson
| last3=Rivest    | first3=Ronald L.  | authorlink3=Ronald L. Rivest
| last4=Stein    | first4=Clifford  | authorlink4=Clifford Stein
| title=Introduction to Algorithms | year=2001 | publisher=MIT Press and McGraw-Hill | location=Cambridge, Mass.
| isbn=0-262-03293-7 | pages=1033–1038}}
* {{Citation | last1=Feige | first1=Uriel | author1-link=Uriel Feige | title=A threshold of ln n for approximating set cover | publisher=ACM | year=1998 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=45 | issue=4 | pages=634–652 | doi=10.1145/285055.285059}}.
* {{Citation | last1=Lund | first1=Carsten | author1-link=Carsten Lund | last2=Yannakakis | first2=Mihalis | author2-link=Mihalis Yannakakis | title=On the hardness of approximating minimization problems | publisher=ACM | year=1994 | journal=[[Journal of the ACM]] | issn=0004-5411 | volume=41 | issue=5 | pages=960–981 | doi=10.1145/185675.306789}}.
* {{Citation | last1=Raz | first1=Ran | author1-link=Ran Raz | last2=Safra | first2=Shmuel | author2-link=Shmuel Safra | title=STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing | publisher=ACM | isbn=978-0-89791-888-6 | year=1997 | chapter=A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP | pages=475–484}}.
* {{cite book
| last = Vazirani | first = Vijay V.
| authorlink = Vijay Vazirani
| title = Approximation Algorithms
| year = 2001
| publisher = Springer-Verlag
| isbn = 3-540-65367-8
| url = http://www.cc.gatech.edu/fac/Vijay.Vazirani/book.pdf
| ref = harv
}}
* {{cite book
| last1 = Korte | first1 = Bernhard
| last2 = Vygen | first2 = Jens
| title = Combinatorial Optimization: Theory and Algorithms
| year = 2012
| isbn = 978-3-642-24487-2
| edition = 5
| publisher = Springer
| ref = harv
}}


==External links==
== External links ==
*[http://www.astro.ucla.edu/~wright/cosmolog.htm Ned Wright's Cosmology Tutorial]
* [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/set-benchmarks.htm Benchmarks with Hidden Optimum Solutions for Set Covering, Set Packing and Winner Determination]
*{{cite web | url =http://www.astro.ucla.edu/~wright/age.html | first =Edward L. | last =Wright | title =Age of the Universe | date =2 July 2005}}
* [http://www.csc.kth.se/~viggo/wwwcompendium/node146.html A compendium of NP optimization problems - Minimum Set Cover]
*Wayne Hu's [http://background.uchicago.edu/~whu/metaanim.html cosmological parameter animations]
*{{cite arXiv|eprint=astro-ph/9505066|author1=Ostriker|author2=Steinhardt|title=Cosmic Concordance|class=astro-ph|year=1995}}
*SEDS page on [http://www.seds.org/messier/glob.html "Globular Star Clusters"]
*Douglas Scott [http://www.astro.ubc.ca/people/scott/bbage.html "Independent Age Estimates"]
*KryssTal [http://www.krysstal.com/scale.html "The Scale of the Universe"] Space and Time scaled for the beginner.
*[http://icosmos.co.uk/ iCosmos: Cosmology Calculator (With Graph Generation )]
*[http://www.aip.org/history/cosmology/ideas/expanding.htm The Expanding Universe] (American Institute of Physics)


{{DEFAULTSORT:Age Of The Universe}}
{{DEFAULTSORT:Set Cover Problem}}
[[Category:Universe]]
[[Category:Set families]]
[[Category:Physical cosmology]]
[[Category:NP-complete problems]]
[[Category:Big Bang]]

Revision as of 22:09, 12 August 2014

The set covering problem (SCP) is a classical question in combinatorics, computer science and complexity theory.

It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.[1] It was also one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.

Given a set of elements {1,2,...,m} (called the universe) and a set S of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of S whose union equals the universe. For example, consider the universe U={1,2,3,4,5} and the set of sets S={{1,2,3},{2,4},{3,4},{4,5}}. Clearly the union of S is U. However, we can cover all of the elements with the following, smaller number of sets: {{1,2,3},{4,5}}.

More formally, given a universe 𝒰 and a family 𝒮 of subsets of 𝒰, a cover is a subfamily 𝒞⊆𝒮 of sets whose union is 𝒰. In the set covering decision problem, the input is a pair (𝒰,𝒮) and an integer k; the question is whether there is a set covering of size k or less. In the set covering optimization problem, the input is a pair (𝒰,𝒮), and the task is to find a set covering that uses the fewest sets.

The decision version of set covering is NP-complete, and the optimization version of set cover is NP-hard .Template:Sfn

If additionally, you want to minimize the cost of the sets, it becomes Weighted Set Cover Problem. Otherwise, its an Un-weighted Set Cover Problem with all costs equal to one.

Template:Covering-Packing Problem Pairs

Integer linear program formulation

The minimum set cover problem can be formulated as the following integer linear program (ILP).[2]

minimize ∑S∈𝒮xS (minimize the number of sets)
subject to ∑S:e∈SxS⩾1 for all e∈𝒰 (cover every element of the universe)
xS∈{0,1} for all S∈𝒮. (every set is either in the set cover or not)

This ILP belongs to the more general class of ILPs for covering problems. The integrality gap of this ILP is at most log⁡n, so its relaxation gives a factor-log⁡n approximation algorithm for the minimum set cover problem (where n is the size of the universe).[3]

Hitting set formulation

Set covering is equivalent to the hitting set problem. It is easy to see this by observing that an instance of set covering can be viewed as an arbitrary bipartite graph, with sets represented by vertices on the left, the universe represented by vertices on the right, and edges representing the inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices.

Greedy algorithm

The greedy algorithm for set covering chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. It can be shown[4] that this algorithm achieves an approximation ratio of H(s), where s is the size of the set to be covered, H(n) is the n-th harmonic number:

H(n)=∑k=1n1k≤ln⁡n+1

This greedy algorithm actually achieves an approximation ratio of H(s′) where s′ is the maximum cardinality set of S.

Tight example for the greedy algorithm with k=3

There is a standard example on which the greedy algorithm achieves an approximation ratio of log2(n)/2. The universe consists of n=2(k+1)−2 elements. The set system consists of k pairwise disjoint sets S1,…,Sk with sizes 2,4,8,…,2k respectively, as well as two additional disjoint sets T0,T1, each of which contains half of the elements from each Si. On this input, the greedy algorithm takes the sets Sk,…,S1, in that order, while the optimal solution consists only of T0 and T1. An example of such an input for k=3 is pictured on the right.

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover (see Inapproximability results below), under plausible complexity assumptions.

Low-frequency systems

If each element occurs in at most f sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of f using LP relaxation.[5]

Inapproximability results

When n refers to the size of the universe, Template:Harvtxt showed that set covering cannot be approximated in polynomial time to within a factor of 12log2n≈0.72ln⁡n, unless NP has quasi-polynomial time algorithms. Feige (1998) improved this lower bound to (1−o(1))⋅ln⁡n under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. Template:Harvtxt established a lower bound of c⋅ln⁡n, where c is a constant, under the weaker assumption that P=NP. A similar result with a higher value of c was recently proved by Template:Harvtxt.

Related problems

See also

Notes

43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.

References

  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • Many property agents need to declare for the PIC grant in Singapore. However, not all of them know find out how to do the correct process for getting this PIC scheme from the IRAS. There are a number of steps that you need to do before your software can be approved.

    Naturally, you will have to pay a safety deposit and that is usually one month rent for annually of the settlement. That is the place your good religion deposit will likely be taken into account and will kind part or all of your security deposit. Anticipate to have a proportionate amount deducted out of your deposit if something is discovered to be damaged if you move out. It's best to you'll want to test the inventory drawn up by the owner, which can detail all objects in the property and their condition. If you happen to fail to notice any harm not already mentioned within the inventory before transferring in, you danger having to pay for it yourself.

    In case you are in search of an actual estate or Singapore property agent on-line, you simply should belief your intuition. It's because you do not know which agent is nice and which agent will not be. Carry out research on several brokers by looking out the internet. As soon as if you end up positive that a selected agent is dependable and reliable, you can choose to utilize his partnerise in finding you a home in Singapore. Most of the time, a property agent is taken into account to be good if he or she locations the contact data on his website. This may mean that the agent does not mind you calling them and asking them any questions relating to new properties in singapore in Singapore. After chatting with them you too can see them in their office after taking an appointment.

    Have handed an trade examination i.e Widespread Examination for House Brokers (CEHA) or Actual Property Agency (REA) examination, or equal; Exclusive brokers are extra keen to share listing information thus making certain the widest doable coverage inside the real estate community via Multiple Listings and Networking. Accepting a severe provide is simpler since your agent is totally conscious of all advertising activity related with your property. This reduces your having to check with a number of agents for some other offers. Price control is easily achieved. Paint work in good restore-discuss with your Property Marketing consultant if main works are still to be done. Softening in residential property prices proceed, led by 2.8 per cent decline within the index for Remainder of Central Region

    Once you place down the one per cent choice price to carry down a non-public property, it's important to accept its situation as it is whenever you move in – faulty air-con, choked rest room and all. Get round this by asking your agent to incorporate a ultimate inspection clause within the possibility-to-buy letter. HDB flat patrons routinely take pleasure in this security net. "There's a ultimate inspection of the property two days before the completion of all HDB transactions. If the air-con is defective, you can request the seller to repair it," says Kelvin.

    15.6.1 As the agent is an intermediary, generally, as soon as the principal and third party are introduced right into a contractual relationship, the agent drops out of the image, subject to any problems with remuneration or indemnification that he could have against the principal, and extra exceptionally, against the third occasion. Generally, agents are entitled to be indemnified for all liabilities reasonably incurred within the execution of the brokers´ authority.

    To achieve the very best outcomes, you must be always updated on market situations, including past transaction information and reliable projections. You could review and examine comparable homes that are currently available in the market, especially these which have been sold or not bought up to now six months. You'll be able to see a pattern of such report by clicking here It's essential to defend yourself in opposition to unscrupulous patrons. They are often very skilled in using highly unethical and manipulative techniques to try and lure you into a lure. That you must also protect your self, your loved ones, and personal belongings as you'll be serving many strangers in your home. Sign a listing itemizing of all of the objects provided by the proprietor, together with their situation. HSR Prime Recruiter 2010.
  • 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534
  • 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534

External links

  1. ↑ Template:Harvtxt
  2. ↑ Template:Harvtxt
  3. ↑ Template:Harvtxt
  4. ↑ Chvatal, V. A Greedy Heuristic for the Set-Covering Problem. Mathematics of Operations Research Vol. 4, No. 3 (Aug., 1979), pp. 233-235
  5. ↑ Template:Harvtxt
Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=47529"