OpenRaiser/Intern-Atlas huggingface dataset:
A more efficient way of finding Hamiltonian cycle
Venue: arXiv cs.DS 2022
Year: 2022

In order to find Hamiltonian cycle, algorithm should find edges that creates a Hamiltonian cycle. Higher number of edges creates more possibilities to check to solve the problem. Algorithm rests on analysis of original graph and opposite graph to it. Algorithm can remove unnecessary edges from graph and test when Hamiltonian cycle can't exist in graph. Algorithm prefers "to think over" which paths should be checked than check many wrong paths.
Multiple Object Tracking: A Literature Review
Venue: arXiv cs.CV 2022
Year: 2022

Multiple Object Tracking (MOT) has gained increasing attention due to its academic and commercial potential. Although different approaches have been proposed to tackle this problem, it still remains challenging due to factors like abrupt appearance changes and severe object occlusions. In this work, we contribute the first comprehensive and most recent review on this problem. We inspect the recent advances in various aspects and propose some interesting directions for future research. To the best of our knowledge, there has not been any extensive review on this topic in the community. We endeavor to provide a thorough review on the development of this problem in recent decades. The main contributions of this review are fourfold: 1) Key aspects in an MOT system, including formulation, categorization, key principles, evaluation of MOT are discussed; 2) Instead of enumerating individual works, we discuss existing approaches according to various aspects, in each of which methods are divided into different groups and each group is discussed in detail for the principles, advances and drawbacks; 3) We examine experiments of existing publications and summarize results on popular datasets to provide quantitative and comprehensive comparisons. By analyzing the results from different perspectives, we have verified some basic agreements in the field; and 4) We provide a discussion about issues of MOT research, as well as some interesting directions which will become potential research effort in the future.
What is Usability? A Characterization based on ISO 9241-11 and ISO/IEC 25010
Venue: arXiv cs.HC 2022
Year: 2022

According to Brooke [1] "Usability does not exist in any absolute sense; it can only be defined with reference to particular contexts." That is, one cannot speak of usability without specifying what that particular usability is characterized by. Driven by the feedback of a reviewer at an international conference, I explore in which way one can precisely specify the kind of usability they are investigating in a given setting. Finally, I come up with a formalism that defines usability as a quintuple comprising the elements level of usability metrics, product, users, goals and context of use. Providing concrete values for these elements then constitutes the investigated type of usability. The use of this formalism is demonstrated in two case studies. [1] J. Brooke. SUS: A "quick and dirty" usability scale. In P. W. Jordan, B. Thomas, B. A. Weerdmeester, and A. L. McClelland, editors, Usability Evaluation in Industry. Taylor and Francis, 1996.
General Deformations of Point Configurations Viewed By a Pinhole Model Camera
Venue: arXiv cs.CV 2022
Year: 2022

This paper is a theoretical study of the following Non-Rigid Structure from Motion problem. What can be computed from a monocular view of a parametrically deforming set of points? We treat various variations of this problem for affine and polynomial deformations with calibrated and uncalibrated cameras. We show that in general at least three images with quasi-identical two deformations are needed in order to have a finite set of solutions of the points' structure and calculate some simple examples.
Composite learning control with application to inverted pendulums
Venue: arXiv cs.SY 2022
Year: 2022

Composite adaptive control (CAC) that integrates direct and indirect adaptive control techniques can achieve smaller tracking errors and faster parameter convergence compared with direct and indirect adaptive control techniques. However, the condition of persistent excitation (PE) still has to be satisfied to guarantee parameter convergence in CAC. This paper proposes a novel model reference composite learning control (MRCLC) strategy for a class of affine nonlinear systems with parametric uncertainties to guarantee parameter convergence without the PE condition. In the composite learning, an integral during a moving-time window is utilized to construct a prediction error, a linear filter is applied to alleviate the derivation of plant states, and both the tracking error and the prediction error are applied to update parametric estimates. It is proven that the closed-loop system achieves global exponential-like stability under interval excitation rather than PE of regression functions. The effectiveness of the proposed MRCLC has been verified by the application to an inverted pendulum control problem.
How to Cut Corners and Get Bounded Convex Curvature
Venue: arXiv cs.CG 2022
Year: 2022

