Search

We investigate the problem of Min-cost Perfect Matching with Delays (MPMD) in which requests are pairwise matched in an online fashion with the objective to minimize the sum of space cost and time cost. Though linear-MPMD (i.e., time cost is linear in delay) has been thoroughly studied in the literature, it does not well model impatient requests that are common in practice. Thus, we propose convex-MPMD where time cost functions are convex, capturing the situation where time cost increases faster and faster. Since the existing algorithms for linear-MPMD are not competitive any more, we devise a new deterministic algorithm for convex-MPMD problems. For a large class of convex time cost functions, our algorithm achieves a competitive ratio of $O(k)$ on any $k$-point uniform metric space, or $O(k\Delta)$ when the metric space has aspect ratio $\Delta$. Moreover, we prove lower bounds for the competitive ratio of deterministic and randomized algorithms, indicating that our deterministic algorithm is optimal. This optimality uncover a substantial difference between convex-MPMD and linear-MPMD, since linear-MPMD allows a deterministic algorithm with constant competitive ratio on any uniform metric space.

Span extraction, aiming to extract text spans (such as words or phrases) from plain texts, is a fundamental process in Information Extraction. Recent works introduce the label knowledge to enhance the text representation by formalizing the span extraction task into a question answering problem (QA Formalization), which achieves state-of-the-art performance. However, QA Formalization does not fully exploit the label knowledge and suffers from low efficiency in training/inference. To address those problems, we introduce a new paradigm to integrate label knowledge and further propose a novel model to explicitly and efficiently integrate label knowledge into text representations. Specifically, it encodes texts and label annotations independently and then integrates label knowledge into text representation with an elaborate-designed semantics fusion module. We conduct extensive experiments on three typical span extraction tasks: flat NER, nested NER, and event detection. The empirical results show that 1) our method achieves state-of-the-art performance on four benchmarks, and 2) reduces training time and inference time by 76% and 77% on average, respectively, compared with the QA Formalization paradigm. Our code and data are available at https://github.com/Akeepers/LEAR., Accepted to the main conference of EMNLP 2021 (long paper)

Carbon–carbon bond-forming reductive elimination from elusive organocopper(III) complexes has been considered the key step in many copper-catalyzed and organocuprate reactions. However, organocopper(III) complexes with well-defined structures that can undergo reductive elimination are extremely rare, especially for the formation of Csp^3–Csp^3 bonds. We report herein a general method for the synthesis of a series of [alkyl-Cu^(III)-(CF_3)_3]^− complexes, the structures of which have been unequivocally characterized by NMR spectroscopy, mass spectrometry, and X-ray crystal diffraction. At elevated temperature, these complexes undergo reductive elimination following first-order kinetics, forming alkyl-CF3 products with good yields (up to 91%). Both kinetic studies and DFT calculations indicate that the reductive elimination to form Csp^3–CF^3 bonds proceeds through a concerted transition state, with a ΔH⧧ = 20 kcal/mol barrier.

Reported here is the chelate effect as a design principle for tuning heterogeneous catalysts for electrochemical CO2 reduction. Palladium functionalized with a chelating tris-N-heterocyclic carbene (NHC) ligand (Pd-timtmbMe ) exhibits a 32-fold increase in activity for electrochemical reduction of CO2 to C1 products with high Faradaic efficiency (FEC1 =86 %) compared to the parent unfunctionalized Pd foil (FE=23 %), and with sustained activity relative to a monodentate NHC-ligated Pd electrode (Pd-mimtmbMe ). The results highlight the contributions of the chelate effect for tailoring and maintaining reactivity at molecular-materials interfaces enabled by surface organometallic chemistry.

We investigate the problem of Min-cost Perfect Matching with Delays (MPMD) in which requests are pairwise matched in an online fashion with the objective to minimize the sum of space cost and time cost. Though linear-MPMD (i.e., time cost is linear in delay) has been thoroughly studied in the literature, it does not well model impatient requests that are common in practice. Thus, we propose convex-MPMD where time cost functions are convex, capturing the situation where time cost increases faster and faster. Since the existing algorithms for linear-MPMD are not competitive any more, we devise a new deterministic algorithm for convex-MPMD problems. For a large class of convex time cost functions, our algorithm achieves a competitive ratio of O(k) on any k-point uniform metric space. Moreover, our deterministic algorithm is asymptotically optimal, which uncover a substantial difference between convex-MPMD and linear-MPMD which allows a deterministic algorithm with constant competitive ratio on any uniform metric space., Leibniz International Proceedings in Informatics (LIPIcs), 123, ISSN:1868-8969, 29th International Symposium on Algorithms and Computation (ISAAC 2018), ISBN:978-3-95977-094-1

According to the failure characteristics of asphalt overlay on rigid pavement, a special-purpose test apparatus and method were developed for interlaminar shear fatigue tests to evaluate interlaminar shear fatigue of asphalt overlay on rigid pavement, and an interlaminar shear fatigue equation was determined by analyzing the correlation between fatigue life and shear stress obtained from interlaminar shear fatigue tests. The damage mechanics theory, heat transfer theory and the Finite Element Method (FEM) were adopted to analyze fatigue damage characteristics and cracking mechanism of asphalt layer. The result showed that under repeated traffic loading, the asphalt layer located at the existing transverse joints of the rigid base on the side of traffic loading, is prone to fatigue cracking, and the crack extends upward along the tip due to the tensile stress; thermal fatigue damage occurs mainly on the surface of asphalt overlay, the horizontal tensile stress on the surface of asphalt overlay decreases linearly with the increase of temperature variation times, and the fatigue life of asphalt overlay decreases with the increase of the amplitude of temperature variation; and it is recommended to choose asphalt mixtures with features such as relatively low thermo-contraction character, low modulus and high tensile strength to guarantee the expected cracking resistance and durability of asphalt overlay on rigid pavement.

