@article{116, abstract = {We describe a model experiment for dynamic jamming: a two-dimensional collection of initially unjammed disks that are forced into the jammed state by uniaxial compression via a rake. This leads to a stable densification front that travels ahead of the rake, leaving regions behind it jammed. Using disk conservation in conjunction with an upper limit to the packing fraction at jamming onset, we predict the front speed as a function of packing fraction and rake speed. However, we find that the jamming front has a finite width, a feature that cannot be explained by disk conservation alone. This width appears to diverge on approach to jamming, which suggests that it may be related to growing lengthscales encountered in other jamming studies.}, author = {Waitukaitis, Scott R and Roth, Leah and Vitelli, Vincenzo and Jaeger, Heinrich}, journal = {EPL}, number = {4}, publisher = {Elsevier}, title = {{Dynamic jamming fronts}}, doi = {10.1209/0295-5075/102/44001}, volume = {102}, year = {2013}, } @article{11671, abstract = {Given only the URL of a Web page, can we identify its language? In this article we examine this question. URL-based language classification is useful when the content of the Web page is not available or downloading the content is a waste of bandwidth and time. We built URL-based language classifiers for English, German, French, Spanish, and Italian by applying a variety of algorithms and features. As algorithms we used machine learning algorithms which are widely applied for text classification and state-of-art algorithms for language identification of text. As features we used words, various sized n-grams, and custom-made features (our novel feature set). We compared our approaches with two baseline methods, namely classification by country code top-level domains and classification by IP addresses of the hosting Web servers. We trained and tested our classifiers in a 10-fold cross-validation setup on a dataset obtained from the Open Directory Project and from querying a commercial search engine. We obtained the lowest F1-measure for English (94) and the highest F1-measure for German (98) with the best performing classifiers. We also evaluated the performance of our methods: (i) on a set of Web pages written in Adobe Flash and (ii) as part of a language-focused crawler. In the first case, the content of the Web page is hard to extract and in the second page downloading pages of the “wrong” language constitutes a waste of bandwidth. In both settings the best classifiers have a high accuracy with an F1-measure between 95 (for English) and 98 (for Italian) for the Adobe Flash pages and a precision between 90 (for Italian) and 97 (for French) for the language-focused crawler.}, author = {Baykan, Eda and Weber, Ingmar and Henzinger, Monika H}, issn = {1559-114X}, journal = {ACM Transactions on the Web}, keywords = {Computer Networks and Communications}, number = {1}, publisher = {Association for Computing Machinery}, title = {{A comprehensive study of techniques for URL-based web page language classification}}, doi = {10.1145/2435215.2435218}, volume = {7}, year = {2013}, } @inproceedings{117, abstract = {The packing arrangement of individual particles inside a granular material and the resulting response to applied stresses depend critically on particle-particle interactions. One aspect that recently received attention are nanoscale surface features of particles, which play an important role in determining the strength of cohesive van der Waals and capillary interactions and also affect tribo-charging of grains. We describe experiments on freely falling granular streams that can detect the contributions from all three of these forces. We show that it is possible to measure the charge of individual grains and build up distributions that are detailed enough to provide stringent tests of tribo-charging models currently available. A second aspect concerns particle shape. In this case steric interactions become important and new types of aggregate behavior can be expected when non-convex particle shapes are considered that can interlock or entangle. However, a general connection between the mechanical response of a granular material and the constituents\' shape remains unknown. This has made it infeasible to tackle the "inverse packing problem", namely to start from a given, desired behavior for the aggregate as a whole and then find the particle shape the produces it. We discuss a new approach, using concepts rooted in artificial evolution that provides a way to solve this inverse problem. This approach facilitates exploring the role of arbitrary particle geometry in jammed systems and invites the discovery and design of granular matter with optimized properties.}, author = {Jaeger, Heinrich and Miskin, Marc and Waitukaitis, Scott R}, booktitle = { AIP Conference Proceedings}, location = {Sydney, Australia}, pages = {3 -- 6}, publisher = {AIP}, title = {{From nanoscale cohesion to macroscale entanglement: opportunities for designing granular aggregate behaviour by tailoring grain shape and interactions}}, doi = {10.1063/1.4811858}, volume = {1542}, year = {2013}, } @article{11759, abstract = {Matching markets play a prominent role in economic theory. A prime example of such a market is the sponsored search market. Here, as in other markets of that kind, market equilibria correspond to feasible, envy free, and bidder optimal outcomes. For settings without budgets such an outcome always exists and can be computed in polynomial-time by the so-called Hungarian Method. Moreover, every mechanism that computes such an outcome is incentive compatible. We show that the Hungarian Method can be modified so that it finds a feasible, envy free, and bidder optimal outcome for settings with budgets. We also show that in settings with budgets no mechanism that computes such an outcome can be incentive compatible for all inputs. For inputs in general position, however, the presented mechanism—as any other mechanism that computes such an outcome for settings with budgets—is incentive compatible.}, author = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar}, issn = {0020-0190}, journal = {Information Processing Letters}, number = {3}, pages = {67--73}, publisher = {Elsevier}, title = {{Sponsored search, market equilibria, and the Hungarian Method}}, doi = {10.1016/j.ipl.2012.11.006}, volume = {113}, year = {2013}, } @inproceedings{11793, abstract = {We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We show (1 + ε)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. This breaks the Θ(D) time bound of recomputing “from scratch”. Our technique also leads to a (1 + ε)-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of [9] that is optimal under some assumptions [27]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if a small approximation is allowed.}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, booktitle = {40th International Colloquium on Automata, Languages, and Programming}, isbn = {9783642392115}, issn = {1611-3349}, location = {Riga, Latvia}, pages = {607–619}, publisher = {Springer Nature}, title = {{Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks}}, doi = {10.1007/978-3-642-39212-2_53}, volume = {7966}, year = {2013}, } @inproceedings{11791, abstract = {The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions the truthful direct-revelation mechanism that maximizes social welfare is the VCG mechanism. For many valuation spaces computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that the welfare loss increases in expressiveness. All our bounds apply to equilibrium concepts that can be computed in polynomial time as well as to learning outcomes.}, author = {Dütting, Paul and Henzinger, Monika H and Starnberger, Martin}, booktitle = {9th International Conference on Web and Internet Economics}, isbn = {9783642450457}, issn = {1611-3349}, location = {Cambridge, MA, USA}, pages = {146–159}, publisher = {Springer Nature}, title = {{Valuation compressions in VCG-based combinatorial auctions}}, doi = {10.1007/978-3-642-45046-4_13}, volume = {8289}, year = {2013}, } @inproceedings{11792, abstract = {We study the problem of maximizing a monotone submodular function with viability constraints. This problem originates from computational biology, where we are given a phylogenetic tree over a set of species and a directed graph, the so-called food web, encoding viability constraints between these species. These food webs usually have constant depth. The goal is to select a subset of k species that satisfies the viability constraints and has maximal phylogenetic diversity. As this problem is known to be NP-hard, we investigate approximation algorithm. We present the first constant factor approximation algorithm if the depth is constant. Its approximation ratio is (1−1𝑒√). This algorithm not only applies to phylogenetic trees with viability constraints but for arbitrary monotone submodular set functions with viability constraints. Second, we show that there is no (1 − 1/e + ε)-approximation algorithm for our problem setting (even for additive functions) and that there is no approximation algorithm for a slight extension of this setting.}, author = {Dvořák, Wolfgang and Henzinger, Monika H and Williamson, David P.}, booktitle = {21st Annual European Symposium on Algorithms}, isbn = {9783642404498}, issn = {1611-3349}, location = {Sophia Antipolis, France}, pages = {409 -- 420}, publisher = {Springer Nature}, title = {{Maximizing a submodular function with viability constraints}}, doi = {10.1007/978-3-642-40450-4_35}, volume = {8125}, year = {2013}, } @inproceedings{11856, abstract = {We study dynamic (1 + ϵ)-approximation algorithms for the all-pairs shortest paths problem in unweighted undirected n-node m-edge graphs under edge deletions. The fastest algorithm for this problem is a randomized algorithm with a total update time of Ȏ(mn) and constant query time by Roditty and Zwick (FOCS 2004). The fastest deterministic algorithm is from a 1981 paper by Even and Shiloach (JACM 1981); it has a total update time of O(mn 2 ) and constant query time. We improve these results as follows: (1) We present an algorithm with a total update time of Ȏ(n 5/2 ) and constant query time that has an additive error of two in addition to the 1 + ϵ multiplicative error. This beats the previous Ȏ(mn) time when m = Ω(n 3/2 ). Note that the additive error is unavoidable since, even in the static case, an O(n 3-δ )-time (a so-called truly sub cubic) combinatorial algorithm with 1 + ϵ multiplicative error cannot have an additive error less than 2 - ϵ, unless we make a major breakthrough for Boolean matrix multiplication (Dor, Halperin and Zwick FOCS 1996) and many other long-standing problems (Vassilevska Williams and Williams FOCS 2010). The algorithm can also be turned into a (2 + ϵ)-approximation algorithm (without an additive error) with the same time guarantees, improving the recent (3 + ϵ)-approximation algorithm with Ȏ(n 5/2+O(1√(log n)) ) running time of Bernstein and Roditty (SODA 2011) in terms of both approximation and time guarantees. (2) We present a deterministic algorithm with a total update time of Ȏ(mn) and a query time of O(log log n). The algorithm has a multiplicative error of 1 + ϵ and gives the first improved deterministic algorithm since 1981. It also answers an open question raised by Bernstein in his STOC 2013 paper. In order to achieve our results, we introduce two new techniques: (1) A lazy Even-Shiloach tree algorithm which maintains a bounded-distance shortest-paths tree on a certain type of emulator called locally persevering emulator. (2) A derandomization technique based on moving Even-Shiloach trees as a way to derandomize the standard random set argument. These techniques might be of independent interest.}, author = {Henzinger, Monika H and Krinninger, Sebastian and Nanongkai, Danupon}, booktitle = {54th Annual Symposium on Foundations of Computer Science}, issn = {0272-5428}, location = {Berkeley, CA, United States}, pages = {538--547}, publisher = {Institute of Electrical and Electronics Engineers}, title = {{Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization}}, doi = {10.1109/focs.2013.64}, year = {2013}, } @article{11902, abstract = {We study the problem of matching bidders to items where each bidder i has general, strictly monotonic utility functions ui,j(pj) expressing his utility of being matched to item j at price pj. For this setting we prove that a bidder optimal outcome always exists, even when the utility functions are non-linear and non-continuous. We give sufficient conditions under which every mechanism that finds a bidder optimal outcome is incentive compatible. We also give a mechanism that finds a bidder optimal outcome if the conditions for incentive compatibility are satisfied. The running time of this mechanism is exponential in the number of items, but polynomial in the number of bidders.}, author = {Dütting, Paul and Henzinger, Monika H and Weber, Ingmar}, issn = {0304-3975}, journal = {Theoretical Computer Science}, number = {3}, pages = {22--32}, publisher = {Elsevier}, title = {{Bidder optimal assignments for general utilities}}, doi = {10.1016/j.tcs.2013.01.030}, volume = {478}, year = {2013}, } @article{11959, abstract = {No catalyst required! A highly efficient, catalyst-free process to generate diimide in situ from hydrazine monohydrate and molecular oxygen for the selective reduction of alkenes has been developed. The use of a gas–liquid segmented flow system allowed safe operating conditions and dramatically enhanced this atom-economical reaction, resulting in short processing times.}, author = {Pieber, Bartholomäus and Martinez, Sabrina Teixeira and Cantillo, David and Kappe, C. Oliver}, issn = {1521-3773}, journal = {Angewandte Chemie International Edition}, number = {39}, pages = {10241--10244}, publisher = {Wiley}, title = {{In situ generation of diimide from hydrazine and oxygen: Continuous-flow transfer hydrogenation of olefins}}, doi = {10.1002/anie.201303528}, volume = {52}, year = {2013}, }