We describe an algorithm for solving an important geometric problem arising in computer-aided manufacturing. When cutting away a region from a solid piece of material -- such as steel, wood, ceramics, or plastic -- using a rough tool in a milling machine, sharp convex corners of the region cannot be done properly, but have to be left for finer tools that are more expensive to use. We want to determine a toolpath that maximizes the use of the rough tool. In order to formulate the problem in mathematical terms, we introduce the notion of bounded convex curvature. A region of points in the plane $Q$ has \emph{bounded convex curvature} if for any point $x\in\partial Q$, there is a unit disk $U$ and $\varepsilon>0$ such that $x\in \partial U$ and all points in $U$ within distance $\varepsilon$ from $x$ are in $Q$. This translates to saying that as we traverse the boundary $\partial Q$ with the interior of $Q$ on the left side, then $\partial Q$ turns to the left with curvature at most $1$. There is no bound on the curvature where $\partial Q$ turns to the right. Given a region of points $P$ in the plane, we are now interested in computing the maximum subset $Q\subseteq P$ of bounded convex curvature. The difference in the requirement to left- and right-curvature is a natural consequence of different conditions when machining convex and concave areas of $Q$. We devise an algorithm to compute the unique maximum such set $Q$, when the boundary of $P$ consists of $n$ line segments and circular arcs of arbitrary radii. In the general case where $P$ may have holes, the algorithm runs in time $O(n^2)$ and uses $O(n)$ space. If $P$ is simply-connected, we describe a faster $O(n\log n)$ time algorithm.
Towards an Indexical Model of Situated Language Comprehension for Cognitive Agents in Physical Worlds
Venue: arXiv cs.AI 2022
Year: 2022

We propose a computational model of situated language comprehension based on the Indexical Hypothesis that generates meaning representations by translating amodal linguistic symbols to modal representations of beliefs, knowledge, and experience external to the linguistic system. This Indexical Model incorporates multiple information sources, including perceptions, domain knowledge, and short-term and long-term experiences during comprehension. We show that exploiting diverse information sources can alleviate ambiguities that arise from contextual use of underspecific referring expressions and unexpressed argument alternations of verbs. The model is being used to support linguistic interactions in Rosie, an agent implemented in Soar that learns from instruction.
Geometric Dominating Set and Set Cover via Local Search
Venue: arXiv cs.CG 2022
Year: 2022

In this paper, we study two classic optimization problems: minimum geometric dominating set and set cover. In the dominating-set problem, for a given set of objects in {the} plane as input, the objective is to choose a minimum number of input objects such that every input object is dominated by the chosen set of objects. Here, one object is dominated by {another} if both of them have {a} nonempty intersection region. For the second problem, for a given set of points and objects {in a plane}, the objective is to choose {a} minimum number of objects to cover all the points. This is a special version of the set-cover problem. For both problems obtaining a PTAS remains open for a large class of objects. For the dominating-set problem, we prove that {a} popular local-search algorithm leads to an $(1+\varepsilon)$ approximation for object sets consisting of homothetic set of convex objects (which includes arbitrary squares, $k$-regular polygons, translated and scaled copies of a convex set, etc.) in $n^{O(1/\varepsilon^2)}$ time. On the other hand, the same technique leads to a PTAS for geometric covering problem when the objects are convex pseudodisks (which includes disks, unit height rectangles, homothetic convex objects, etc.). As a consequence, we obtain an easy to implement approximation algorithm for both problems for a large class of objects, significantly improving the best known approximation guarantees.
A Probabilistic Generative Grammar for Semantic Parsing
Venue: arXiv cs.CL 2022
Year: 2022

