Changjun Wang

Xujin Chen, Xiaodong Hu, Changjun Wang et al.

This paper studies an online trading variant of the classical secretary problem, called secretary problem variant trading (SPVT), from the perspective of an intermediary who facilitates trade between a seller and $n$ buyers (collectively referred to as agents). The seller has an item, and each buyer demands the item. These agents arrive sequentially in a uniformly random order to meet the intermediary, each revealing their valuation of the item upon arrival. After each arrival, the intermediary must make an immediate and irrevocable decision before the next agent appears. The intermediary's objective is to maximize the price of the agent who ultimately holds the item at the end of the process. We evaluate the performance of online algorithms for SPVT using two notions of competitive ratio: strong and weak. The strong notion benchmarks the online algorithm against a powerful offline optimum: the highest price among the $n+1$ agents. We propose an online algorithm for SPVT achieving a strong competitive ratio of $\frac{4e^2}{e^2+1} \approx 3.523$, which is the best possible even when the seller's price may be zero. This tight ratio closes the gap between the previous best upper bound of $4.189$ and lower bound of $3.258$. In contrast, the weak notion restricts the offline optimal algorithm to the given arrival order. The offline algorithm can no longer alter the predetermined arrival order to always place the item in the hands of the agent offering the highest price. Against this weaker benchmark, we design a simple online algorithm for SPVT, achieving a weak competitive ratio of $2$. We further investigate the special case in which the seller's price is zero. For this special SPVT, we develop a double-threshold algorithm achieving a weak competitive ratio of at most $1.83683$ and establish a lower bound of $1.76239$.

Changjun Wang, Chenhao Wang

We study a new bilevel optimization problem, termed the Randomized Max-Vertex-Cover Interdiction (RMVCI) problem under matroid constraints, which can be modeled as a zero-sum Stackelberg game on a network between a leader and a follower. The leader randomly selects a subset of vertices to protect, subject to a matroid constraint, while the follower-after inferring the leader's protection probability distribution-chooses a subset of vertices (also matroid-constrained) to attack, aiming to maximize the expected total weight of edges incident to the set of vertices that are both attacked and unprotected. The leader's objective is to determine an optimal randomized interdiction strategy that minimizes the follower's expected payoff. Since the follower's response problem is NP-hard, the resulting bilevel program is computationally challenging. We develop a conceptual approximation framework for tackling general bilevel interdiction problems. For the RMVCI problem under matroid constraints, we first formulate the follower's problem as an integer linear program and show that its linear relaxation admits a tight integrality gap of $\tfrac{4}{3}$. Within the approximation framework, we replace the follower's problem by its LP relaxation, and then study the resulting bilevel program. By shifting from distributions over sets to distributions over vertices and applying our approximation framework, we manage to design a polynomial-time 2-approximation algorithm for this relaxed bilevel problem. Combining these ingredients within our framework yields a polynomial-time $\tfrac{8}{3}$-approximation algorithm for RMVCI under matroid constraints.

Bi-Ying Yan, Chao Yang, Feng Chen et al.

With the goal of predicting the future rainfall intensity in a local region over a relatively short period time, precipitation nowcasting has been a long-time scientific challenge with great social and economic impact. The radar echo extrapolation approaches for precipitation nowcasting take radar echo images as input, aiming to generate future radar echo images by learning from the historical images. To effectively handle complex and high non-stationary evolution of radar echoes, we propose to decompose the movement into optical flow field motion and morphologic deformation. Following this idea, we introduce Flow-Deformation Network (FDNet), a neural network that models flow and deformation in two parallel cross pathways. The flow encoder captures the optical flow field motion between consecutive images and the deformation encoder distinguishes the change of shape from the translational motion of radar echoes. We evaluate the proposed network architecture on two real-world radar echo datasets. Our model achieves state-of-the-art prediction results compared with recent approaches. To the best of our knowledge, this is the first network architecture with flow and deformation separation to model the evolution of radar echoes for precipitation nowcasting. We believe that the general idea of this work could not only inspire much more effective approaches but also be applied to other similar spatiotemporal prediction tasks

Huiqiang Liao, Guihua Wen, Yang Hu et al.

In Traditional Chinese Medicine (TCM), facial features are important basis for diagnosis and treatment. A doctor of TCM can prescribe according to a patient's physical indicators such as face, tongue, voice, symptoms, pulse. Previous works analyze and generate prescription according to symptoms. However, research work to mine the association between facial features and prescriptions has not been found for the time being. In this work, we try to use deep learning methods to mine the relationship between the patient's face and herbal prescriptions (TCM prescriptions), and propose to construct convolutional neural networks that generate TCM prescriptions according to the patient's face image. It is a novel and challenging job. In order to mine features from different granularities of faces, we design a multi-scale convolutional neural network based on three-grained face, which mines the patient's face information from the organs, local regions, and the entire face. Our experiments show that convolutional neural networks can learn relevant information from face to prescribe, and the multi-scale convolutional neural networks based on three-grained face perform better.

Yang Hu, Guihua Wen, Huiqiang Liao et al.

The tongue image provides important physical information of humans. It is of great importance for diagnoses and treatments in clinical medicine. Herbal prescriptions are simple, noninvasive and have low side effects. Thus, they are widely applied in China. Studies on the automatic construction technology of herbal prescriptions based on tongue images have great significance for deep learning to explore the relevance of tongue images for herbal prescriptions, it can be applied to healthcare services in mobile medical systems. In order to adapt to the tongue image in a variety of photographic environments and construct herbal prescriptions, a neural network framework for prescription construction is designed. It includes single/double convolution channels and fully connected layers. Furthermore, it proposes the auxiliary therapy topic loss mechanism to model the therapy of Chinese doctors and alleviate the interference of sparse output labels on the diversity of results. The experiment use the real world tongue images and the corresponding prescriptions and the results can generate prescriptions that are close to the real samples, which verifies the feasibility of the proposed method for the automatic construction of herbal prescriptions from tongue images. Also, it provides a reference for automatic herbal prescription construction from more physical information.