. . "RIV/00216208:11320/11:10126049!RIV13-MSM-11320___" . "Graph-Theoretic Concepts in Computer Science" . . . "Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses"@en . "In a modification of the classical model of housing market which includes duplicate houses, economic equilibrium might not exist. As a measure of approximation the value sat (M) was proposed: the maximum number of satisfied agents in the market (M) , where an agent is said to be satisfied if, given a set of prices, he gets a most preferred house in his budget set. Clearly, market (M) admits an economic equilibrium if sat(M) is equal to the total number n of agents, but sat (M) is NP-hard to compute. In this paper we give a 2-approximation algorithm for sat (M) in the case of trichotomic preferences. On the other hand, we prove that sat (M) is hard to approximate within a factor smaller than 21/19, even if each house type is used for at most two houses. If the preferences are not required to be trichotomic, the problem is hard to approximate within a factor smaller than 1.2. We also prove that, provided the Unique Games Conjecture is true, approximation is hard within a factor 1.25 for trichotomic preferences, and within a factor 1.5 in the case of general preferences." . "Tepl\u00E1 Monastery, Czech Republic" . "http://dx.doi.org/10.1007/978-3-642-25870-1_10" . . "10.1007/978-3-642-25870-1_10" . . . "Cechl\u00E1rov\u00E1, Katar\u00EDna" . "In a modification of the classical model of housing market which includes duplicate houses, economic equilibrium might not exist. As a measure of approximation the value sat (M) was proposed: the maximum number of satisfied agents in the market (M) , where an agent is said to be satisfied if, given a set of prices, he gets a most preferred house in his budget set. Clearly, market (M) admits an economic equilibrium if sat(M) is equal to the total number n of agents, but sat (M) is NP-hard to compute. In this paper we give a 2-approximation algorithm for sat (M) in the case of trichotomic preferences. On the other hand, we prove that sat (M) is hard to approximate within a factor smaller than 21/19, even if each house type is used for at most two houses. If the preferences are not required to be trichotomic, the problem is hard to approximate within a factor smaller than 1.2. We also prove that, provided the Unique Games Conjecture is true, approximation is hard within a factor 1.25 for trichotomic preferences, and within a factor 1.5 in the case of general preferences."@en . . . "0302-9743" . . "Springer-Verlag. (Berlin; Heidelberg)" . "1"^^ . . . . . "186943" . "11320" . "hardness of approximation; approximation algorithms; economic equilibrium; housing markets"@en . . "RIV/00216208:11320/11:10126049" . "[748F7A29D253]" . "2"^^ . "978-3-642-25869-5" . "2011-06-21+02:00"^^ . "Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses"@en . "Z(MSM0021620838)" . "Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses" . "Approximability of Economic Equilibrium for Housing Markets with Duplicate Houses" . "Jel\u00EDnkov\u00E1, Eva" . "12"^^ . "000307088100010" . "Heidelberg" . . . .