OpenRaiser/Intern-Atlas huggingface dataset:
Multi-objective Resource Allocation for D2D and Enabled MC-NOMA Networks by Tchebycheff Method
Venue: arXiv cs.IT 2021
Year: 2021

This paper considers a resource allocation problem in device-to-device (D2D) communications sharing the same frequency spectrum. In particular, the CUs utilize non-orthogonal multiple access (NOMA) while DUs adopt the orthogonal frequency division multiple access (OFDMA). A multi-objective optimization problem (MOOP) is formulated, which jointly maximizes the sum rate of D2D and CUs (CUs) in uplink communications while taking into account the maximum transmit power budget and minimum data rate requirement for D2D and CUs. This MOOP is handled by the weighted Tchebycheff method, which converts it into a single-objective optimization (SOOP). Then, the monotonic optimization approach is employed to solve this SOOP optimally. Numerical results unveil an interesting tradeoff between D2D and CUs.
MoboTSP: Solving the Task Sequencing Problem for Mobile Manipulators
Venue: arXiv cs.RO 2021
Year: 2021

We introduce a new approach to tackle the mobile manipulator task sequencing problem. We leverage computational geometry, graph theory and combinatorial optimization to yield a principled method to segment the task-space targets into clusters, analytically determine reachable base pose for each cluster, and find task sequences that minimize the number of base movements and robot execution time. By clustering targets first and by doing so from first principles, our solution is more general and computationally efficient when compared to existing methods.
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
Venue: arXiv cs.DS 2021
Year: 2021

