@article{9013, abstract = {In this Letter, we investigate experimentally the nonequilibrium steady state of an active colloidal suspension under gravity field. The active particles are made of chemically powered colloids, showing self propulsion in the presence of an added fuel, here hydrogen peroxide. The active suspension is studied in a dedicated microfluidic device, made of permeable gel microstructures. Both the microdynamics of individual colloids and the global stationary state of the suspension under gravity are measured with optical microscopy. This yields a direct measurement of the effective temperature of the active system as a function of the particle activity, on the basis of the fluctuation-dissipation relationship. Our work is a first step in the experimental exploration of the out-of-equilibrium properties of active colloidal systems.}, author = {Palacci, Jérémie A and Cottin-Bizonne, Cécile and Ybert, Christophe and Bocquet, Lydéric}, issn = {10797114}, journal = {Physical Review Letters}, number = {8}, publisher = {American Physical Society }, title = {{Sedimentation and effective temperature of active colloidal suspensions}}, doi = {10.1103/physrevlett.105.088304}, volume = {105}, year = {2010}, } @article{9145, abstract = {We have found a new way to express the solutions of the RSM (Reynolds Stress Model) equations that allows us to present the turbulent diffusivities for heat, salt and momentum in a way that is considerably simpler and thus easier to implement than in previous work. The RSM provides the dimensionless mixing efficiencies Γα (α stands for heat, salt and momentum). However, to compute the diffusivities, one needs additional information, specifically, the dissipation ε. Since a dynamic equation for the latter that includes the physical processes relevant to the ocean is still not available, one must resort to different sources of information outside the RSM to obtain a complete Mixing Scheme usable in OGCMs. As for the RSM results, we show that the Γα’s are functions of both Ri and Rρ (Richardson number and density ratio representing double diffusion, DD); the Γα are different for heat, salt and momentum; in the case of heat, the traditional value Γh = 0.2 is valid only in the presence of strong shear (when DD is inoperative) while when shear subsides, NATRE data show that Γh can be three times as large, a result that we reproduce. The salt Γs is given in terms of Γh. The momentum Γm has thus far been guessed with different prescriptions while the RSM provides a well defined expression for Γm(Ri, Rρ). Having tested Γh, we then test the momentum Γm by showing that the turbulent Prandtl number Γm/Γh vs. Ri reproduces the available data quite well. As for the dissipation ε, we use different representations, one for the mixed layer (ML), one for the thermocline and one for the ocean’s bottom. For the ML, we adopt a procedure analogous to the one successfully used in PB (planetary boundary layer) studies; for the thermocline, we employ an expression for the variable εN−2 from studies of the internal gravity waves spectra which includes a latitude dependence; for the ocean bottom, we adopt the enhanced bottom diffusivity expression used by previous authors but with a state of the art internal tidal energy formulation and replace the fixed Γα = 0.2 with the RSM result that brings into the problem the Ri, Rρ dependence of the Γα; the unresolved bottom drag, which has thus far been either ignored or modeled with heuristic relations, is modeled using a formalism we previously developed and tested in PBL studies. We carried out several tests without an OGCM. Prandtl and flux Richardson numbers vs. Ri. The RSM model reproduces both types of data satisfactorily. DD and Mixing efficiency Γh(Ri, Rρ). The RSM model reproduces well the NATRE data. Bimodal ε-distribution. NATRE data show that ε(Ri < 1) ≈ 10ε(Ri > 1), which our model reproduces. Heat to salt flux ratio. In the Ri ≫ 1 regime, the RSM predictions reproduce the data satisfactorily. NATRE mass diffusivity. The z-profile of the mass diffusivity reproduces well the measurements at NATRE. The local form of the mixing scheme is algebraic with one cubic equation to solve.}, author = {Canuto, V.M. and Howard, A.M. and Cheng, Y. and Muller, Caroline J and Leboissetier, A. and Jayne, S.R.}, issn = {1463-5003}, journal = {Ocean Modelling}, keywords = {Computer Science (miscellaneous), Geotechnical Engineering and Engineering Geology, Atmospheric Science, Oceanography}, number = {3-4}, pages = {70--91}, publisher = {Elsevier}, title = {{Ocean turbulence, III: New GISS vertical mixing scheme}}, doi = {10.1016/j.ocemod.2010.04.006}, volume = {34}, year = {2010}, } @article{9146, abstract = {The factors governing the rate of change in the amount of atmospheric water vapor are analyzed in simulations of climate change. The global-mean amount of water vapor is estimated to increase at a differential rate of 7.3% K − 1 with respect to global-mean surface air temperature in the multi-model mean. Larger rates of change result if the fractional change is evaluated over a finite change in temperature (e.g., 8.2% K − 1 for a 3 K warming), and rates of change of zonal-mean column water vapor range from 6 to 12% K − 1 depending on latitude. Clausius–Clapeyron scaling is directly evaluated using an invariant distribution of monthly-mean relative humidity, giving a rate of 7.4% K − 1 for global-mean water vapor. There are deviations from Clausius–Clapeyron scaling of zonal-mean column water vapor in the tropics and mid-latitudes, but they largely cancel in the global mean. A purely thermodynamic scaling based on a saturated troposphere gives a higher global rate of 7.9% K − 1. Surface specific humidity increases at a rate of 5.7% K − 1, considerably lower than the rate for global-mean water vapor. Surface specific humidity closely follows Clausius–Clapeyron scaling over ocean. But there are widespread decreases in surface relative humidity over land (by more than 1% K − 1 in many regions), and it is argued that decreases of this magnitude could result from the land/ocean contrast in surface warming.}, author = {O’Gorman, P A and Muller, Caroline J}, issn = {1748-9326}, journal = {Environmental Research Letters}, keywords = {Renewable Energy, Sustainability and the Environment, Public Health, Environmental and Occupational Health, General Environmental Science}, number = {2}, publisher = {IOP Publishing}, title = {{How closely do changes in surface and column water vapor follow Clausius–Clapeyron scaling in climate change simulations?}}, doi = {10.1088/1748-9326/5/2/025207}, volume = {5}, year = {2010}, } @article{920, abstract = {Most eukaryotic cells sense and respond to the mechanical properties of their surroundings. This can strongly influence their collective behavior in embryonic development, tissue function, and wound healing. We use a deformable substrate to measure collective behavior in cell motion due to substrate mediated cell-cell interactions. We quantify spatial and temporal correlations in migration velocity and substrate deformation, and show that cooperative cell-driven patterns of substrate deformation mediate long-distance mechanical coupling between cells and control collective cell migration.}, author = {Angelini, Thomas and Hannezo, Edouard B and Trepat, Xavier and Fredberg, Jeffrey and Weitz, David}, journal = {Physical Review Letters}, number = {16}, publisher = {American Physical Society}, title = {{Cell migration driven by cooperative substrate deformation patterns}}, doi = {10.1103/PhysRevLett.104.168104}, volume = {104}, year = {2010}, } @article{9452, abstract = {Eukaryotic cytosine methylation represses transcription but also occurs in the bodies of active genes, and the extent of methylation biology conservation is unclear. We quantified DNA methylation in 17 eukaryotic genomes and found that gene body methylation is conserved between plants and animals, whereas selective methylation of transposons is not. We show that methylation of plant transposons in the CHG context extends to green algae and that exclusion of histone H2A.Z from methylated DNA is conserved between plants and animals, and we present evidence for RNA-directed DNA methylation of fungal genes. Our data demonstrate that extant DNA methylation systems are mosaics of conserved and derived features, and indicate that gene body methylation is an ancient property of eukaryotic genomes.}, author = {Zemach, Assaf and McDaniel, Ivy E. and Silva, Pedro and Zilberman, Daniel}, issn = {1095-9203}, journal = {Science}, keywords = {Multidisciplinary}, number = {5980}, pages = {916--919}, publisher = {American Association for the Advancement of Science}, title = {{Genome-wide evolutionary analysis of eukaryotic DNA methylation}}, doi = {10.1126/science.1186366}, volume = {328}, year = {2010}, } @article{9485, abstract = {Cytosine methylation silences transposable elements in plants, vertebrates, and fungi but also regulates gene expression. Plant methylation is catalyzed by three families of enzymes, each with a preferred sequence context: CG, CHG (H = A, C, or T), and CHH, with CHH methylation targeted by the RNAi pathway. Arabidopsis thaliana endosperm, a placenta-like tissue that nourishes the embryo, is globally hypomethylated in the CG context while retaining high non-CG methylation. Global methylation dynamics in seeds of cereal crops that provide the bulk of human nutrition remain unknown. Here, we show that rice endosperm DNA is hypomethylated in all sequence contexts. Non-CG methylation is reduced evenly across the genome, whereas CG hypomethylation is localized. CHH methylation of small transposable elements is increased in embryos, suggesting that endosperm demethylation enhances transposon silencing. Genes preferentially expressed in endosperm, including those coding for major storage proteins and starch synthesizing enzymes, are frequently hypomethylated in endosperm, indicating that DNA methylation is a crucial regulator of rice endosperm biogenesis. Our data show that genome-wide reshaping of seed DNA methylation is conserved among angiosperms and has a profound effect on gene expression in cereal crops.}, author = {Zemach, Assaf and Kim, M. Yvonne and Silva, Pedro and Rodrigues, Jessica A. and Dotson, Bradley and Brooks, Matthew D. and Zilberman, Daniel}, issn = {1091-6490}, journal = {Proceedings of the National Academy of Sciences}, number = {43}, pages = {18729--18734}, publisher = {National Academy of Sciences}, title = {{Local DNA hypomethylation activates genes in rice endosperm}}, doi = {10.1073/pnas.1009695107}, volume = {107}, year = {2010}, } @article{9489, abstract = {Cytosine methylation is an ancient process with conserved enzymology but diverse biological functions that include defense against transposable elements and regulation of gene expression. Here we will discuss the evolution and biological significance of eukaryotic DNA methylation, the likely drivers of that evolution, and major remaining mysteries.}, author = {Zemach, Assaf and Zilberman, Daniel}, issn = {1879-0445}, journal = {Current Biology}, number = {17}, pages = {R780--R785}, publisher = {Elsevier}, title = {{Evolution of eukaryotic DNA methylation and the pursuit of safer sex}}, doi = {10.1016/j.cub.2010.07.007}, volume = {20}, year = {2010}, } @article{10127, abstract = {We use numerical simulations to show how noninteracting hard particles binding to a deformable elastic shell may self-assemble into a variety of linear patterns. This is a result of the nontrivial elastic response to deformations of shells. The morphology of the patterns can be controlled by the mechanical properties of the surface, and can be fine-tuned by varying the binding energy of the particles. We also repeat our calculations for a fully flexible chain and find that the chain conformations follow patterns similar to those formed by the nanoparticles under analogous conditions. We propose a simple way of understanding and sorting the different structures and relate it to the underlying shape transition of the shell. Finally, we discuss the implications of our results.}, author = {Šarić, Anđela and Cacciuto, Angelo}, issn = {1744-683X}, journal = {Soft Matter}, keywords = {condensed matter physics, general chemistry}, number = {5}, pages = {1874--1878}, publisher = {Royal Society of Chemistry (RSC)}, title = {{Particle self-assembly on soft elastic shells}}, doi = {10.1039/c0sm01143f}, volume = {7}, year = {2010}, } @article{10128, abstract = {An extensive computational study of the conformational preferences of three capped dipeptides: Ac-Xxx-Phe-NH2, Xxx = Gly, Ala, Val is reported. On the basis of local second-order Møller–Plesset perturbation theory (LMP2) and DFT computations we were able to identify the experimentally observed conformers as γL–γL(g−) and β-turn I(g+) in Ac-Gly-Phe-NH2, and Ac-Ala-Phe-NH2, and as the closely related γL(g+)–γL(g−) and β-turn I(a,g+) in Ac-Val-Phe-NH2. In contrast to the experimental observation that peptides with bulky side chain have a propensity for β-turns, we show that in Ac-Val-Phe-NH2 the minimum energy structure corresponds to the experimentally non detected β-strand.}, author = {Šarić, Anđela and Hrenar, T. and Mališ, M. and Došlić, N.}, issn = {1463-9076}, journal = {Physical Chemistry Chemical Physics}, keywords = {Physical and Theoretical Chemistry, General Physics and Astronomy}, number = {18}, pages = {4678--4685}, publisher = {Royal Society of Chemistry }, title = {{Quantum mechanical study of secondary structure formation in protected dipeptides}}, doi = {10.1039/b923041f}, volume = {12}, year = {2010}, } @article{10390, abstract = {We use numerical simulations to study the phase behavior of a system of purely repulsive soft dumbbells as a function of size ratio of the two components and their relative degree of deformability. We find a plethora of different phases, which includes most of the mesophases observed in self-assembly of block copolymers but also crystalline structures formed by asymmetric, hard binary mixtures. Our results detail the phenomenological behavior of these systems when softness is introduced in terms of two different classes of interparticle interactions: (a) the elastic Hertz potential, which has a finite energy cost for complete overlap of any two components, and (b) a generic power-law repulsion with tunable exponent. We discuss how simple geometric arguments can be used to account for the large structural variety observed in these systems and detail the similarities and differences in the phase behavior for the two classes of potentials under consideration.}, author = {Šarić, Anđela and Bozorgui, Behnaz and Cacciuto, Angelo}, issn = {1520-5207}, journal = {The Journal of Physical Chemistry B}, keywords = {materials chemistry}, number = {22}, pages = {7182--7189}, publisher = {American Chemical Society}, title = {{Packing of soft asymmetric dumbbells}}, doi = {10.1021/jp107545w}, volume = {115}, year = {2010}, } @article{10391, abstract = {We use numerical simulations to show how a fully flexible filament binding to a deformable cylindrical surface may acquire a macroscopic persistence length and a helical conformation. This is a result of the nontrivial elastic response to deformations of elastic sheets. We find that the filament’s helical pitch is completely determined by the mechanical properties of the surface, and can be easily tuned by varying the surface stretching rigidity. We propose simple scaling arguments to understand the physical mechanism behind this phenomenon and present a phase diagram indicating under what conditions one should expect a fully flexible chain to behave as a helical semiflexible filament. Finally, we discuss the implications of our results.}, author = {Šarić, Anđela and Pàmies, Josep C. and Cacciuto, Angelo}, issn = {1079-7114}, journal = {Physical Review Letters}, keywords = {general physics and astronomy}, number = {22}, publisher = {American Physical Society}, title = {{Effective elasticity of a flexible filament bound to a deformable cylindrical surface}}, doi = {10.1103/physrevlett.104.226101}, volume = {104}, year = {2010}, } @inproceedings{1042, abstract = {Recent years have seen tremendous progress in the field of cold and ultracold molecules. A central goal in the field is currently the realization of stable rovibronic ground-state molecular samples in the regime of quantum degeneracy, e.g. in the form of molecular Bose-Einstein condensates, molecular degenerate Fermi gases, or, when an optical lattice is present, molecular Mott-insulator phases. However, molecular samples are not readily cooled to the extremely low temperatures at which quantum degeneracy occurs. In particular, laser cooling, the \'workhorse\' for the field of atomic quantum gases, is generally not applicable to molecular samples. Here we take an important step beyond previous work1 and provide details on the realization of an ultracold quantum gas of ground-state dimer molecules trapped in an optical lattice as recently reported in Ref. 2. We demonstrate full control over all internal and external quantum degrees of freedom for the ground-state molecules by deterministically preparing the molecules in a single quantum state, i.e. in a specific hyperfine sublevel of the rovibronic ground state, while the molecules are trapped in the motional ground state of the individual lattice wells. We circumvent the problem of cooling by associating weakly-bound molecules out of a zero-temperature atomic Mott-insulator state and by transferring these to the absolute ground state in a four-photon STIRAP process. Our preparation procedure directly leads to a long-lived, lattice-trapped molecular many-body state, which we expect to form the platform for many of the envisioned future experiments with molecular quantum gases, e.g. on precision molecular spectroscopy, quantum information science, and dipolar quantum systems.}, author = {Danzl, Johann G and Mark, Manfred and Haller, Elmar and Gustavsson, Mattias and Hart, Russell and Nägerl, Hanns}, pages = {256 -- 269}, publisher = {World Scientific Publishing}, title = {{Production of a quantum gas of rovibronic ground-state molecules in an optical lattice}}, doi = {10.1142/9789814282345_0024}, year = {2010}, } @article{1044, abstract = {Control over all internal and external degrees of freedom of molecules at the level of single quantum states will enable a series of fundamental studies in physics and chemistry1,2. In particular, samples of ground-state molecules at ultralow temperatures and high number densities will facilitate new quantum-gas studies3 and future applications in quantum information science4. However, high phase-space densities for molecular samples are not readily attainable because efficient cooling techniques such as laser cooling are lacking. Here we produce an ultracold and dense sample of molecules in a single hyperfine level of the rovibronic ground state with each molecule individually trapped in the motional ground state of an optical lattice well. Starting from a zero-temperature atomic Mott-insulator state with optimized double-site occupancy6, weakly bound dimer molecules are efficiently associated on a Feshbach resonance7 and subsequently transferred to the rovibronic ground state by a stimulated four-photon process with >50% efficiency. The molecules are trapped in the lattice and have a lifetime of 8 s. Our results present a crucial step towards Bose-Einstein condensation of ground-state molecules and, when suitably generalized to polar heteronuclear molecules, the realization of dipolar quantum-gas phases in optical lattices8-10.}, author = {Danzl, Johann G and Mark, Manfred and Haller, Elmar and Gustavsson, Mattias and Hart, Russell and Aldegunde, Jesus and Hutson, Jeremy and Nägerl, Hanns}, journal = {Nature Physics}, number = {4}, pages = {265 -- 270}, publisher = {Nature Publishing Group}, title = {{An ultracold high-density sample of rovibronic ground-state molecules in an optical lattice}}, doi = {10.1038/nphys1533}, volume = {6}, year = {2010}, } @article{1045, abstract = {We report on the observation of confinement-induced resonances in strongly interacting quantum-gas systems with tunable interactions for one- and two-dimensional geometry. Atom-atom scattering is substantially modified when the s-wave scattering length approaches the length scale associated with the tight transversal confinement, leading to characteristic loss and heating signatures. Upon introducing an anisotropy for the transversal confinement we observe a splitting of the confinement-induced resonance. With increasing anisotropy additional resonances appear. In the limit of a two-dimensional system we find that one resonance persists.}, author = {Haller, Elmar and Mark, Manfred and Hart, Russell and Danzl, Johann G and Reichsöllner, Lukas and Melezhik, Vladimir and Schmelcher, Peter and Nägerl, Hanns}, journal = {Physical Review Letters}, number = {15}, publisher = {American Physical Society}, title = {{Confinement-induced resonances in low-dimensional quantum systems}}, doi = {10.1103/PhysRevLett.104.153203}, volume = {104}, year = {2010}, } @article{1046, abstract = {The phenomenon of matter-wave interference lies at the heart of quantum physics. It has been observed in various contexts in the limit of non-interacting particles as a single-particle effect. Here we observe and control matter-wave interference whose evolution is driven by interparticle interactions. In a multi-path matter-wave interferometer, the macroscopic manybody wave function of an interacting atomic Bose-Einstein condensate develops a regular interference pattern, allowing us to detect and directly visualize the effect of interaction-induced phase shifts. We demonstrate control over the phase evolution by inhibiting interaction-induced dephasing and by refocusing a dephased macroscopic matter wave in a spin-echo-type experiment. Our results show that interactions in a many-body system lead to a surprisingly coherent evolution, possibly enabling narrow-band and high-brightness matterwave interferometers based on atom lasers.}, author = {Gustavsson, Mattias and Haller, Elmar and Mark, Manfred and Danzl, Johann G and Hart, Russell and Daley, Andrew and Nägerl, Hanns}, journal = {New Journal of Physics}, publisher = {IOP Publishing Ltd.}, title = {{Interference of interacting matter waves}}, doi = {10.1088/1367-2630/12/6/065029}, volume = {12}, year = {2010}, } @article{1047, abstract = {Particles in a perfect lattice potential perform Bloch oscillations when subject to a constant force, leading to localization and preventing conductivity. For a weakly interacting Bose-Einstein condensate of Cs atoms, we observe giant center-of-mass oscillations in position space with a displacement across hundreds of lattice sites when we add a periodic modulation to the force near the Bloch frequency. We study the dependence of these "super" Bloch oscillations on lattice depth, modulation amplitude, and modulation frequency and show that they provide a means to induce linear transport in a dissipation-free lattice.}, author = {Haller, Elmar and Hart, Russell and Mark, Manfred and Danzl, Johann G and Reichsöllner, Lukas and Nägerl, Hanns}, journal = {Physical Review Letters}, number = {20}, publisher = {American Physical Society}, title = {{Inducing transport in a dissipation-free lattice with super bloch oscillations}}, doi = {10.1103/PhysRevLett.104.200403}, volume = {104}, year = {2010}, } @article{1049, abstract = {Quantum many-body systems can have phase transitions even at zero temperature; fluctuations arising from Heisenbergĝ€™s uncertainty principle, as opposed to thermal effects, drive the system from one phase to another. Typically, during the transition the relative strength of two competing terms in the systemĝ€™s Hamiltonian changes across a finite critical value. A well-known example is the Mottĝ€" Hubbard quantum phase transition from a superfluid to an insulating phase, which has been observed for weakly interacting bosonic atomic gases. However, for strongly interacting quantum systems confined to lower-dimensional geometry, a novel type of quantum phase transition may be induced and driven by an arbitrarily weak perturbation to the Hamiltonian. Here we observe such an effectĝ€"the sineĝ€"Gordon quantum phase transition from a superfluid Luttinger liquid to a Mott insulatorĝ€ "in a one-dimensional quantum gas of bosonic caesium atoms with tunable interactions. For sufficiently strong interactions, the transition is induced by adding an arbitrarily weak optical lattice commensurate with the atomic granularity, which leads to immediate pinning of the atoms. We map out the phase diagram and find that our measurements in the strongly interacting regime agree well with a quantum field description based on the exactly solvable sineĝ€"Gordon model. We trace the phase boundary all the way to the weakly interacting regime, where we find good agreement with the predictions of the one-dimensional Boseĝ€"Hubbard model. Our results open up the experimental study of quantum phase transitions, criticality and transport phenomena beyond Hubbard-type models in the context of ultracold gases.}, author = {Haller, Elmar and Hart, Russell and Mark, Manfred and Danzl, Johann G and Reichsöllner, Lukas and Gustavsson, Mattias and Dalmonte, Marcello and Pupillo, Guido and Nägerl, Hanns}, journal = {Nature}, number = {7306}, pages = {597 -- 600}, publisher = {Nature Publishing Group}, title = {{Pinning quantum phase transition for a Luttinger liquid of strongly interacting bosons}}, doi = {10.1038/nature09259}, volume = {466}, year = {2010}, } @inproceedings{11797, abstract = {Inspired by online ad allocation, we study online stochastic packing integer programs from theoretical and practical standpoints. We first present a near-optimal online algorithm for a general class of packing integer programs which model various online resource allocation problems including online variants of routing, ad allocations, generalized assignment, and combinatorial auctions. As our main theoretical result, we prove that a simple dual training-based algorithm achieves a (1 − o(1))-approximation guarantee in the random order stochastic model. This is a significant improvement over logarithmic or constant-factor approximations for the adversarial variants of the same problems (e.g. factor 1−1𝑒 for online ad allocation, and log(m) for online routing). We then focus on the online display ad allocation problem and study the efficiency and fairness of various training-based and online allocation algorithms on data sets collected from real-life display ad allocation system. Our experimental evaluation confirms the effectiveness of training-based algorithms on real data sets, and also indicates an intrinsic trade-off between fairness and efficiency.}, author = {Feldman, Jon and Henzinger, Monika H and Korula, Nitish and Mirrokni, Vahab S. and Stein, Cliff}, booktitle = {18th Annual European Symposium on Algorithms}, isbn = {3642157742}, issn = {1611-3349}, location = {Liverpool, United Kingdom}, pages = {182–194}, publisher = {Springer Nature}, title = {{Online stochastic packing applied to display ad allocation}}, doi = {10.1007/978-3-642-15775-2_16}, volume = {6346}, year = {2010}, } @inproceedings{11798, abstract = {Starting with two models fifty years ago, the discrete marriage game [1] and the continuous assignment game [2], the study of stable matchings has evolved into a rich theory with applications in many areas. Most notably, it has lead to a number of truthful mechanisms that have seen a recent rejuvenation in the context of sponsored search. In this paper we survey the history of these problems and provide several links to ongoing research in the field.}, author = {Dütting, Paul and Henzinger, Monika H}, booktitle = {7th International Conference on Algorithms and Complexity}, isbn = {9783642130724}, issn = {1611-3349}, location = {Rome, Italy}, pages = {6–12}, publisher = {Springer Nature}, title = {{Mechanisms for the marriage and the assignment game}}, doi = {10.1007/978-3-642-13073-1_2}, volume = {6078}, year = {2010}, } @inproceedings{11838, abstract = {Two-sided matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market where $n$ advertisers compete for the assignment of one of $k$ sponsored search results, also known as ``slots'', for certain keywords they are interested in. Here, as in other markets of that kind, market equilibria correspond to stable matchings. In this paper, we show how to modify Kuhn's Hungarian Method (Kuhn, 1955) so that it finds an optimal stable matching between advertisers and advertising slots in settings with generalized linear utilities, per-bidder-item reserve prices, and per-bidder-item maximum prices. The only algorithm for this problem presented so far (Aggarwal et al., 2009) requires the market to be in ''general position''. We do not make this assumption.}, author = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, isbn = {978-3-939897-16-3}, issn = {1868-8969}, location = {Nancy, France}, pages = {287--298}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Sponsored search, market equilibria, and the Hungarian Method}}, doi = {10.4230/LIPICS.STACS.2010.2463}, volume = {5}, year = {2010}, }