OpenRaiser/Intern-Atlas huggingface dataset:
A Tight $(1.5+ε)$-Approximation for Unsplittable Capacitated Vehicle Routing on Trees
Venue: arXiv cs.DS 2022
Year: 2022

In the unsplittable capacitated vehicle routing problem (UCVRP) on trees, we are given a rooted tree with edge weights and a subset of vertices of the tree called terminals. Each terminal is associated with a positive demand between 0 and 1. The goal is to find a minimum length collection of tours starting and ending at the root of the tree such that the demand of each terminal is covered by a single tour (i.e., the demand cannot be split), and the total demand of the terminals in each tour does not exceed the capacity of 1. For the special case when all terminals have equal demands, a long line of research culminated in a quasi-polynomial time approximation scheme [Jayaprakash and Salavatipour, SODA 2022] and a polynomial time approximation scheme [Mathieu and Zhou, ICALP 2022]. In this work, we study the general case when the terminals have arbitrary demands. Our main contribution is a polynomial time $(1.5+ε)$-approximation algorithm for the UCVRP on trees. This is the first improvement upon the 2-approximation algorithm more than 30 years ago [Labbé, Laporte, and Mercure, Operations Research, 1991]. Our approximation ratio is essentially best possible, since it is NP-hard to approximate the UCVRP on trees to better than a 1.5 factor.
Self-adjusting optimization algorithm for solving the setunion knapsack problem
Venue: arXiv cs.NE 2022
Year: 2022

The set-union knapsack problem (SUKP) is a constrained composed optimization problem. It is more difficulty for solving because values and weights depend on items and elements respectively. In this paper, we present two self-adjusting optimization algorithms for approximating SUKP from items and elements perspective respectively. By analyzing the dynamic characters in the SUKP, we design two types of self-adjusting repair and optimization operators that are based on the different loading process. We use the novel teaching-learning-based optimization algorithm (TLBO) to design a general discrete framework (DTLBO) suitable for these two types of operators. In addition, we introduce elite opposite search and natural selection mechanism into DTLBO to furtherly improve the performance of the algorithm from the perspective of population. Finally, we performed experimental comparisons on benchmark sets to verify the effectiveness of the proposed algorithm. The experimental results show that the item-based self-adjusting optimization algorithm I-DTLBO is outstanding, and the algorithm is superior to the other swarm intelligence methods for solving SUKP. IDTLBO algorithm reaches the upper boundary of the current swarm intelligence algorithms for solving SUKP in 10 instances, and gotten new upper boundary in 15 instances. The algorithm E-DTLBO based on element loading only perform slightly better on small and middle data sets, but worse on large-scale instances. It shows that element-based design is not suitable for solving SUKP.
Reliability function for streaming over a DMC with feedback
Venue: arXiv cs.IT 2022
Year: 2022

Conventionally, posterior matching is investigated in channel coding and block encoding contexts -- the source symbols are equiprobably distributed and are entirely known by the encoder before the transmission. In this paper, we consider a streaming source, whose symbols arrive at the encoder at a sequence of deterministic times. We derive the joint source-channel coding (JSCC) reliability function for streaming over a discrete memoryless channel (DMC) with feedback. We propose a novel instantaneous encoding phase that operates during the symbol arriving period and achieves the JSCC reliability function for streaming when followed by a block encoding scheme that achieves the JSCC reliability function for a classical source whose symbols are fully accessible before the transmission. During the instantaneous encoding phase, the evolving message alphabet is partitioned into groups, and the encoder determines the index of the group that contains the symbols arrived so far and applies randomization to match the distribution of the transmitted index to the capacity-achieving one. Surprisingly, the JSCC reliability function for streaming is equal to that for a fully accessible source, implying that the knowledge of the entire symbol sequence before the transmission offers no advantage regarding the reliability function. For streaming over a symmetric 2-input DMC, we propose an instantaneous small-enough difference (SED) code that not only achieves the JSCC reliability function but also can be used to stabilize an unstable linear system over a noisy channel. We design low complexity algorithms to implement both the instantaneous encoding phase and the instantaneous SED code. While the reliability function is derived for non-degenerate DMCs, for degenerate DMCs we design a code with instantaneous encoding that achieves zero error for all rates below Shannon's JSCC limit.
Visualising Multiplayer Game Spaces
Venue: arXiv cs.AI 2022
Year: 2022