Domain-general semantic parsing is a long-standing goal in natural language processing, where the semantic parser is capable of robustly parsing sentences from domains outside of which it was trained. Current approaches largely rely on additional supervision from new domains in order to generalize to those domains. We present a generative model of natural language utterances and logical forms and demonstrate its application to semantic parsing. Our approach relies on domain-independent supervision to generalize to new domains. We derive and implement efficient algorithms for training, parsing, and sentence generation. The work relies on a novel application of hierarchical Dirichlet processes (HDPs) for structured prediction, which we also present in this manuscript. This manuscript is an excerpt of chapter 4 from the Ph.D. thesis of Saparov (2022), where the model plays a central role in a larger natural language understanding system. This manuscript provides a new simplified and more complete presentation of the work first introduced in Saparov, Saraswat, and Mitchell (2017). The description and proofs of correctness of the training algorithm, parsing algorithm, and sentence generation algorithm are much simplified in this new presentation. We also describe the novel application of hierarchical Dirichlet processes for structured prediction. In addition, we extend the earlier work with a new model of word morphology, which utilizes the comprehensive morphological data from Wiktionary.
Accelerating Eulerian Fluid Simulation With Convolutional Networks
Venue: arXiv cs.CV 2022
Year: 2022

Efficient simulation of the Navier-Stokes equations for fluid flow is a long standing problem in applied mathematics, for which state-of-the-art methods require large compute resources. In this work, we propose a data-driven approach that leverages the approximation power of deep-learning with the precision of standard solvers to obtain fast and highly realistic simulations. Our method solves the incompressible Euler equations using the standard operator splitting method, in which a large sparse linear system with many free parameters must be solved. We use a Convolutional Network with a highly tailored architecture, trained using a novel unsupervised learning framework to solve the linear system. We present real-time 2D and 3D simulations that outperform recently proposed data-driven methods; the obtained results are realistic and show good generalization properties.
Rightsstatements.org White Paper: Requirements for the Technical Infrastructure for Standardized International Rights Statements
Venue: arXiv cs.DL 2022
Year: 2022

This document is part of the deliverables created by the RightsStatements.org consortium. It provides the technical requirements for implementation of the Standardized International Rights Statements. These requirements are based on the principles and specifications found in the normative Recommendations for Standardized International Rights Statements. This document replaces and supersedes the previously released Recommendations for the Technical Infrastructure for Standardized Rights Statements, released by this working group. The Requirements for the Technical Infrastructure for Standardized International Rights Statements describes the expected behaviours for a service that enables the delivery of human and machine-readable representations of the rights statements. It documents the fundamental decisions that informed the development of a data model grounded in Linked Data approaches. This document also provides proposed implementation guidelines and a non-normative set of examples for incorporating rights statements into provider metadata.
Automated Enterprise Applications Generation from Requirements Model
Venue: arXiv cs.SE 2022
Year: 2022

Enterprise applications can be automatically generated from a sophisticated OO design model based on model-driven approach. The design model contains information about how to decompose the system into components, how to encapsulate the system operations into classes, and how the objects of classes collaborate to fulfill the functionality of the system operations. However, the efforts to build the design model from a validated requirements model are not proportional to the return. In practice, it is very desirable to have an approach that can automatically generate standardized enterprise applications directly from the validated requirements models. In this paper, we propose an approach named RM2EA, which can reach this goal based on the contract-based requirements model. We demonstrate the proposed approach through 13 case studies. The evaluation result shows that the quality and efficiency of the generated applications are almost equal to the applications implemented by developers: firstly, we demonstrate that a popular type of enterprise applications (i.e., a Jakarta EE application) can be successfully generated by customizing and improving the set of rules; secondly, RM2EA can generate more readable or maintainable code; thirdly, the enterprise applications generated by RM2EA achieve similar performance in test results. Overall, the result is satisfactory, and the implementation of the proposed approach can be further enhanced and applied to software development in the industry.
Recurrent 3D Attentional Networks for End-to-End Active Object Recognition
Venue: arXiv cs.CV 2022
Year: 2022

