Given an undirected graph $G=(V,E)$ with a nonnegative edge length function and an integer $p$, $0 < p < |V|$, the $p$-centdian problem is to find $p$ vertices (called the {\it centdian set}) of $V$ such that the {\it eccentricity} plus {\it median-distance} is minimized, in which the {\it eccentricity} is the maximum (length) distance of all vertices to their nearest {\it centdian set} and the {\it median-distance} is the total (length) distance of all vertices to their nearest {\it centdian set}. The {\it eccentricity} plus {\it median-distance} is called the {\it centdian-distance}. The purpose of the $p$-centdian problem is to find $p$ open facilities (servers) which satisfy the quality-of-service of the minimum total distance ({\it median-distance}) and the maximum distance ({\it eccentricity}) to their service customers, simultaneously. If we converse the two criteria, that is given the bound of the {\it centdian-distance} and the objective function is to minimize the cardinality of the {\it centdian set}, this problem is called the converse centdian problem. In this paper, we prove the $p$-centdian problem is NP-Complete. Then we design the first non-trivial brute force exact algorithms for the $p$-centdian problem and the converse centdian problem, respectively. Finally, we design two approximation algorithms for both problems.
相關內容
For optimal control problems constrained by a initial-valued parabolic PDE, we have to solve a large scale saddle point algebraic system consisting of considering the discrete space and time points all together. A popular strategy to handle such a system is the Krylov subspace method, for which an efficient preconditioner plays a crucial role. The matching-Schur-complement preconditioner has been extensively studied in literature and the implementation of this preconditioner lies in solving the underlying PDEs twice, sequentially in time. In this paper, we propose a new preconditioner for the Schur complement, which can be used parallel-in-time (PinT) via the so called diagonalization technique. We show that the eigenvalues of the preconditioned matrix are low and upper bounded by positive constants independent of matrix size and the regularization parameter. The uniform boundedness of the eigenvalues leads to an optimal linear convergence rate of conjugate gradient solver for the preconditioned Schur complement system. To the best of our knowledge, it is the first time to have an optimal convergence analysis for a PinT preconditioning technique of the optimal control problem. Numerical results are reported to show that the performance of the proposed preconditioner is robust with respect to the discretization step-sizes and the regularization parameter.
The performance of large-scale computing systems often critically depends on high-performance communication networks. Dynamically reconfigurable topologies, e.g., based on optical circuit switches, are emerging as an innovative new technology to deal with the explosive growth of datacenter traffic. Specifically, \emph{periodic} reconfigurable datacenter networks (RDCNs) such as RotorNet (SIGCOMM 2017), Opera (NSDI 2020) and Sirius (SIGCOMM 2020) have been shown to provide high throughput, by emulating a \emph{complete graph} through fast periodic circuit switch scheduling. However, to achieve such a high throughput, existing reconfigurable network designs pay a high price: in terms of potentially high delays, but also, as we show as a first contribution in this paper, in terms of the high buffer requirements. In particular, we show that under buffer constraints, emulating the high-throughput complete graph is infeasible at scale, and we uncover a spectrum of unvisited and attractive alternative RDCNs, which emulate regular graphs, but with lower node degree than the complete graph. We present Mars, a periodic reconfigurable topology which emulates a $d$-regular graph with near-optimal throughput. In particular, we systematically analyze how the degree~$d$ can be optimized for throughput given the available buffer and delay tolerance of the datacenter. We further show empirically that Mars achieves higher throughput compared to existing systems when buffer sizes are bounded.
This paper investigates the orthogonal time frequency space (OTFS) transmission for enabling ultra-reliable low-latency communications (URLLC). To guarantee excellent reliability performance, pragmatic precoder design is an effective and indispensable solution. However, the design requires accurate instantaneous channel state information at the transmitter (ICSIT) which is not always available in practice. Motivated by this, we adopt a deep learning (DL) approach to exploit implicit features from estimated historical delay-Doppler domain channels (DDCs) to directly predict the precoder to be adopted in the next time frame for minimizing the frame error rate (FER), that can further improve the system reliability without the acquisition of ICSIT. To this end, we first establish a predictive transmission protocol and formulate a general problem for the precoder design where a closed-form theoretical FER expression is derived serving as the objective function to characterize the system reliability. Then, we propose a DL-based predictive precoder design framework which exploits an unsupervised learning mechanism to improve the practicability of the proposed scheme. As a realization of the proposed framework, we design a DDCs-aware convolutional long short-term memory (CLSTM) network for the precoder design, where both the convolutional neural network and LSTM modules are adopted to facilitate the spatial-temporal feature extraction from the estimated historical DDCs to further enhance the precoder performance. Simulation results demonstrate that the proposed scheme facilitates a flexible reliability-latency tradeoff and achieves an excellent FER performance that approaches the lower bound obtained by a genie-aided benchmark requiring perfect ICSI at both the transmitter and receiver.
In optimization-based approaches to inverse problems and to statistical estimation, it is common to augment the objective with a regularizer to address challenges associated with ill-posedness. The choice of a suitable regularizer is typically driven by prior domain information and computational considerations. Convex regularizers are attractive as they are endowed with certificates of optimality as well as the toolkit of convex analysis, but exhibit a computational scaling that makes them ill-suited beyond moderate-sized problem instances. On the other hand, nonconvex regularizers can often be deployed at scale, but do not enjoy the certification properties associated with convex regularizers. In this paper, we seek a systematic understanding of the power and the limitations of convex regularization by investigating the following questions: Given a distribution, what are the optimal regularizers, both convex and nonconvex, for data drawn from the distribution? What properties of a data source govern whether it is amenable to convex regularization? We address these questions for the class of continuous and positively homogenous regularizers for which convex and nonconvex regularizers correspond, respectively, to convex bodies and star bodies. By leveraging dual Brunn-Minkowski theory, we show that a radial function derived from a data distribution is the key quantity for identifying optimal regularizers and for assessing the amenability of a data source to convex regularization. Using tools such as $\Gamma$-convergence, we show that our results are robust in the sense that the optimal regularizers for a sample drawn from a distribution converge to their population counterparts as the sample size grows large. Finally, we give generalization guarantees that recover previous results for polyhedral regularizers (i.e., dictionary learning) and lead to new ones for semidefinite regularizers.
Many problems involve the use of models which learn probability distributions or incorporate randomness in some way. In such problems, because computing the true expected gradient may be intractable, a gradient estimator is used to update the model parameters. When the model parameters directly affect a probability distribution, the gradient estimator will involve score function terms. This paper studies baselines, a variance reduction technique for score functions. Motivated primarily by reinforcement learning, we derive for the first time an expression for the optimal state-dependent baseline, the baseline which results in a gradient estimator with minimum variance. Although we show that there exist examples where the optimal baseline may be arbitrarily better than a value function baseline, we find that the value function baseline usually performs similarly to an optimal baseline in terms of variance reduction. Moreover, the value function can also be used for bootstrapping estimators of the return, leading to additional variance reduction. Our results give new insight and justification for why value function baselines and the generalized advantage estimator (GAE) work well in practice.
Let $\mathbb{N}$ be the set of positive integers. A radio labeling of a graph $G$ is a mapping $\varphi : V(G) \rightarrow \mathbb{N} \cup \{0\}$ such that the inequality $|\varphi(u)-\varphi(v)| \geq diam(G) + 1 - d(u,v)$ holds for every pair of distinct vertices $u,v$ of $G$, where $diam(G)$ and $d(u,v)$ are the diameter of $G$ and distance between $u$ and $v$ in $G$, respectively. The radio number $rn(G)$ of $G$ is the smallest number $k$ such that $G$ has radio labeling $\varphi$ with $\max\{\varphi(v) : v \in V(G)\}$ = $k$. Das et al. [Discrete Math. $\mathbf{340}$(2017) 855-861] gave a technique to find a lower bound for the radio number of graphs. In [Algorithms and Discrete Applied Mathematics: CALDAM 2019, Lecture Notes in Computer Science $\mathbf{11394}$, springer, Cham, 2019, 161-173], Bantva modified this technique for finding an improved lower bound on the radio number of graphs and gave a necessary and sufficient condition to achieve the improved lower bound. In this paper, one more useful necessary and sufficient condition to achieve the improved lower bound for the radio number of graphs is given. Using this result, the radio number of the Cartesian product of a path and a wheel graphs is determined.
Existence results on Lagrange multiplier approach for gradient flows and application to optimization
This paper deals with the geometric numerical integration of gradient flow and its application to optimization. Gradient flows often appear as model equations of various physical phenomena, and their dissipation laws are essential. Therefore, dissipative numerical methods, which are numerical methods replicating the dissipation law, have been studied in the literature. Recently, Cheng, Liu, and Shen proposed a novel dissipative method, the Lagrange multiplier approach, for gradient flows, which is computationally cheaper than existing dissipative methods. Although their efficacy is numerically confirmed in existing studies, the existence results of the Lagrange multiplier approach are not known in the literature. In this paper, we establish some existence results. We prove the existence of the solution under a relatively mild assumption. In addition, by restricting ourselves to a special case, we show some existence and uniqueness results with concrete bounds. As gradient flows also appear in optimization, we further apply the latter results to optimization problems.
Images with haze of different varieties often pose a significant challenge to dehazing. Therefore, guidance by estimates of haze parameters related to the variety would be beneficial and their progressive update jointly with haze reduction will allow effective dehazing. To this end, we propose a multi-network dehazing framework containing novel interdependent dehazing and haze parameter updater networks that operate in a progressive manner. The haze parameters, transmission map and atmospheric light, are first estimated using specific convolutional networks allowing color-cast handling. The estimated parameters are then used to guide our dehazing module, where the estimates are progressively updated by novel convolutional networks. The updating takes place jointly with progressive dehazing by a convolutional network that invokes inter-step dependencies. The joint progressive updating and dehazing gradually modify the haze parameter estimates toward achieving effective dehazing. Through different studies, our dehazing framework is shown to be more effective than image-to-image mapping or predefined haze formation model based dehazing. Our dehazing framework is qualitatively and quantitatively found to outperform the state-of-the-art on synthetic and real-world hazy images of several datasets with varied haze conditions.
As soon as abstract mathematical computations were adapted to computation on digital computers, the problem of efficient representation, manipulation, and communication of the numerical values in those computations arose. Strongly related to the problem of numerical representation is the problem of quantization: in what manner should a set of continuous real-valued numbers be distributed over a fixed discrete set of numbers to minimize the number of bits required and also to maximize the accuracy of the attendant computations? This perennial problem of quantization is particularly relevant whenever memory and/or computational resources are severely restricted, and it has come to the forefront in recent years due to the remarkable performance of Neural Network models in computer vision, natural language processing, and related areas. Moving from floating-point representations to low-precision fixed integer values represented in four bits or less holds the potential to reduce the memory footprint and latency by a factor of 16x; and, in fact, reductions of 4x to 8x are often realized in practice in these applications. Thus, it is not surprising that quantization has emerged recently as an important and very active sub-area of research in the efficient implementation of computations associated with Neural Networks. In this article, we survey approaches to the problem of quantizing the numerical values in deep Neural Network computations, covering the advantages/disadvantages of current methods. With this survey and its organization, we hope to have presented a useful snapshot of the current research in quantization for Neural Networks and to have given an intelligent organization to ease the evaluation of future research in this area.
Multi-agent influence diagrams (MAIDs) are a popular form of graphical model that, for certain classes of games, have been shown to offer key complexity and explainability advantages over traditional extensive form game (EFG) representations. In this paper, we extend previous work on MAIDs by introducing the concept of a MAID subgame, as well as subgame perfect and trembling hand perfect equilibrium refinements. We then prove several equivalence results between MAIDs and EFGs. Finally, we describe an open source implementation for reasoning about MAIDs and computing their equilibria.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191