We present a simple deterministic distributed algorithm that computes a $(Δ+1)$-vertex coloring in $O(\log^2 Δ\cdot \log n)$ rounds. The algorithm can be implemented with $O(\log n)$-bit messages. The algorithm can also be extended to the more general $(degree+1)$-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for $(Δ+1)$-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozhoň and Ghaffari [STOC'20]. The current state of the art is based on an improved variant of their decomposition, which leads to an $O(\log^5 n)$-round algorithm for $(Δ+1)$-vertex coloring. Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignments. Moreover, via the approach of Chang, Li, and Pettie [STOC'18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for $(Δ+1)$-coloring, now reaching the bound of $O(\log^3\log n)$ rounds. As a further application, we also provide faster deterministic distributed algorithms for the following variants of the vertex coloring problem. In graphs of arboricity $a$, we show that a $(2+ε)a$-vertex coloring can be computed in $O(\log^3 a\cdot\log n)$ rounds. We also show that for $Δ\geq 3$, a $Δ$-coloring of a $Δ$-colorable graph $G$ can be computed in $O(\log^2 Δ\cdot\log^2 n)$ rounds.
Balanced Crown Decomposition for Connectivity Constraints
Venue: arXiv cs.DS 2021
Year: 2021

We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular modeling tool in various application areas, where the non-local nature of the connectivity condition usually results in very challenging algorithmic tasks. The balanced crown decomposition is a combination of a crown decomposition and a balanced partition which makes it applicable to graph editing as well as graph packing and partitioning problems. We illustrate this by deriving improved kernelization and approximation algorithms for a variety of such problems. In particular, through this structure, we obtain the first constant-factor approximation for the Balanced Connected Partition (BCP) problem, where the task is to partition a vertex-weighted graph into $k$ connected components of approximately equal weight. We derive a 3-approximation for the two most commonly used objectives of maximizing the weight of the lightest component or minimizing the weight of the heaviest component.
Similarity-Based Clustering for Enhancing Image Classification Architectures
Venue: arXiv cs.CV 2021
Year: 2021

Convolutional networks are at the center of best-in-class computer vision applications for a wide assortment of undertakings. Since 2014, a profound amount of work began to make better convolutional architectures, yielding generous additions in different benchmarks. Albeit expanded model size and computational cost will, in general, mean prompt quality increases for most undertakings but, the architectures now need to have some additional information to increase the performance. I show evidence that with the amalgamation of content-based image similarity and deep learning models, we can provide the flow of information which can be used in making clustered learning possible. The paper shows how training of sub-dataset clusters not only reduces the cost of computation but also increases the speed of evaluating and tuning a model on the given dataset.
Efficient Algorithms for Stochastic Repeated Second-price Auctions
Venue: arXiv cs.LG 2021
Year: 2021

Developing efficient sequential bidding strategies for repeated auctions is an important practical challenge in various marketing tasks. In this setting, the bidding agent obtains information, on both the value of the item at sale and the behavior of the other bidders, only when she wins the auction. Standard bandit theory does not apply to this problem due to the presence of action-dependent censoring. In this work, we consider second-price auctions and propose novel, efficient UCB-like algorithms for this task. These algorithms are analyzed in the stochastic setting, assuming regularity of the distribution of the opponents' bids. We provide regret upper bounds that quantify the improvement over the baseline algorithm proposed in the literature. The improvement is particularly significant in cases when the value of the auctioned item is low, yielding a spectacular reduction in the order of the worst-case regret. We further provide the first parametric lower bound for this problem that applies to generic UCB-like strategies. As an alternative, we propose more explainable strategies which are reminiscent of the Explore Then Commit bandit algorithm. We provide a critical analysis of this class of strategies, showing both important advantages and limitations. In particular, we provide a minimax lower bound and propose a nearly minimax-optimal instance of this class.
Qualities, challenges and future of genetic algorithms: a literature review
Venue: arXiv cs.NE 2021
Year: 2021

Genetic algorithms, computer programs that simulate natural evolution, are increasingly applied across many disciplines. They have been used to solve various optimisation problems from neural network architecture search to strategic games, and to model phenomena of adaptation and learning. Expertise on the qualities and drawbacks of this technique is largely scattered across the literature or former, motivating an compilation of this knowledge at the light of the most recent developments of the field. In this review, we present genetic algorithms, their qualities, limitations and challenges, as well as some future development perspectives. Genetic algorithms are capable of exploring large and complex spaces of possible solutions, to quickly locate promising elements, and provide an adequate modelling tool to describe evolutionary systems, from games to economies. They however suffer from high computation costs, difficult parameter configuration, and crucial representation of the solutions. Recent developments such as GPU, parallel and quantum computing, conception of powerful parameter control methods, and novel approaches in representation strategies, may be keys to overcome those limitations. This compiling review aims at informing practitioners and newcomers in the field alike in their genetic algorithm research, and at outlining promising avenues for future research. It highlights the potential for interdisciplinary research associating genetic algorithms to pulse original discoveries in social sciences, open ended evolution, artificial life and AI.
Sound Synthesis, Propagation, and Rendering: A Survey
Venue: arXiv cs.SD 2021
Year: 2021

Sound, as a crucial sensory channel, plays a vital role in improving the reality and immersiveness of a virtual environment, following only vision in importance. Sound can provide important clues such as sound directionality and spatial size. This paper gives a broad overview of research works on sound simulation in virtual reality, games, multimedia, computer-aided design. We first survey various sound synthesis methods, including harmonic synthesis, texture synthesis, spectral analysis, and physics-based synthesis. Then, we summarize popular sound propagation techniques, namely wave-based methods, geometric-based methods, and hybrid methods. Next, the sound rendering methods are reviewed. We further demonstrate the latest deep learning based sound simulation approaches. Finally, we point to some future directions of this field. To the best of our knowledge, this is the first attempt to provide a comprehensive summary of sound research in the field of computer graphics.
Identifying Properties of Real-World Optimisation Problems through a Questionnaire
Venue: arXiv cs.NE 2021
Year: 2021

Optimisation algorithms are commonly compared on benchmarks to get insight into performance differences. However, it is not clear how closely benchmarks match the properties of real-world problems because these properties are largely unknown. This work investigates the properties of real-world problems through a questionnaire to enable the design of future benchmark problems that more closely resemble those found in the real world. The results, while not representative as they are based on only 45 responses, indicate that many problems possess at least one of the following properties: they are constrained, deterministic, have only continuous variables, require substantial computation times for both the objectives and the constraints, or allow a limited number of evaluations. Properties like known optimal solutions and analytical gradients are rarely available, limiting the options in guiding the optimisation process. These are all important aspects to consider when designing realistic benchmark problems. At the same time, the design of realistic benchmarks is difficult, because objective functions are often reported to be black-box and many problem properties are unknown. To further improve the understanding of real-world problems, readers working on a real-world optimisation problem are encouraged to fill out the questionnaire: https://tinyurl.com/opt-survey
Comprehensive and Efficient Workload Compression
Venue: arXiv cs.DB 2021
Year: 2021

This work studies the problem of constructing a representative workload from a given input analytical query workload where the former serves as an approximation with guarantees of the latter. We discuss our work in the context of workload analysis and monitoring. As an example, evolving system usage patterns in a database system can cause load imbalance and performance regressions which can be controlled by monitoring system usage patterns, i.e.,~a representative workload, over time. To construct such a workload in a principled manner, we formalize the notions of workload {\em representativity} and {\em coverage}. These metrics capture the intuition that the distribution of features in a compressed workload should match a target distribution, increasing representativity, and include common queries as well as outliers, increasing coverage. We show that solving this problem optimally is NP-hard and present a novel greedy algorithm that provides approximation guarantees. We compare our techniques to established algorithms in this problem space such as sampling and clustering, and demonstrate advantages and key trade-offs of our techniques.
TERMCast: Temporal Relation Modeling for Effective Urban Flow Forecasting
Venue: arXiv cs.AI 2021
Year: 2021

Urban flow forecasting is a challenging task, given the inherent periodic characteristics of urban flow patterns. To capture the periodicity, existing urban flow prediction approaches are often designed with closeness, period, and trend components extracted from the urban flow sequence. However, these three components are often considered separately in the prediction model. These components have not been fully explored together and simultaneously incorporated in urban flow forecasting models. We introduce a novel urban flow forecasting architecture, TERMCast. A Transformer based long-term relation prediction module is explicitly designed to discover the periodicity and enable the three components to be jointly modeled This module predicts the periodic relation which is then used to yield the predicted urban flow tensor. To measure the consistency of the predicted periodic relation vector and the relation vector inferred from the predicted urban flow tensor, we propose a consistency module. A consistency loss is introduced in the training process to further improve the prediction performance. Through extensive experiments on three real-world datasets, we demonstrate that TERMCast outperforms multiple state-of-the-art methods. The effectiveness of each module in TERMCast has also been investigated.
Interference Impact on Decode-and-Forward Relay Networks with RIS-Assisted Source and Relays
Venue: arXiv cs.IT 2021
Year: 2021

In this letter, we consider the scenario of decode-and-forward relay network with reconfigurable intelligent surface (RIS)-assisted source and relays in the presence of interference. We derive approximate closed-form expression for the system outage probability assuming Rayleigh fading channels and opportunistic relaying scheme. In addition, we study the system behavior at the high signal-to-noise ratio (SNR) regime, where the diversity order and coding gain are obtained and analyzed. The results show that the system can achieve a diversity order of Gd = min(N1,N2)K, where N1 and N2 are the numbers of reflecting elements at the source and relays, respectively, and K is the number of relays. In addition, findings illustrate that for the same diversity order, utilizing one relay with multiple reflecting elements gives better performance than utilizing multiple relays with a single reflecting element. Furthermore, findings illustrate that the interference at the destination is more severe on the system performance than the interference at the relays. Therefore, under the same interference powers and for a fixed number of relays K, results show that the case where the first hop is dominating the performance N1 < N2 gives better results in terms of coding gain than the case where N2 < N1.
Skeleton-based Relational Reasoning for Group Activity Analysis
Venue: arXiv cs.CV 2021
Year: 2021

Research on group activity recognition mostly leans on the standard two-stream approach (RGB and Optical Flow) as their input features. Few have explored explicit pose information, with none using it directly to reason about the persons interactions. In this paper, we leverage the skeleton information to learn the interactions between the individuals straight from it. With our proposed method GIRN, multiple relationship types are inferred from independent modules, that describe the relations between the body joints pair-by-pair. Additionally to the joints relations, we also experiment with the previously unexplored relationship between individuals and relevant objects (e.g. volleyball). The individuals distinct relations are then merged through an attention mechanism, that gives more importance to those individuals more relevant for distinguishing the group activity. We evaluate our method in the Volleyball dataset, obtaining competitive results to the state-of-the-art. Our experiments demonstrate the potential of skeleton-based approaches for modeling multi-person interactions.
Transmission of a Bit over a Discrete Poisson Channel with Memory
Venue: arXiv cs.IT 2021
Year: 2021

A coding scheme for transmission of a bit maps a given bit to a sequence of channel inputs (called the codeword associated to the transmitted bit). In this paper, we study the problem of designing the best code for a discrete Poisson channel with memory (under peak-power and total-power constraints). The outputs of a discrete Poisson channel with memory are Poisson distributed random variables with a mean comprising of a fixed additive noise and a linear combination of past input symbols. Assuming a maximum-likelihood (ML) decoder, we search for a codebook that has the smallest possible error probability. This problem is challenging because error probability of a code does not have a closed-form analytical expression. For the case of having only a total-power constraint, the optimal code structure is obtained, provided that the blocklength is greater than the memory length of the channel. For the case of having only a peak-power constraint, the optimal code is derived for arbitrary memory and blocklength in the high-power regime. For the case of having both the peak-power and total-power constraints, the optimal code is derived for memoryless Poisson channels when both the total-power and the peak-power bounds are large.
Saturating stable matchings
Venue: arXiv cs.GT 2021
Year: 2021

I relate bipartite graph matchings to stable matchings. I prove a necessary and sufficient condition for the existence of a saturating stable matching, where every agent on one side is matched, for all possible preferences. I extend my analysis to perfect stable matchings, where every agent on both sides is matched.
DSAM: A Distance Shrinking with Angular Marginalizing Loss for High Performance Vehicle Re-identificatio
Venue: arXiv cs.CV 2021
Year: 2021

Vehicle Re-identification (ReID) is an important yet challenging problem in computer vision. Compared to other visual objects like faces and persons, vehicles simultaneously exhibit much larger intraclass viewpoint variations and interclass visual similarities, making most exiting loss functions designed for face recognition and person ReID unsuitable for vehicle ReID. To obtain a high-performance vehicle ReID model, we present a novel Distance Shrinking with Angular Marginalizing (DSAM) loss function to perform hybrid learning in both the Original Feature Space (OFS) and the Feature Angular Space (FAS) using the local verification and the global identification information. Specifically, it shrinks the distance between samples of the same class locally in the Original Feature Space while keeps samples of different classes far away in the Feature Angular Space. The shrinking and marginalizing operations are performed during each iteration of the training process and are suitable for different SoftMax based loss functions. We evaluate the DSAM loss function on three large vehicle ReID datasets with detailed analyses and extensive comparisons with many competing vehicle ReID methods. Experimental results show that our DSAM loss enhances the SoftMax loss by a large margin on the PKU-VD1-Large dataset: 10.41% for mAP, 5.29% for cmc1, and 4.60% for cmc5. Moreover, the mAP is increased by 9.34% on the PKU-VehicleID dataset and 6.13% on the VeRi-776 dataset. Source code will be released to facilitate further studies in this research direction.
Towards Better Approximation of Graph Crossing Number
Venue: arXiv cs.DS 2021
Year: 2021

Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. Despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a $\tilde O(\sqrt n)$-approximation, while the best current negative result is APX-hardness. All current approximation algorithms for the problem build on the same paradigm: compute a set $E'$ of edges (called a \emph{planarizing set}) such that $G\setminus E'$ is planar; compute a planar drawing of $G\setminus E'$; then add the drawings of the edges of $E'$ to the resulting drawing. Unfortunately, there are examples of graphs, in which any implementation of this method must incur $Ω(\text{OPT}^2)$ crossings, where $\text{OPT}$ is the value of the optimal solution. This barrier seems to doom the only known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than $O(\sqrt n)$-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm that, given a bounded-degree graph $G$ and a planarizing set $E'$ of its edges, computes another set $E''$ with $E'\subseteq E''$, such that $|E''|$ is relatively small, and there exists a near-optimal drawing of $G$ in which only edges of $E''$ participate in crossings. This allows us to reduce the Crossing Number problem to \emph{Crossing Number with Rotation System} -- a variant in which the ordering of the edges incident to every vertex is fixed as part of input. We show a randomized algorithm for this new problem, that allows us to obtain an $O(n^{1/2-ε})$-approximation for Crossing Number on bounded-degree graphs, for some constant $ε>0$.
Coordinated Motion Control and Event-based Obstacle-crossing for Four Wheel-leg Independent Motor-driven Robotic System via MPC
Venue: arXiv cs.RO 2021
Year: 2021

This work presents the coordinated motion control and obstacle-crossing problem for the four wheel-leg independent motor-driven robotic systems via a model predictive control (MPC) approach based on an event-triggering mechanism. The modeling of a wheel-leg robotic control system with a dynamic supporting polygon is organized. The system dynamic model is 3 degrees of freedom (DOF) ignoring the pitch, roll and vertical motions. The single wheel dynamic is analyzed considering the characteristics of motor-driven and the Burckhardt nonlinear tire model. As a result, an over-actuated predictive model is proposed with the motor torques as inputs and the system states as outputs. As the supporting polygon is only adjusted at certain conditions, an event-based triggering mechanism is designed to save hardware resources and energy. The MPC controller is evaluated on a virtual prototype as well as a physical prototype. The simulation results guide the parameter tuning for the controller implementation in the physical prototype. The experimental results on these two prototypes verify the efficiency of the proposed approach.
Memory-two zero-determinant strategies in repeated games
Venue: arXiv cs.GT 2021
Year: 2021

Repeated games have provided an explanation how mutual cooperation can be achieved even if defection is more favorable in a one-shot game in prisoner's dilemma situation. Recently found zero-determinant strategies have substantially been investigated in evolutionary game theory. The original memory-one zero-determinant strategies unilaterally enforce linear relations between average payoffs of players. Here, we extend the concept of zero-determinant strategies to memory-two strategies in repeated games. Memory-two zero-determinant strategies unilaterally enforce linear relations between correlation functions of payoffs and payoffs at the previous round. Examples of memory-two zero-determinant strategy in the repeated prisoner's dilemma game are provided, some of which generalize the Tit-for-Tat strategy to memory-two case. Extension of zero-determinant strategies to memory-$n$ case with $n\geq 2$ is also straightforward.