A tight criterion under which the abstract version Lov\'asz Local Lemma (abstract-LLL) holds was given by Shearer decades ago. However, little is known about that of the variable version LLL (variable-LLL) where events are generated by independent random variables, though this model of events is applicable to almost all applications of LLL. We introduce a necessary and sufficient criterion for variable-LLL, in terms of the probabilities of the events and the event-variable graph specifying the dependency among the events. Based on this new criterion, we obtain boundaries for two families of event-variable graphs, namely, cyclic and treelike bigraphs. These are the first two non-trivial cases where the variable-LLL boundary is fully determined. As a byproduct, we also provide a universal constructive method to find a set of events whose union has the maximum probability, given the probability vector and the event-variable graph. Though it is #P-hard in general to determine variable-LLL boundaries, we can to some extent decide whether a gap exists between a variable-LLL boundary and the corresponding abstract-LLL boundary. In particular, we show that the gap existence can be decided without solving Shearer's conditions or checking our variable-LLL criterion. Equipped with this powerful theorem, we show that there is no gap if the base graph of the event-variable graph is a tree, while gap appears if the base graph has an induced cycle of length at least 4. The problem is almost completely solved except when the base graph has only 3-cliques, in which case we also get partial solutions. A set of reduction rules are established that facilitate to infer gap existence of an event-variable graph from known ones. As an application, various event-variable graphs, in particular combinatorial ones, are shown to be gapful/gapless., Comment: Part of the work has been published at FOCS2017

The demand for multi-dimensional range query over Distributed Ordered Table (DOT) has become increasingly popular, however, the DOT does not support queries very well other than the primary key. One solution to this problem is indexing. Many indexing techniques are focusing on how to improve the query ability, but do not care about the consistency between the index table and base data table. This paper focuses on the relationship between the consistency and the performance about the indexing techniques. In this paper, we give the definition about the consistency between the index table and the base data table, and present the inconsistency window to measure the degree of consistency. We classify the existing indexing techniques into four categories: sync, async-compact, async-insert and async-simple, according to their implementation in terms of how the index is maintained. Experimental results confirm that async indexing technique have better performance compared with sync indexing technique but with worse consistency. For async indexing techniques, the performance of async-simple is about 1.86x to 6.26x compared with async-insert but with similar consistency.

A tight criterion under which the abstract version Lov��sz Local Lemma (abstract-LLL) holds was given by Shearer decades ago. However, little is known about that of the variable version LLL (variable-LLL) where events are generated by independent random variables, though this model of events is applicable to almost all applications of LLL. We introduce a necessary and sufficient criterion for variable-LLL, in terms of the probabilities of the events and the event-variable graph specifying the dependency among the events. Based on this new criterion, we obtain boundaries for two families of event-variable graphs, namely, cyclic and treelike bigraphs. These are the first two non-trivial cases where the variable-LLL boundary is fully determined. As a byproduct, we also provide a universal constructive method to find a set of events whose union has the maximum probability, given the probability vector and the event-variable graph. Though it is #P-hard in general to determine variable-LLL boundaries, we can to some extent decide whether a gap exists between a variable-LLL boundary and the corresponding abstract-LLL boundary. In particular, we show that the gap existence can be decided without solving Shearer's conditions or checking our variable-LLL criterion. Equipped with this powerful theorem, we show that there is no gap if the base graph of the event-variable graph is a tree, while gap appears if the base graph has an induced cycle of length at least 4. The problem is almost completely solved except when the base graph has only 3-cliques, in which case we also get partial solutions. A set of reduction rules are established that facilitate to infer gap existence of an event-variable graph from known ones. As an application, various event-variable graphs, in particular combinatorial ones, are shown to be gapful/gapless., Part of the work has been published at FOCS2017

In this paper we investigate the top-$k$-selection problem, i.e. determine the largest, second largest, ..., and the $k$-th largest elements, in the dynamic data model. In this model the order of elements evolves dynamically over time. In each time step the algorithm can only probe the changes of data by comparing a pair of elements. Previously only two special cases were studied[2]: finding the largest element and the median; and sorting all elements. This paper systematically deals with $k\in [n]$ and solves the problem almost completely. Specifically, we identify a critical point $k^*$ such that the top-$k$-selection problem can be solved error-free with probability $1-o(1)$ if and only if $k=o(k^*)$. A lower bound of the error when $k=\Omega(k^*)$ is also determined, which actually is tight under some condition. On the other hand, it is shown that the top-$k$-set problem, which means finding the largest $k$ elements without sorting them, can be solved error-free for all $k\in [n]$. Additionally, we extend the dynamic data model and show that most of these results still hold., Comment: 23 pages, 2 figures

In recent years there have been numerous meetings and discussions reported in local and national newspapers about the advantages and disadvantages of Chinese culture and traditions. These include the Forum on the Study of Chinese Cultural History held in December 1982, the Seminar on Comparative Studies of Eastern and Western Cultures in 1984, and two additional workshops on the same topics in 1985. In these sessions many cultural experts were invited to air their views and findings.