教学课程资源库 更多>>

关键词： computers   computer science   analysis of algorithms   suboptimal algorithms   online algorithms   competitive analysis   matching and batching  

摘要： In several applications of real-time matching of demand to supply in online marketplaces, the platform allows for some latency to batch the demand and improve the efficiency of the resulting matching. Motivated by these applications, we study the optimal trade-off between batching and inefficiency in the context of designing robust online allocations. As our base model, we consider K-stage variants of the classic vertexweighted bipartite b-matching in the adversarial setting, where online vertices arrive stagewise and in K batches-in contrast to online arrival. Our main result for this problem is an optimal (1 - (1- 1/K)K)-competitive (fractional) matching algorithm, improving the classic (1 -1/e)-competitive ratio bound known for its online variant [Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Ad words and generalized online matching. J. ACM 54(5):22-es;Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex weighted bipartite matching and single-bid budgeted allocations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1253-1264]. We also extend this result to the general problem of multistage configuration allocation with free disposals [Devanur NR, Huang Z, Korula N, Mirrokni VS, Yan Q (2016) Whole page optimization and submodular welfare maximization with online bidders. ACM Trans. Econom. Comput. 4(3):1-20], which is motivated by the display advertising application in the context of video streaming platforms. Our main technique at a high level is developing algorithmic tools to vary the trade-off between "greediness" and "hedging" of the matching algorithm across stages. We rely on a particular family of convex programming-based matchings that distribute the demand in a specifically balanced way among supply in different stages while carefully modifying the balancedness of the resulting matching across stages. More precisely, we identify a sequence of polynomials with decreasing degr

关键词： Tensors   Matrix decomposition   Computer science   Kernel   Clustering methods   Spectral analysis   Sequential analysis   Clustering   fusing affinity   high-order affinity   spectral graph   tensor  

摘要： Traditional clustering methods rely on pairwise affinity to divide samples into different subgroups. However, high-dimensional small-sample (HDLSS) data are affected by the concentration effects, rendering traditional pairwise metrics unable to accurately describe relationships between samples, leading to suboptimal clustering results. This article advances the proposition of employing high-order affinities to characterize multiple sample relationships as a strategic means to circumnavigate the concentration effects. We establish a nexus between different order affinities by constructing specialized decomposable high-order affinities, thereby formulating a uniform mathematical framework. Building upon this insight, a novel clustering method named uniform tensor clustering (UTC) is proposed, which learns a consensus low-dimensional embedding for clustering by the synergistic exploitation of multiple-order affinities. Extensive experiments on synthetic and real-world datasets demonstrate two findings: 1) high-order affinities are better suited for characterizing sample relationships in complex data and 2) reasonable use of different order affinities can enhance clustering effectiveness, especially in handling high-dimensional data.

关键词： Peer-to-peer computing   Cloud computing   Engines   Vehicle dynamics   Time factors   Computer science   Automobiles   Topology   Distributed databases   Actuators   Edge stream processing   distributed hash table   edge networks   bandit algorithm  

摘要： Edge applications generate a large influx of sensor data on massive scales, and these massive data streams must be processed shortly to derive actionable intelligence. However, traditional data processing systems are not well-suited for these edge applications as they often do not scale well with a large number of concurrent stream queries, do not support low-latency processing under limited edge computing resources, and do not adapt to the level of heterogeneity and dynamicity commonly present in edge computing environments. As such, we present AgileDart, an agile and scalable edge stream processing engine that enables fast stream processing of many concurrently running low-latency edge applications' queries at scale in dynamic, heterogeneous edge environments. The novelty of our work lies in a dynamic dataflow abstraction that leverages distributed hash table-based peer-to-peer overlay networks to autonomously place, chain, and scale stream operators to reduce query latencies, adapt to workload variations, and recover from failures and a bandit-based path planning model that re-plans the data shuffling paths to adapt to unreliable and heterogeneous edge networks. We show that AgileDart outperforms Storm and EdgeWise on query latency and significantly improves scalability and adaptability when processing many real-world edge stream applications' queries.

关键词： Optimization   Generators   Benchmark testing   Vectors   Scalability   Urban areas   Knowledge transfer   Design methodology   Cybernetics   Computer science   Benchmark problems   optimization experience   sequential transfer optimization (STO)  