Active vision is inherently attention-driven: The agent actively selects views to attend in order to fast achieve the vision task while improving its internal representation of the scene being observed. Inspired by the recent success of attention-based models in 2D vision tasks based on single RGB images, we propose to address the multi-view depth-based active object recognition using attention mechanism, through developing an end-to-end recurrent 3D attentional network. The architecture takes advantage of a recurrent neural network (RNN) to store and update an internal representation. Our model, trained with 3D shape datasets, is able to iteratively attend to the best views targeting an object of interest for recognizing it. To realize 3D view selection, we derive a 3D spatial transformer network which is differentiable for training with backpropagation, achieving much faster convergence than the reinforcement learning employed by most existing attention-based models. Experiments show that our method, with only depth input, achieves state-of-the-art next-best-view performance in time efficiency and recognition accuracy.
REFOCUS: Current & Future Search Interface Requirements for German-speaking Users
Venue: arXiv cs.HC 2022
Year: 2022

While smartphones are widely used for web browsing, also other novel devices like Smart TVs become increasingly popular. Yet, current interfaces do not cater for the newly available devices beyond touch and small screens, if at all for the latter. Particularly search engines -- today's entry points of the WWW -- must ensure their interfaces are easy to use on any web-enabled device. We report on a survey that investigated (1) users' perception and usage of current search interfaces, and (2) their expectations towards current and future search interfaces. Users are mostly satisfied with desktop and mobile search, but seem to be skeptical towards web search with novel devices and input modalities. Hence, we derive REFOCUS -- a novel set of requirements for current and future search interfaces, which shall address the demand for improvement of novel web search and has been validated by 12 dedicated experts.
Universal Algebraic Methods for Constraint Satisfaction Problems
Venue: arXiv cs.LO 2022
Year: 2022

After substantial progress over the last 15 years, the "algebraic CSP-dichotomy conjecture" reduces to the following: every local constraint satisfaction problem (CSP) associated with a finite idempotent algebra is tractable if and only if the algebra has a Taylor term operation. Despite the tremendous achievements in this area (including recently announce proofs of the general conjecture), there remain examples of small algebras with just a single binary operation whose CSP resists direct classification as either tractable or NP-complete using known methods. In this paper we present some new methods for approaching such problems, with particular focus on those techniques that help us attack the class of finite algebras known as "commutative idempotent binars" (CIBs). We demonstrate the utility of these methods by using them to prove that every CIB of cardinality at most 4 yields a tractable CSP.
Inferring Restaurant Styles by Mining Crowd Sourced Photos from User-Review Websites
Venue: arXiv cs.CV 2022
Year: 2022

When looking for a restaurant online, user uploaded photos often give people an immediate and tangible impression about a restaurant. Due to their informativeness, such user contributed photos are leveraged by restaurant review websites to provide their users an intuitive and effective search experience. In this paper, we present a novel approach to inferring restaurant types or styles (ambiance, dish styles, suitability for different occasions) from user uploaded photos on user-review websites. To that end, we first collect a novel restaurant photo dataset associating the user contributed photos with the restaurant styles from TripAdvior. We then propose a deep multi-instance multi-label learning (MIML) framework to deal with the unique problem setting of the restaurant style classification task. We employ a two-step bootstrap strategy to train a multi-label convolutional neural network (CNN). The multi-label CNN is then used to compute the confidence scores of restaurant styles for all the images associated with a restaurant. The computed confidence scores are further used to train a final binary classifier for each restaurant style tag. Upon training, the styles of a restaurant can be profiled by analyzing restaurant photos with the trained multi-label CNN and SVM models. Experimental evaluation has demonstrated that our crowd sourcing-based approach can effectively infer the restaurant style when there are a sufficient number of user uploaded photos for a given restaurant.
Equilibrium Computation in Resource Allocation Games
Venue: arXiv cs.GT 2022
Year: 2022