We compare four different `game-spaces' in terms of their usefulness in characterising multi-player tabletop games, with a particular interest in any underlying change to a game's characteristics as the number of players changes. In each case we take a 16-dimensional feature space, and reduce it to a 2-dimensional visualizable landscape. We find that a space obtained from optimization of parameters in Monte Carlo Tree Search (MCTS) is the most directly interpretable to characterise our set of games in terms of the relative importance of imperfect information, adversarial opponents and reward sparsity. These results do not correlate with a space defined using attributes of the game-tree. This dimensionality reduction does not show any general effect as the number of players. We therefore consider the question using the original features to classify the games into two sets; those for which the characteristics of the game changes significantly as the number of players changes, and those for which there is no such effect.
Answer Set Planning: A Survey
Venue: arXiv cs.AI 2022
Year: 2022

Answer Set Planning refers to the use of Answer Set Programming (ASP) to compute plans, i.e., solutions to planning problems, that transform a given state of the world to another state. The development of efficient and scalable answer set solvers has provided a significant boost to the development of ASP-based planning systems. This paper surveys the progress made during the last two and a half decades in the area of answer set planning, from its foundations to its use in challenging planning domains. The survey explores the advantages and disadvantages of answer set planning. It also discusses typical applications of answer set planning and presents a set of challenges for future research.
SHED: A Newton-type algorithm for federated learning based on incremental Hessian eigenvector sharing
Venue: arXiv cs.LG 2022
Year: 2022

There is a growing interest in the distributed optimization framework that goes under the name of Federated Learning (FL). In particular, much attention is being turned to FL scenarios where the network is strongly heterogeneous in terms of communication resources (e.g., bandwidth) and data distribution. In these cases, communication between local machines (agents) and the central server (Master) is a main consideration. In this work, we present SHED, an original communication-constrained Newton-type (NT) algorithm designed to accelerate FL in such heterogeneous scenarios. SHED is by design robust to non i.i.d. data distributions, handles heterogeneity of agents' communication resources (CRs), only requires sporadic Hessian computations, and achieves super-linear convergence. This is possible thanks to an incremental strategy, based on eigendecomposition of the local Hessian matrices, which exploits (possibly) outdated second-order information. The proposed solution is thoroughly validated on real datasets by assessing (i) the number of communication rounds required for convergence, (ii) the overall amount of data transmitted and (iii) the number of local Hessian computations. For all these metrics, the proposed approach shows superior performance against state-of-the art techniques like GIANT and FedNL.
Active Privacy-Utility Trade-off Against Inference in Time-Series Data Sharing
Venue: arXiv cs.IT 2022
Year: 2022

Internet of things (IoT) devices, such as smart meters, smart speakers and activity monitors, have become highly popular thanks to the services they offer. However, in addition to their many benefits, they raise privacy concerns since they share fine-grained time-series user data with untrusted third parties. In this work, we consider a user releasing her data containing personal information in return of a service from an honest-but-curious service provider (SP). We model user's personal information as two correlated random variables (r.v.'s), one of them, called the secret variable, is to be kept private, while the other, called the useful variable, is to be disclosed for utility. We consider active sequential data release, where at each time step the user chooses from among a finite set of release mechanisms, each revealing some information about the user's personal information, i.e., the true values of the r.v.'s, albeit with different statistics. The user manages data release in an online fashion such that the maximum amount of information is revealed about the latent useful variable as quickly as possible, while the confidence for the sensitive variable is kept below a predefined level. For privacy measure, we consider both the probability of correctly detecting the true value of the secret and the mutual information (MI) between the secret and the released data. We formulate both problems as partially observable Markov decision processes (POMDPs), and numerically solve them by advantage actor-critic (A2C) deep reinforcement learning (DRL). We evaluate the privacy-utility trade-off (PUT) of the proposed policies on both the synthetic data and smoking activity dataset, and show their validity by testing the activity detection accuracy of the SP modeled by a long short-term memory (LSTM) neural network.
Blocking Techniques for Sparse Matrix Multiplication on Tensor Accelerators
Venue: arXiv cs.DC 2022
Year: 2022

Tensor accelerators have gained popularity because they provide a cheap and efficient solution for speeding up computational-expensive tasks in Deep Learning and, more recently, in other Scientific Computing applications. However, since their features are specifically designed for tensor algebra (typically dense matrix-product), it is commonly assumed that they are not suitable for applications with sparse data. To challenge this viewpoint, we discuss methods and present solutions for accelerating sparse matrix multiplication on such architectures. In particular, we present a 1-dimensional blocking algorithm with theoretical guarantees on the density, which builds dense blocks from arbitrary sparse matrices. Experimental results show that, even for unstructured and highly-sparse matrices, our block-based solution which exploits Nvidia Tensor Cores is faster than its sparse counterpart. We observed significant speed-ups of up to two orders of magnitude on real-world sparse matrices.
REST: Integrating Term Rewriting with Program Verification (Extended Version)
Venue: arXiv cs.PL 2022
Year: 2022

We introduce REST, a novel term rewriting technique for theorem proving that uses online termination checking and can be integrated with existing program verifiers. REST enables flexible but terminating term rewriting for theorem proving by: (1) exploiting newly-introduced term orderings that are more permissive than standard rewrite simplification orderings; (2) dynamically and iteratively selecting orderings based on the path of rewrites taken so far; and (3) integrating external oracles that allow steps that cannot be justified with rewrite rules. Our REST approach is designed around an easily implementable core algorithm, parameterizable by choices of term orderings and their implementations; in this way our approach can be easily integrated into existing tools. We implemented REST as a Haskell library and incorporated it into Liquid Haskell's evaluation strategy, extending Liquid Haskell with rewriting rules. We evaluated our REST implementation by comparing it against both existing rewriting techniques and E-matching and by showing that it can be used to supplant manual lemma application in many existing Liquid Haskell proofs.
Optimal Spend Rate Estimation and Pacing for Ad Campaigns with Budgets
Venue: arXiv cs.GT 2022
Year: 2022

Online ad platforms offer budget management tools for advertisers that aim to maximize the number of conversions given a budget constraint. As the volume of impressions, conversion rates and prices vary over time, these budget management systems learn a spend plan (to find the optimal distribution of budget over time) and run a pacing algorithm which follows the spend plan. This paper considers two models for impressions and competition that varies with time: a) an episodic model which exhibits stationarity in each episode, but each episode can be arbitrarily different from the next, and b) a model where the distributions of prices and values change slowly over time. We present the first learning theoretic guarantees on both the accuracy of spend plans and the resulting end-to-end budget management system. We present four main results: 1) for the episodic setting we give sample complexity bounds for the spend rate prediction problem: given $n$ samples from each episode, with high probability we have $|\widehatρ_e - ρ_e| \leq \tilde{O}(\frac{1}{n^{1/3}})$ where $ρ_e$ is the optimal spend rate for the episode, $\widehatρ_e$ is the estimate from our algorithm, 2) we extend the algorithm of Balseiro and Gur (2017) to operate on varying, approximate spend rates and show that the resulting combined system of optimal spend rate estimation and online pacing algorithm for episodic settings has regret that vanishes in number of historic samples $n$ and the number of rounds $T$, 3) for non-episodic but slowly-changing distributions we show that the same approach approximates the optimal bidding strategy up to a factor dependent on the rate-of-change of the distributions and 4) we provide experiments showing that our algorithm outperforms both static spend plans and non-pacing across a wide variety of settings.
Can We Talk? An Exploratory Study of Gender and Network Ties in a Local Government Setting
Venue: arXiv cs.SI 2022
Year: 2022

We explore the influence of gender and formal organizational status on the formation of discussion ties. Network data, gathered through surveying employees from a municipal organization in the United States, garnered a 92% response rate (n=143). Results of exponential random graph modeling indicate women supervisors are more likely to send discussion ties, while women in general are more likely to receive discussion ties. These exploratory results suggest women may be perceived as more approachable for work discussions, but not as supervisors. Finally, the results identified a consistent homophily effect of gender in the discussion network.
Towards Build Verifiability for Java-based Systems
Venue: arXiv cs.SE 2022
Year: 2022

Build verifiability refers to the property that the build of a software system can be verified by independent third parties and it is crucial for the trustworthiness of a software system. Various efforts towards build verifiability have been made to C/C++-based systems, yet the techniques for Java-based systems are not systematic and are often specific to a particular build tool (e.g., Maven). In this study, we present a systematic approach towards build verifiability on Java-based systems. Our approach consists of three parts: a unified build process, a tool that dynamically controls non-determinism during the build process, and another tool that eliminates non-equivalences by post-processing the build artifacts. We apply our approach on 46 unverified open source projects from Reproducible Central and 13 open source projects that are widely used by Huawei commercial products. As a result, 91% of the unverified Reproducible Central projects and 100% of the commercially adopted OSS projects are successfully verified with our approach. In addition, based on our experience in analyzing thousands of builds for both commercial and open source Java-based systems, we present 14 patterns that introduce non-equivalences in generated build artifacts and their respective mitigation strategies. Among these patterns, 11 (78%) are unique for Java-based system, whereas the remaining 3 (22%) are common with C/C++-based systems. The approach and the findings of this paper are useful for both practitioners and researchers who are interested in build verifiability.
Compute Trends Across Three Eras of Machine Learning
Venue: arXiv cs.LG 2022
Year: 2022

Compute, data, and algorithmic advances are the three fundamental factors that guide the progress of modern Machine Learning (ML). In this paper we study trends in the most readily quantified factor - compute. We show that before 2010 training compute grew in line with Moore's law, doubling roughly every 20 months. Since the advent of Deep Learning in the early 2010s, the scaling of training compute has accelerated, doubling approximately every 6 months. In late 2015, a new trend emerged as firms developed large-scale ML models with 10 to 100-fold larger requirements in training compute. Based on these observations we split the history of compute in ML into three eras: the Pre Deep Learning Era, the Deep Learning Era and the Large-Scale Era. Overall, our work highlights the fast-growing compute requirements for training advanced ML systems.
Detecting out-of-context objects using contextual cues
Venue: arXiv cs.CV 2022
Year: 2022

This paper presents an approach to detect out-of-context (OOC) objects in an image. Given an image with a set of objects, our goal is to determine if an object is inconsistent with the scene context and detect the OOC object with a bounding box. In this work, we consider commonly explored contextual relations such as co-occurrence relations, the relative size of an object with respect to other objects, and the position of the object in the scene. We posit that contextual cues are useful to determine object labels for in-context objects and inconsistent context cues are detrimental to determining object labels for out-of-context objects. To realize this hypothesis, we propose a graph contextual reasoning network (GCRN) to detect OOC objects. GCRN consists of two separate graphs to predict object labels based on the contextual cues in the image: 1) a representation graph to learn object features based on the neighboring objects and 2) a context graph to explicitly capture contextual cues from the neighboring objects. GCRN explicitly captures the contextual cues to improve the detection of in-context objects and identify objects that violate contextual relations. In order to evaluate our approach, we create a large-scale dataset by adding OOC object instances to the COCO images. We also evaluate on recent OCD benchmark. Our results show that GCRN outperforms competitive baselines in detecting OOC objects and correctly detecting in-context objects.
Increasing FPGA Accelerators Memory Bandwidth with a Burst-Friendly Memory Layout
Venue: arXiv cs.AR 2022
Year: 2022

Offloading compute-intensive kernels to hardware accelerators relies on the large degree of parallelism offered by these platforms. However, the effective bandwidth of the memory interface often causes a bottleneck, hindering the accelerator's effective performance. Techniques enabling data reuse, such as tiling, lower the pressure on memory traffic but still often leave the accelerators I/O-bound. A further increase in effective bandwidth is possible by using burst rather than element-wise accesses, provided the data is contiguous in memory. In this paper, we propose a memory allocation technique, and provide a proof-of-concept source-to-source compiler pass, that enables such burst transfers by modifying the data layout in external memory. We assess how this technique pushes up the memory throughput, leaving room for exploiting additional parallelism, for a minimal logic overhead.
Random primes in arithmetic progressions
Venue: arXiv cs.CC 2022
Year: 2022

We describe a straightforward method to generate a random prime q such that the multiplicative group GF(q)* also has a random large prime-order subgroup. The described algorithm also yields this order p as well as a p'th primitive root of unity. The methods here are efficient asymptotically, but due to large constants may not be very useful in practical settings.
Awe Versus Aww: The Effectiveness of Two Kinds of Positive Emotional Stimulation on Stress Reduction for Online Content Moderators
Venue: arXiv cs.HC 2022
Year: 2022

When people have the freedom to create and post content on the internet, particularly anonymously, they do not always respect the rules and regulations of the websites on which they post, leaving other unsuspecting users vulnerable to sexism, racism, threats, and other unacceptable content in their daily cyberspace diet. However, content moderators witness the worst of humanity on a daily basis in place of the average netizen. This takes its toll on moderators, causing stress, fatigue, and emotional distress akin to the symptomology of post-traumatic stress disorder (PTSD). The goal of the present study was to explore whether adding positive stimuli to breaktimes-images of baby animals or beautiful, aweinspiring landscapes-could help reduce the negative side-effects of being a content moderator. To test this, we had over 300 experienced content moderators read and decide whether 200 fake text-based social media posts were acceptable or not for public consumption. Although we set out to test positive emotional stimulation, however, we actually found that it is the cumulative nature of the negative emotions that likely negates most of the effects of the intervention: the longer the person had practiced content moderation, the stronger their negative experience. Connections to compassion fatigue and how best to spend work breaks as a content moderator are discussed.
Wildfires and Climate Change: What does social media tell us on linkages and public understanding? (Preliminary White Paper, February 11, 2022)
Venue: arXiv cs.SI 2022
Year: 2022

Wildfires are increasing in frequency and size across the western U.S., with some of the deadliest fires in recorded history occurring in the last few years. The public, as well as elected officials, use social media to convey opinions and knowledge on topics that are impacting their communities. We utilize the platform Twitter to assess connections of wildfire to climate change during recent events and evaluate the differences in knowledge between the public and their government officials. Results show some linkages of wildfire cause and effect, although this relationship was not large (only 5%) and was even lower at the governmental level (2%), suggesting that a broader number of the public and government did not relate climate change to recent extreme wildfires.