摘要： Despite the increasing interest in sequential transfer optimization (STO), a comprehensive benchmark suite for systematically comparing various STO algorithms remains underexplored. Existing test problems, which are often manually configured and lack scalability, can result in biased and nongeneralizable algorithm performance. In light of the above, we first introduce four concepts for characterizing STO problems (STOPs) in this study and present an important feature, namely similarity distribution, to quantitatively delineate the relationship between the optimal solutions of source and target tasks. Subsequently, we present general design guidelines for STOPs and introduce a problem generator that demonstrates strong scalability. Specifically, the similarity distribution of a problem can be easily customized through a novel inverse generation strategy, allowing for a continuous spectrum that captures the diverse similarity relationships present in real-world scenarios. Lastly, a benchmark suite comprising 12 STOPs, characterized by a range of customized similarity relationships, has been developed using the proposed generator and will serve as a platform for examining various STO algorithms. For instance, biased transferability representation, irregular mapping learning behaviors, and performance improvements unrelated to search experience are significant empirical findings that previous benchmarks failed to reveal, yet can be effectively identified through our test problems. The source code of the proposed problem generator is available at https://***/XmingHsueh/STOP-G.

关键词： Resource management   Inductive charging   Optimization   Wireless communication   Energy consumption   Hybrid power systems   Device-to-device communication   Computer science   Wireless sensor networks   Performance evaluation   Multi-access edge computing   wireless charging   computation offloading   deep reinforcement learning   proximal policy optimization  

摘要： Wireless-powered multi-access edge computing (WP-MEC), as a promising computing paradigm with the great potential for breaking through the power limitations of wireless devices, is facing the challenges of reliable task offloading and charging power allocation. Towards this end, we formulate a joint optimization problem of wireless charging and computation offloading in socially-aware D2D-assisted WP-MEC to maximize the utility, characterized by wireless devices' residual energy and the strength of social relationship. To address this problem, we propose a deep reinforcement learning (DRL)-based approach with hybrid actor-critic networks including three actor networks and one critic network as well as with Proximal Policy Optimization (PPO) updating policy. Further, to prevent the policy collapse, we adopt the PPO-clip algorithm which limits the update steps to enhance the stability of algorithm. The experimental results show that the proposed algorithm can achieved superior convergence performance and, meanwhile, improves the average utility efficiently compared to other baseline approaches.

关键词： Blockchains   Public key   Smart contracts   Regulators   Computer science   Stress   Encryption   Blockchain rewriting   chameleon hash   message control  

摘要： Blockchain rewriting is necessary for modifying illegal or messages included in blockchain transactions, while maintaining the consistency of subsequent blocks in the blockchain. However, arbitrary blockchain rewriting is not desirable as it defeats the purpose of blockchain rewriting. In this work, we propose a new security primitive named message-controlled chameleon hash (MCH) and apply it for message control in blockchain rewriting to ensure that no unspecified messages are generated from blockchain rewriting. The proposed MCH enables permitted parties to select candidate messages from designated message sets for blockchain rewriting at the message level. Our evaluation shows that the proposed MCH can be easily integrated into both permissioned and permissionless blockchains.

关键词： Object detection   Light fields   Feature extraction   Training   Annotations   Noise measurement   Deep learning   Solid modeling   Computer science   Computational modeling   Light field   salient object detection   unsupervised model  

摘要： Most current Light Field Salient Object Detection (LFSOD) methods require full supervision with labor-intensive pixel-level annotations. Unsupervised Light Field Salient Object Detection (ULFSOD) has gained attention due to this limitation. However, existing methods use traditional handcrafted techniques to generate noisy pseudo-labels, which degrades the performance of models trained on them. To mitigate this issue, we present a novel learning-based approach to synthesize labels for ULFSOD. We introduce a prominent focal stack identification module that utilizes light field information (focal stack, depth map, and RGB color image) to generate high-quality pixel-level pseudo-labels, aiding network training. Additionally, we propose a novel model architecture for LFSOD, combining a multi-scale spatial attention module for focal stack information with a cross fusion module for RGB and focal stack integration. Through extensive experiments, we demonstrate that our pseudo-label generation method significantly outperforms existing methods in label quality. Our proposed model, trained with our labels, shows significant improvement on ULFSOD, achieving new state-of-the-art scores across public benchmarks.