We study the equilibrium computation problem for two classical resource allocation games: atomic splittable congestion games and multimarket Cournot oligopolies. For atomic splittable congestion games with singleton strategies and player-specific affine cost functions, we devise the first polynomial time algorithm computing a pure Nash equilibrium. Our algorithm is combinatorial and computes the exact equilibrium assuming rational input. The idea is to compute an equilibrium for an associated integrally-splittable singleton congestion game in which the players can only split their demands in integral multiples of a common packet size. While integral games have been considered in the literature before, no polynomial time algorithm computing an equilibrium was known. Also for this class, we devise the first polynomial time algorithm and use it as a building block for our main algorithm. We then develop a polynomial time computable transformation mapping a multimarket Cournot competition game with firm-specific affine price functions and quadratic costs to an associated atomic splittable congestion game as described above. The transformation preserves equilibria in either games and, thus, leads -- via our first algorithm -- to a polynomial time algorithm computing Cournot equilibria. Finally, our analysis for integrally-splittable games implies new bounds on the difference between real and integral Cournot equilibria. The bounds can be seen as a generalization of the recent bounds for single market oligopolies obtained by Todd [2016].
Optimizing tree decompositions in MSO
Venue: arXiv cs.LO 2022
Year: 2022

The classic algorithm of Bodlaender and Kloks [J. Algorithms, 1996] solves the following problem in linear fixed-parameter time: given a tree decomposition of a graph of (possibly suboptimal) width k, compute an optimum-width tree decomposition of the graph. In this work, we prove that this problem can also be solved in mso in the following sense: for every positive integer k, there is an mso transduction from tree decompositions of width k to tree decompositions of optimum width. Together with our recent results [LICS 2016], this implies that for every k there exists an mso transduction which inputs a graph of treewidth k, and nondeterministically outputs its tree decomposition of optimum width. We also show that mso transductions can be implemented in linear fixed-parameter time, which enables us to derive the algorithmic result of Bodlaender and Kloks as a corollary of our main result.
Conditional Lower Bounds for All-Pairs Max-Flow
Venue: arXiv cs.DS 2022
Year: 2022

We provide evidence that computing the maximum flow value between every pair of nodes in a directed graph on $n$ nodes, $m$ edges,and capacities in the range $[1..n]$, which we call the All-Pairs Max-Flow problem, cannot be solved in time that is significantly faster (i.e., by a polynomial factor) than $O(n^3)$ even for sparse graphs. Since a single maximum $st$-flow can be solved in time $\tilde{O}(m\sqrt{n})$ [Lee and Sidford, FOCS 2014], we conclude that the all-pairs version might require time equivalent to $\tildeΩ(n^{3/2})$ computations of maximum $st$-flow,which strongly separates the directed case from the undirected one. Moreover, if maximum $st$-flow can be solved in time $\tilde{O}(m)$,then the runtime of $\tildeΩ(n^2)$ computations is needed. The latter settles a conjecture of Lacki, Nussbaum, Sankowski, and Wulf-Nilsen [FOCS 2012] negatively. Specifically, we show that in sparse graphs $G=(V,E,w)$, if one can compute the maximum $st$-flow from every $s$ in an input set of sources $S\subseteq V$ to every $t$ in an input set of sinks $T\subseteq V$ in time $O((|S| |T| m)^{1-ε})$,for some $|S|$, $|T|$, and a constant $ε>0$,then MAX-CNF-SAT with $n'$ variables and $m'$ clauses can be solved in time ${m'}^{O(1)}2^{(1-δ)n'}$ for a constant $δ(ε)>0$,a problem for which not even $2^{n'}/poly(n')$ algorithms are known. Such runtime for MAX-CNF-SAT would in particular refute the Strong Exponential Time Hypothesis (SETH). Hence, we improve the lower bound of Abboud, Vassilevska-Williams, and Yu [STOC 2015], who showed that for every fixed $ε>0$ and $|S|=|T|=O(\sqrt{n})$, if the above problem can be solved in time $O(n^{3/2-ε})$, then some incomparable conjecture is false. Furthermore, a larger lower bound than ours implies strictly super-linear time for maximum $st$-flow problem, which would be an amazing breakthrough.