关键词： Contracts   Throughput   Autonomous aerial vehicles   Relays   Receivers   Artificial neural networks   Reliability   Performance evaluation   Optimization   Computer science   Covert communication   contract theory   unmanned aerial vehicle (UAV)   information asymmetric  

摘要： Covert communication is considered a promising technology for hiding transmission processes and activities from malicious eavesdropping. With the development of detection technology, the traditional point-to-point covert communication method cannot effectively guarantee the reliability of covert communication. In order to solve this problem, unmanned aerial vehicle (UAV) are widely adopted in covert communication as common relay equipment. However, the UAV maximizes its benefits by taking advantage of the information asymmetry between itself and the covert communication sender. Therefore, it is necessary to encourage UAV-assisted potential users (UPU) to transmit covert data honestly by designing an information asymmetry-based incentive mechanism. In this paper, we propose a UAV-assisted contract-theoretic (UACT) model to improve the covert communication performance, where UPU honestly transmits covert data and the throughput of UACT can be increased. Specifically, we first divide UPU into finite types and model the data transfer contract between the sender, UPU, and receiver. Then, the contract feasibility of UACT is derived with sufficient and necessary conditions. Finally, we analyze the contract optimization in the continuous case of UPUs. Numerical simulations show that the UACT can incentivize UPUs to transmit covert data through UAV assistance and make covert communication performance close to the information symmetry case.

关键词： Measurement   Bipartite graph   Reliability   Feature extraction   Cryptocurrency   Receivers   Fraud   Ecosystems   Costs   Computer science   Ethereum   risk control   network propagation   financial transaction networks  

摘要： As one of the most popular blockchain platforms supporting smart contracts, Ethereum has caught the interest of both investors and criminals. Differently from traditional financial scenarios, executing Know Your Customer verification on Ethereum is rather difficult due to its pseudonymous nature. Fortunately, as the transaction records stored in the Ethereum blockchain are publicly accessible, we can understand the behavior of accounts or detect illicit activities via transaction mining. Existing risk control techniques have primarily been developed from the perspectives of de-anonymizing address clustering and illicit account classification. However, these techniques cannot ascertain the potential risks for all accounts and are limited by specific heuristic strategies or insufficient label information. These constraints motivate us to seek an effective rating method for quantifying the spread of risk in a transaction network. To the best of our knowledge, we are the first to address the problem of account risk rating on Ethereum by proposing a novel model called RiskProp, which includes a de-anonymous score to measure transaction anonymity and a network propagation mechanism to formulate the relationships between accounts and transactions. Experimental results on a realistic Ethereum dataset demonstrate that proposed RiskProp newly discovered 63% of the Top 150 high-risk accounts as suspicious. The superior performance of risk score-based account classification experiments further verifies the effectiveness of our rating method (85.63% accuracy).

关键词： Adaptation models   Calibration   Training   Federated learning   Data models   Computational modeling   Accuracy   Convergence   Data privacy   Computer science   Mobile computing   federated learning   statistical heterogeneity   adaptive calibration strategy  

摘要： Federated learning (FL) is a promising artificial intelligence framework that enables clients to collectively train models with data privacy. However, in real-world scenarios, to construct practical FL frameworks, several challenges have to be addressed, including statistical heterogeneity, constrained resources, and fairness. Therefore, we first investigate an aggregation gap caused by statistical heterogeneity during local model initialization, which not only causes additional computational overhead for clients but also leads to the degradation of fairness. To bridge this gap, we propose pFedCal, a novel personalized federated learning with lightweight adaptive calibration strategy that performs calibration compensation through the prior knowledge of clients. Specifically, we introduce compensation for each client at the model initialization, with the compensation derived from the global gradient and the latest gradient bias. To enhance the calibration effect, we introduce a smoothing-based calibration strategy, and we design an adaptive calibration strategy. A representative example demonstrates that the proposed calibration and smoothing strategies improve fairness for clients. The theoretical analysis indicates that with an appropriate learning rate, pFedCal converges to a first-order stationary point for non-convex loss functions. Comprehensive experimental results show that pFedCal achieves faster convergence, higher accuracy, and improved fairness than the state-of-the-art methods.