**Vaguery : algorithms**
2635

The Stanford Natural Language Processing Group

13 days ago by Vaguery

Tregex is a utility for matching patterns in trees, based on tree relationships and regular expression matches on nodes (the name is short for "tree regular expressions"). Tregex comes with Tsurgeon, a tree transformation language. Also included from version 2.0 on is a similar package which operates on dependency graphs (class SemanticGraph, called semgrex.

pattern-matching
library
software-development
algorithms
rather-interesting
consider:in-gp-apps
consider:classification
to-understand
to-complain-about-docs
data-structures
13 days ago by Vaguery

Robustness of the two-sample t-test

13 days ago by Vaguery

It is fairly well known that the t-test is robust to departures from a normal distribution, as long as the actual distribution is symmetric. That is, the test works more or less as advertised as long as the distribution is symmetric like a normal distribution, but it may not work as expected if the distribution is asymmetric.

This post will explore the robustness of the t-test via simulation. How far can you be from a normal distribution and still do OK? Can you have any distribution as long as it’s symmetric? Does a little asymmetry ruin everything? If something does go wrong, how does it go wrong?

statistics
looking-to-see
rather-interesting
algorithms
robustness
to-do
to-write-about
consider:animation
This post will explore the robustness of the t-test via simulation. How far can you be from a normal distribution and still do OK? Can you have any distribution as long as it’s symmetric? Does a little asymmetry ruin everything? If something does go wrong, how does it go wrong?

13 days ago by Vaguery

[1804.07150] Improved Bounds for Guarding Plane Graphs with Edges

20 days ago by Vaguery

An "edge guard set" of a plane graph G is a subset Γ of edges of G such that each face of G is incident to an endpoint of an edge in Γ. Such a set is said to guard G. We improve the known upper bounds on the number of edges required to guard any n-vertex embedded planar graph G:

1- We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that G can be guarded with at most 2n5 edges, then extend this approach with a deeper analysis to yield an improved bound of 3n8 edges for any plane graph.

2- We prove that there exists an edge guard set of G with at most n3+α9 edges, where α is the number of quadrilateral faces in G. This improves the previous bound of n3+α by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in G, we show that n3 edges suffice, removing the dependence on α.

graph-theory
computational-complexity
computational-geometry
algorithms
feature-construction
rather-interesting
to-understand
to-simulate
1- We present a simple inductive proof for a theorem of Everett and Rivera-Campo (1997) that G can be guarded with at most 2n5 edges, then extend this approach with a deeper analysis to yield an improved bound of 3n8 edges for any plane graph.

2- We prove that there exists an edge guard set of G with at most n3+α9 edges, where α is the number of quadrilateral faces in G. This improves the previous bound of n3+α by Bose, Kirkpatrick, and Li (2003). Moreover, if there is no short path between any two quadrilateral faces in G, we show that n3 edges suffice, removing the dependence on α.

20 days ago by Vaguery

[1808.01984] Time-Dependent Shortest Path Queries Among Growing Discs

20 days ago by Vaguery

The determination of time-dependent collision-free shortest paths has received a fair amount of attention. Here, we study the problem of computing a time-dependent shortest path among growing discs which has been previously studied for the instance where the departure times are fixed. We address a more general setting: For two given points s and d, we wish to determine the function (t) which is the minimum arrival time at d for any departure time t at s. We present a (1+ϵ)-approximation algorithm for computing (t). As part of preprocessing, we execute O(1ϵlog(rc)) shortest path computations for fixed departure times, where r is the maximum speed of the robot and c is the minimum growth rate of the discs. For any query departure time t≥0 from s, we can approximate the minimum arrival time at the destination in O(log(1ϵ)+loglog(rc)) time, within a factor of 1+ϵ of optimal. Since we treat the shortest path computations as black-box functions, for different settings of growing discs, we can plug-in different shortest path algorithms. Thus, the exact time complexity of our algorithm is determined by the running time of the shortest path computations.

computational-complexity
computational-geometry
planning
constraint-satisfaction
optimization
rather-interesting
to-understand
algorithms
to-simulate
to-write-about
consider:robustness
20 days ago by Vaguery

[1810.09232] On the Minimum Consistent Subset Problem

25 days ago by Vaguery

Let P be a set of n colored points in the plane. Introduced by Hart (1968), a consistent subset of P, is a set S⊆P such that for every point p in P∖S, the closest point of p in S has the same color as p. The consistent subset problem is to find a consistent subset of P with minimum cardinality. This problem is known to be NP-complete even for two-colored point sets. Since the initial presentation of this problem, aside from the hardness results, there has not been a significant progress from the algorithmic point of view. In this paper we present the following algorithmic results:

1. The first subexponential-time algorithm for the consistent subset problem.

2. An O(nlogn)-time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Towards our proof of this running time we present a deterministic O(nlogn)-time algorithm for computing a variant of the compact Voronoi diagram; this improves the previously claimed expected running time.

3. An O(nlog2n)-time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known O(n2) running time which is due to Wilfong (SoCG 1991).

4. An O(n)-time algorithm for the consistent subset problem on collinear points; this improves the previous best known O(n2) running time.

5. A non-trivial O(n6)-time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines.

To obtain these results, we combine tools from planar separators, additively-weighted Voronoi diagrams with respect to convex distance functions, point location in farthest-point Voronoi diagrams, range trees, paraboloid lifting, minimum covering of a circle with arcs, and several geometric transformations.

computational-complexity
computational-geometry
algorithms
combinatorics
plane-geometry
to-simulate
to-write-about
consider:movement
consider:heuristics
1. The first subexponential-time algorithm for the consistent subset problem.

2. An O(nlogn)-time algorithm that finds a consistent subset of size two in two-colored point sets (if such a subset exists). Towards our proof of this running time we present a deterministic O(nlogn)-time algorithm for computing a variant of the compact Voronoi diagram; this improves the previously claimed expected running time.

3. An O(nlog2n)-time algorithm that finds a minimum consistent subset in two-colored point sets where one color class contains exactly one point; this improves the previous best known O(n2) running time which is due to Wilfong (SoCG 1991).

4. An O(n)-time algorithm for the consistent subset problem on collinear points; this improves the previous best known O(n2) running time.

5. A non-trivial O(n6)-time dynamic programming algorithm for the consistent subset problem on points arranged on two parallel lines.

To obtain these results, we combine tools from planar separators, additively-weighted Voronoi diagrams with respect to convex distance functions, point location in farthest-point Voronoi diagrams, range trees, paraboloid lifting, minimum covering of a circle with arcs, and several geometric transformations.

25 days ago by Vaguery

[1905.07124] Variations of largest rectangle recognition amidst a bichromatic point set

25 days ago by Vaguery

Classical separability problem involving multi-color point sets is an important area of study in computational geometry. In this paper, we study different separability problems for bichromatic point set P=P_r\cup P_b on a plane, where Pr and Pb represent the set of n red points and m blue points respectively, and the objective is to compute a monochromatic object of the desired type and of maximum size. We propose in-place algorithms for computing (i) an arbitrarily oriented monochromatic rectangle of maximum size in R^2, (ii) an axis-parallel monochromatic cuboid of maximum size in R^3. The time complexities of the algorithms for problems (i) and (ii) are O(m(m+n)(m\sqrt{n}+m\log m+n \log n)) and O(m^3\sqrt{n}+m^2n\log n), respectively. As a prerequisite, we propose an in-place construction of the classic data structure the k-d tree, which was originally invented by J. L. Bentley in 1975. Our in-place variant of the k-d tree for a set of n points in R^k supports both orthogonal range reporting and counting query using O(1) extra workspace, and these query time complexities are the same as the classical complexities, i.e., O(n^{1-1/k}+\mu) and O(n^{1-1/k}), respectively, where \mu is the output size of the reporting query. The construction time of this data structure is O(n\log n). Both the construction and query algorithms are non-recursive in nature that do not need O(\log n) size recursion stack compared to the previously known construction algorithm for in-place k-d tree and query in it. We believe that this result is of independent interest. We also propose an algorithm for the problem of computing an arbitrarily oriented rectangle of maximum weight among a point set P=P_r \cup P_b, where each point in P_b (resp. P_r) is associated with a negative (resp. positive) real-valued weight that runs in O(m^2(n+m)\log(n+m)) time using O(n) extra space.

computational-complexity
computational-geometry
optimization
sorting
algorithms
heuristics
to-simulate
to-write-about
consider:variants
25 days ago by Vaguery

[1906.11948] Packing Boundary-Anchored Rectangles and Squares

25 days ago by Vaguery

Consider a set P of n points on the boundary of an axis-aligned square Q. We study the boundary-anchored packing problem on P in which the goal is to find a set of interior-disjoint axis-aligned rectangles in Q such that each rectangle is anchored (has a corner at some point in P), each point in P is used to anchor at most one rectangle, and the total area of the rectangles is maximized. Here, a rectangle is anchored at a point p in P if one of its corners coincides with p. In this paper, we show how to solve this problem in time linear in n, provided that the points of P are given in sorted order along the boundary of Q. We also consider the problem for anchoring squares and give an O(n4)-time algorithm when the points in P lie on two opposite sides of Q.

packing
operations-research
computational-geometry
computational-complexity
algorithms
optimization
constraint-satisfaction
rather-interesting
to-write-about
to-simulate
consider:feature-discovery
consider:heuristics
25 days ago by Vaguery

[1907.01617] A Short Proof of the Toughness of Delaunay Triangulations

25 days ago by Vaguery

We present a self-contained short proof of the seminal result of Dillencourt (SoCG 1987 and DCG 1990) that Delaunay triangulations, of planar point sets in general position, are 1-tough. An important implication of this result is that Delaunay triangulations have perfect matchings. Another implication of our result is a proof of the conjecture of Aichholzer et al. (2010) that at least n points are required to block any n-vertex Delaunay triangulation

computational-geometry
computational-complexity
rather-interesting
algorithms
hard-problems
feature-construction
to-simulate
to-write-about
consider:hardness-features
25 days ago by Vaguery

Constructing random polygons | Proceedings of the 9th ACM SIGITE conference on Information technology education

26 days ago by Vaguery

The construction of random polygons has been used in psychological research and for the testing of algorithms. With the increased popularity of client-side vector based graphics in the web browser such as seen in Flash and SVG, as well as the newly introduced <canvas> tag in HTML5.0, the use of random shapes for creation of scenes for animation and interactive art requires the construction of random polygons. A natural question, then, is how to generate random polygons in a way which is computationally efficient (particularly in a resource limited environment such as the web browser). This paper presents a random polygon algorithm (RPA) that generates polygons that are random and representative of the class of all n-gons in O(n2logn) time. Our algorithm differs from other approaches in that the vertices are generated randomly, the algorithm is inclusive (i.e. each polygon has a non-zero probability to be constructed), and it runs efficiently in polynomial time.

probability-theory
sampling
computational-geometry
algorithms
rather-interesting
to-write-about
to-simulate
26 days ago by Vaguery

[1712.04922] Closing the gap for pseudo-polynomial strip packing

4 weeks ago by Vaguery

The set of 2-dimensional packing problems builds an important class of optimization problems and Strip Packing together with 2-dimensional Bin Packing and 2-dimensional Knapsack is one of the most famous of these problems. Given a set of rectangular axis parallel items and a strip with bounded width and infinite height the objective is to find a packing of the items into the strip which minimizes the packing height. We speak of pseudo-polynomial Strip Packing if we consider algorithms with pseudo-polynomial running time with respect to the width of the strip.

It is known that there is no pseudo-polynomial algorithm for Strip Packing with a ratio better than 5/4 unless P=NP. The best algorithm so far has a ratio of (4/3+ε). In this paper, we close this gap between inapproximability result and best known algorithm by presenting an algorithm with approximation ratio (5/4+ε) and thus categorize the problem accurately. The algorithm uses a structural result which states that each optimal solution can be transformed such that it has one of a polynomial number of different forms. The strength of this structural result is that it applies to other problem settings as well for example to Strip Packing with rotations (90 degrees) and Contiguous Moldable Task Scheduling. This fact enabled us to present algorithms with approximation ratio (5/4+ε) for these problems as well.

operations-research
optimization
strip-packing
packing
numerical-methods
mathematical-programming
algorithms
computational-complexity
horse-races
to-write-about
to-simulate
consider:genetic-programming
consider:performance-measures
consider:heuristics
It is known that there is no pseudo-polynomial algorithm for Strip Packing with a ratio better than 5/4 unless P=NP. The best algorithm so far has a ratio of (4/3+ε). In this paper, we close this gap between inapproximability result and best known algorithm by presenting an algorithm with approximation ratio (5/4+ε) and thus categorize the problem accurately. The algorithm uses a structural result which states that each optimal solution can be transformed such that it has one of a polynomial number of different forms. The strength of this structural result is that it applies to other problem settings as well for example to Strip Packing with rotations (90 degrees) and Contiguous Moldable Task Scheduling. This fact enabled us to present algorithms with approximation ratio (5/4+ε) for these problems as well.

4 weeks ago by Vaguery

[1702.08066] On the Classification and Algorithmic Analysis of Carmichael Numbers

4 weeks ago by Vaguery

In this paper, we study the properties of Carmichael numbers, false positives to several primality tests. We provide a classification for Carmichael numbers with a proportion of Fermat witnesses of less than 50%, based on if the smallest prime factor is greater than a determined lower bound. In addition, we conduct a Monte Carlo simulation as part of a probabilistic algorithm to detect if a given composite number is Carmichael. We modify this highly accurate algorithm with a deterministic primality test to create a novel, more efficient algorithm that differentiates between Carmichael numbers and prime numbers.

number-theory
primes
rather-interesting
feature-construction
classification
tricky-cases
edge-cases
algorithms
performance-measure
to-simulate
to-write-about
consider:classification
computational-complexity
4 weeks ago by Vaguery

[1806.06751] Entropy of hard square lattice gas with $k$ distinct species of particles: coloring problems and vertex models

4 weeks ago by Vaguery

Coloring the faces of 2-dimensional square lattice with k distinct colors such that no two adjacent faces have the same color is considered by establishing connection between the k coloring problem and a generalized vertex model. Associating the colors with k distinct species of particles with infinite repulsive force between nearest neighbors of the same type and zero chemical potential μ associated with each species, the number of ways [W(k)]N for large N is related to the entropy of the {\it{hard square lattice gas}} at close packing of the lattice, where N is the number of lattice sites. We discuss the evaluation of W(k) using transfer matrix method with non-periodic boundary conditions imposed on at least one dimension and show the characteristic Toeplitz block structure of the transfer matrix. Using this result, we present some analytical calculations for non-periodic models that remain finite in one dimension. The case k=3 is found to approach the exact result obtained by Lieb for the residual entropy of ice with periodic boundary conditions. Finally, we show, by explicit calculation of the contribution of subgraphs and the series expansion of W(k), that the genenralized Pauling type estimate(which is based on mean field approximation) dominates at large values of k. We thus also provide an alternative series expansion for the chromatic polynomial of a regular square graph.

graph-theory
graph-coloring
algorithms
parallel
distributed-processing
cellular-automata
rather-interesting
to-simulate
to-write-about
consider:constraint-satisfaction
consider:rules-variants
4 weeks ago by Vaguery

[1805.03963] Monotone Learning with Rectified Wire Networks

5 weeks ago by Vaguery

We introduce a new neural network model, together with a tractable and monotone online learning algorithm. Our model describes feed-forward networks for classification, with one output node for each class. The only nonlinear operation is rectification using a ReLU function with a bias. However, there is a rectifier on every edge rather than at the nodes of the network. There are also weights, but these are positive, static, and associated with the nodes. Our "rectified wire" networks are able to represent arbitrary Boolean functions. Only the bias parameters, on the edges of the network, are learned. Another departure in our approach, from standard neural networks, is that the loss function is replaced by a constraint. This constraint is simply that the value of the output node associated with the correct class should be zero. Our model has the property that the exact norm-minimizing parameter update, required to correctly classify a training item, is the solution to a quadratic program that can be computed with a few passes through the network. We demonstrate a training algorithm using this update, called sequential deactivation (SDA), on MNIST and some synthetic datasets. Upon adopting a natural choice for the nodal weights, SDA has no hyperparameters other than those describing the network structure. Our experiments explore behavior with respect to network size and depth in a family of sparse expander networks.

machine-learning
neural-networks
representation
algorithms
to-simulate
to-write-about
consider:performance-measures
rather-interesting
5 weeks ago by Vaguery

[1612.04861] Some Counterexamples for Compatible Triangulations

5 weeks ago by Vaguery

We consider the conjecture by Aichholzer, Aurenhammer, Hurtado, and Krasser that any two points sets with the same cardinality and the same size convex hull can be triangulated in the "same" way, more precisely via \emph{compatible triangulations}. We show counterexamples to various strengthened versions of this conjecture.

computational-geometry
equivalence
triangulation
algorithms
rather-interesting
feature-construction
graph-theory
to-simulate
to-write-about
5 weeks ago by Vaguery

[1902.01486] Stiefel manifolds and polygons

5 weeks ago by Vaguery

Polygons are compound geometric objects, but when trying to understand the expected behavior of a large collection of random polygons -- or even to formalize what a random polygon is -- it is convenient to interpret each polygon as a point in some parameter space, essentially trading the complexity of the object for the complexity of the space. In this paper I describe such an interpretation where the parameter space is a Stiefel manifold and show how to exploit the geometry of the Stiefel manifold both to generate random polygons and to morph one polygon into another.

computational-geometry
interpolation
algorithms
rather-interesting
visualization
mathematical-recreations
to-simulate
5 weeks ago by Vaguery

[1203.3353] Solving Structure with Sparse, Randomly-Oriented X-ray Data

5 weeks ago by Vaguery

Single-particle imaging experiments of biomolecules at x-ray free-electron lasers (XFELs) require processing of hundreds of thousands (or more) of images that contain very few x-rays. Each low-flux image of the diffraction pattern is produced by a single, randomly oriented particle, such as a protein. We demonstrate the feasibility of collecting data at these extremes, averaging only 2.5 photons per frame, where it seems doubtful there could be information about the state of rotation, let alone the image contrast. This is accomplished with an expectation maximization algorithm that processes the low-flux data in aggregate, and without any prior knowledge of the object or its orientation. The versatility of the method promises, more generally, to redefine what measurement scenarios can provide useful signal in the high-noise regime.

diffraction
inverse-problems
tomography
rather-interesting
algorithms
statistics
probability-theory
inference
to-simulate
to-write-about
optimization
signal-processing
5 weeks ago by Vaguery

[1706.03049] A linear-time algorithm for the maximum-area inscribed triangle in a convex polygon

5 weeks ago by Vaguery

Given the n vertices of a convex polygon in cyclic order, can the triangle of maximum area inscribed in P be determined by an algorithm with O(n) time complexity? A purported linear-time algorithm by Dobkin and Snyder from 1979 has recently been shown to be incorrect by Keikha, Löffler, Urhausen, and van der Hoog. These authors give an alternative algorithm with O(n log n) time complexity. Here we give an algorithm with linear time complexity.

computational-complexity
computational-geometry
algorithms
rather-interesting
plane-geometry
to-simulate
to-write-about
consider:genetic-programming
5 weeks ago by Vaguery

[1305.1961] An Improved Three-Weight Message-Passing Algorithm

5 weeks ago by Vaguery

We describe how the powerful "Divide and Concur" algorithm for constraint satisfaction can be derived as a special case of a message-passing version of the Alternating Direction Method of Multipliers (ADMM) algorithm for convex optimization, and introduce an improved message-passing algorithm based on ADMM/DC by introducing three distinct weights for messages, with "certain" and "no opinion" weights, as well as the standard weight used in ADMM/DC. The "certain" messages allow our improved algorithm to implement constraint propagation as a special case, while the "no opinion" messages speed convergence for some problems by making the algorithm focus only on active constraints. We describe how our three-weight version of ADMM/DC can give greatly improved performance for non-convex problems such as circle packing and solving large Sudoku puzzles, while retaining the exact performance of ADMM for convex problems. We also describe the advantages of our algorithm compared to other message-passing algorithms based upon belief propagation.

constraint-satisfaction
algorithms
distributed-processing
rather-interesting
to-simulate
to-write-about
consider:sudoku
consider:performance-measures
5 weeks ago by Vaguery

[1903.04900] The 5-Way Scale

5 weeks ago by Vaguery

In this paper, we discuss coin-weighing problems that use a 5-way scale which has five different possible outcomes: MUCH LESS, LESS, EQUAL, MORE, and MUCH MORE. The 5-way scale provides more information than the regular 3-way scale. We study the problem of finding two fake coins from a pile of identically looking coins in a minimal number of weighings using a 5-way scale. We discuss similarities and differences between the 5-way and 3-way scale. We introduce a strategy for a 5-way scale that can find both counterfeit coins among 2k coins in k+1 weighings, which is better than any strategy for a 3-way scale.

mathematical-recreations
logic-puzzles
constraint-satisfaction
combinatorics
algorithms
rather-interesting
to-write-about
to-simulate
consider:looking-to-see
consider:performance-measures
5 weeks ago by Vaguery

[1909.02415] It's Common Knowledge

5 weeks ago by Vaguery

We discuss some old common knowledge puzzles and introduce a lot of new common knowledge puzzles.

mathematical-recreations
logic
puzzles
information-theory
algorithms
rather-interesting
to-simulate
to-write-about
5 weeks ago by Vaguery

[math/0202236] On comparing the writhe of a smooth curve to the writhe of an inscribed polygon

5 weeks ago by Vaguery

We find bounds on the difference between the writhing number of a smooth curve, and the writhing number of a polygon inscribed within. The proof is based on an extension of Fuller's difference of writhe formula to the case of polygonal curves. The results establish error bounds useful in the computation of writhe.

algorithms
approximation
computational-complexity
computational-geometry
numerical-methods
rather-interesting
to-write-about
to-simulate
5 weeks ago by Vaguery

[1910.14481] Continual Unsupervised Representation Learning

5 weeks ago by Vaguery

Continual learning aims to improve the ability of modern learning systems to deal with non-stationary distributions, typically by attempting to learn a series of tasks sequentially. Prior art in the field has largely considered supervised or reinforcement learning tasks, and often assumes full knowledge of task labels and boundaries. In this work, we propose an approach (CURL) to tackle a more general problem that we will refer to as unsupervised continual learning. The focus is on learning representations without any knowledge about task identity, and we explore scenarios when there are abrupt changes between tasks, smooth transitions from one task to another, or even when the data is shuffled. The proposed approach performs task inference directly within the model, is able to dynamically expand to capture new concepts over its lifetime, and incorporates additional rehearsal-based techniques to deal with catastrophic forgetting. We demonstrate the efficacy of CURL in an unsupervised learning setting with MNIST and Omniglot, where the lack of labels ensures no information is leaked about the task. Further, we demonstrate strong performance compared to prior art in an i.i.d setting, or when adapting the technique to supervised tasks such as incremental class learning.

machine-learning
reinvented-wheels
continual-learning
neural-networks
unsupervised-learning
algorithms
to-write-about
to-simulate
consider:genetic-programming
revive:1998-paper
5 weeks ago by Vaguery

[math/0508248] Self-contact Sets for 50 Tightly Knotted and Linked Tubes

5 weeks ago by Vaguery

We report on new numerical computations of the set of self-contacts in tightly knotted tubes of uniform circular cross-section. Such contact sets have been obtained before for the trefoil and figure eight knots by simulated annealing -- we use constrained gradient-descent to provide new self-contact sets for those and 48 other knot and link types. The minimum length of all unit diameter tubes in a given knot or link type is called the ropelength of that class of curves. Our computations yield improved upper bounds for the ropelength of all knots and links with 9 or fewer crossings except the trefoil.

knot-theory
simulation
rather-interesting
algorithms
optimization
computational-geometry
to-write-about
to-try
5 weeks ago by Vaguery

[1212.1617] Similarity of Polygonal Curves in the Presence of Outliers

6 weeks ago by Vaguery

The Fréchet distance is a well studied and commonly used measure to capture the similarity of polygonal curves. Unfortunately, it exhibits a high sensitivity to the presence of outliers. Since the presence of outliers is a frequently occurring phenomenon in practice, a robust variant of Fréchet distance is required which absorbs outliers. We study such a variant here. In this modified variant, our objective is to minimize the length of subcurves of two polygonal curves that need to be ignored (MinEx problem), or alternately, maximize the length of subcurves that are preserved (MaxIn problem), to achieve a given Fréchet distance. An exact solution to one problem would imply an exact solution to the other problem. However, we show that these problems are not solvable by radicals over ℚ and that the degree of the polynomial equations involved is unbounded in general. This motivates the search for approximate solutions. We present an algorithm, which approximates, for a given input parameter δ, optimal solutions for the \MinEx\ and \MaxIn\ problems up to an additive approximation error δ times the length of the input curves. The resulting running time is upper bounded by (n3δlog(nδ)), where n is the complexity of the input polygonal curves.

computational-geometry
robustness
algorithms
numerical-methods
to-write-about
to-simulate
consider:robustness
consider:feature-discovery
6 weeks ago by Vaguery

[1211.4559] Visiting All Sites with Your Dog

6 weeks ago by Vaguery

Given a polygonal curve P, a pointset S, and an \epsilon > 0, we study the problem of finding a polygonal curve Q whose vertices are from S and has a Frechet distance less or equal to \epsilon to curve P. In this problem, Q must visit every point in S and we are allowed to reuse points of pointset in building Q. First, we show that this problem in NP-Complete. Then, we present a polynomial time algorithm for a special cases of this problem, when P is a convex polygon.

computational-complexity
computational-geometry
algorithms
planning
rather-interesting
to-simulate
consider:performance-measures
consider:rediscovery
6 weeks ago by Vaguery

[1204.2634] Space-efficient Algorithms for Visibility Problems in Simple Polygon

6 weeks ago by Vaguery

Given a simple polygon P consisting of n vertices, we study the problem of designing space-efficient algorithms for computing (i) the visibility polygon of a point inside P, (ii) the weak visibility polygon of a line segment inside P and (iii) the minimum link path between a pair of points inside P. For problem (i) two algorithms are proposed. The first one is an in-place algorithm where the input array may be lost. It uses only O(1) extra space apart from the input array. The second one assumes that the input is given in a read-only array, and it needs O(n‾√) extra space. The time complexity of both the algorithms are O(n). For problem (ii), we have assumed that the input polygon is given in a read-only array. Our proposed algorithm runs in O(n2) time using O(1) extra space. For problem (iii) the time and space complexities of our proposed algorithm are O(kn) and O(1) respectively; k is the length (number of links) in a minimum link path between the given pair of points.

plane-geometry
computational-complexity
computational-geometry
visibility-problems
algorithms
horse-races
to-write-about
to-simulate
consider:performance-measures
6 weeks ago by Vaguery

[1111.2918] Localized Geometric Query Problems

6 weeks ago by Vaguery

A new class of geometric query problems are studied in this paper. We are required to preprocess a set of geometric objects P in the plane, so that for any arbitrary query point q, the largest circle that contains q but does not contain any member of P, can be reported efficiently. The geometric sets that we consider are point sets and boundaries of simple polygons.

computational-geometry
computational-complexity
algorithms
to-simulate
to-write-about
consider:rediscovery
6 weeks ago by Vaguery

Depth of Field with Colour Shift · inconvergent

6 weeks ago by Vaguery

The last time I wrote, I described a relatively easy way to get a nice depth of field effect. Let's see how we can add a colour shift effect as well. I've tried to repeat most of the relevant information here, but you might want to read the previous post before you continue.

generative-art
visualization
algorithms
animation
programming
to-simulate
to-try
6 weeks ago by Vaguery

[1812.01502] Parallelising Particle Filters with Butterfly Interactions

6 weeks ago by Vaguery

Bootstrap particle filter (BPF) is the corner stone of many popular algorithms used for solving inference problems involving time series that are observed through noisy measurements in a non-linear and non-Gaussian context. The long term stability of BPF arises from particle interactions which in the context of modern parallel computing systems typically means that particle information needs to be communicated between processing elements, which makes parallel implementation of BPF nontrivial.

In this paper we show that it is possible to constrain the interactions in a way which, under some assumptions, enables the reduction of the cost of communicating the particle information while still preserving the consistency and the long term stability of the BPF. Numerical experiments demonstrate that although the imposed constraints introduce additional error, the proposed method shows potential to be the method of choice in certain settings.

parallel-processing
distributed-processing
algorithms
collective-behavior
simulation
numerical-methods
heuristics
to-understand
to-write-about
optimization
In this paper we show that it is possible to constrain the interactions in a way which, under some assumptions, enables the reduction of the cost of communicating the particle information while still preserving the consistency and the long term stability of the BPF. Numerical experiments demonstrate that although the imposed constraints introduce additional error, the proposed method shows potential to be the method of choice in certain settings.

6 weeks ago by Vaguery

[nlin/0206025] The Mermin fixed point

6 weeks ago by Vaguery

The most efficient known method for solving certain computational problems is to construct an iterated map whose fixed points are by design the problem's solution. Although the origins of this idea go back at least to Newton, the clearest expression of its logical basis is an example due to Mermin. A contemporary application in image recovery demonstrates the power of the method.

inverse-problems
rather-interesting
algorithms
heuristics
to-understand
to-write-about
to-simulate
consider:numerical-methods
consider:performance-measures
consider:lexicase
6 weeks ago by Vaguery

[1610.07717] Distributed and parallel time series feature extraction for industrial big data applications

6 weeks ago by Vaguery

The all-relevant problem of feature selection is the identification of all strongly and weakly relevant attributes. This problem is especially hard to solve for time series classification and regression in industrial applications such as predictive maintenance or production line optimization, for which each label or regression target is associated with several time series and meta-information simultaneously. Here, we are proposing an efficient, scalable feature extraction algorithm for time series, which filters the available features in an early stage of the machine learning pipeline with respect to their significance for the classification or regression task, while controlling the expected percentage of selected but irrelevant features. The proposed algorithm combines established feature extraction methods with a feature importance filter. It has a low computational complexity, allows to start on a problem with only limited domain knowledge available, can be trivially parallelized, is highly scalable and based on well studied non-parametric hypothesis tests. We benchmark our proposed algorithm on all binary classification problems of the UCR time series classification archive as well as time series from a production line optimization project and simulated stochastic processes with underlying qualitative change of dynamics.

time-series
feature-extraction
machine-learning
algorithms
to-understand
compare:pareto-gp
6 weeks ago by Vaguery

[1806.04325] Augmenting Stream Constraint Programming with Eventuality Conditions

6 weeks ago by Vaguery

Stream constraint programming is a recent addition to the family of constraint programming frameworks, where variable domains are sets of infinite streams over finite alphabets. Previous works showed promising results for its applicability to real-world planning and control problems. In this paper, motivated by the modelling of planning applications, we improve the expressiveness of the framework by introducing 1) the "until" constraint, a new construct that is adapted from Linear Temporal Logic and 2) the @ operator on streams, a syntactic sugar for which we provide a more efficient solving algorithm over simple desugaring. For both constructs, we propose corresponding novel solving algorithms and prove their correctness. We present competitive experimental results on the Missionaries and Cannibals logic puzzle and a standard path planning application on the grid, by comparing with Apt and Brand's method for verifying eventuality conditions using a CP approach.

game-theory
constraint-satisfaction
algorithms
computational-complexity
to-simulate
to-understand
to-write-about
6 weeks ago by Vaguery

[1910.10288] Location-Relative Attention Mechanisms For Robust Long-Form Speech Synthesis

6 weeks ago by Vaguery

Despite the ability to produce human-level speech for in-domain text, attention-based end-to-end text-to-speech (TTS) systems suffer from text alignment failures that increase in frequency for out-of-domain text. We show that these failures can be addressed using simple location-relative attention mechanisms that do away with content-based query/key comparisons. We compare two families of attention mechanisms: location-relative GMM-based mechanisms and additive energy-based mechanisms. We suggest simple modifications to GMM-based attention that allow it to align quickly and consistently during training, and introduce a new location-relative attention mechanism to the additive energy-based family, called Dynamic Convolution Attention (DCA). We compare the various mechanisms in terms of alignment speed and consistency during training, naturalness, and ability to generalize to long utterances, and conclude that GMM attention and DCA can generalize to very long utterances, while preserving naturalness for shorter, in-domain utterances.

speech-synthesis
natural-language-processing
neural-networks
recurrent-networks
algorithms
feature-construction
rather-interesting
to-write-about
to-simulate
6 weeks ago by Vaguery

[1611.01090] General and Fractional Hypertree Decompositions: Hard and Easy Cases

6 weeks ago by Vaguery

Hypertree decompositions, as well as the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHD) are hypergraph decomposition methods successfully used for answering conjunctive queries and for the solution of constraint satisfaction problems. Every hypergraph H has a width relative to each of these decomposition methods: its hypertree width hw(H), its generalized hypertree width ghw(H), and its fractional hypertree width fhw(H), respectively.

It is known that hw(H) <= k can be checked in polynomial time for fixed k, while checking ghw(H) <= k is NP-complete for any k greater than or equal to 3. The complexity of checking fhw(H) <= k for a fixed k has been open for more than a decade.

We settle this open problem by showing that checking fhw(H) <= k is NP-complete, even for k=2. The same construction allows us to prove also the NP-completeness of checking ghw(H) <= k for k=2. After proving these hardness results, we identify meaningful restrictions, for which checking for bounded ghw or fhw becomes tractable.

constraint-satisfaction
hypergraphs
representation
rather-interesting
computational-complexity
algorithms
feature-construction
to-understand
to-write-about
consider:simulation
consider:feature-discovery
It is known that hw(H) <= k can be checked in polynomial time for fixed k, while checking ghw(H) <= k is NP-complete for any k greater than or equal to 3. The complexity of checking fhw(H) <= k for a fixed k has been open for more than a decade.

We settle this open problem by showing that checking fhw(H) <= k is NP-complete, even for k=2. The same construction allows us to prove also the NP-completeness of checking ghw(H) <= k for k=2. After proving these hardness results, we identify meaningful restrictions, for which checking for bounded ghw or fhw becomes tractable.

6 weeks ago by Vaguery

[1901.05372] The notion of "Unimaginable Numbers" in computational number theory

6 weeks ago by Vaguery

Literature considers under the name \emph{unimaginable numbers} any positive integer going beyond any physical application, with this being more of a vague description of what we are talking about rather than an actual mathematical definition. This simply means that research in this topic must always consider shortened representations, usually involving \emph{recursion}, to even being able to describe such numbers.\par\medskip One of the most known methodologies to conceive such numbers is using \emph{hyperoperations}, that is a sequence of binary functions defined recursively starting from the usual chain: addition - multiplication - exponentiation. The most important notations to represent such hyperoperations have been considered by Knuth, Goodstein, Ackermann and Conway as described in this work's introduction.\par\medskip Within this work we will give an axiomatic set for this topic, and then try to find on one hand other ways to represent unimaginable numbers, as well as on the other hand applications to computer science, where the algorithmic nature of representations and the increased computation capabilities of computers give the perfect field to develop further the topic.\par\medskip After the introduction, we will give axioms and generalizations for the up-arrow notation; in the subsequent section we consider a representation via rooted trees of the \emph{hereditary base-n notation} involved in Goodstein's theorem, which can be used efficiently to represent some defective unimaginable numbers, and in the last section we will analyse some methods to compare big numbers, proving specifically a theorem about approximation using scientific notation.

number-theory
representation
notation
algorithms
rather-interesting
to-write-about
to-simulate
consider:sense-of-scale
6 weeks ago by Vaguery

[1902.08171] A Dictionary Based Generalization of Robust PCA

6 weeks ago by Vaguery

We analyze the decomposition of a data matrix, assumed to be a superposition of a low-rank component and a component which is sparse in a known dictionary, using a convex demixing method. We provide a unified analysis, encompassing both undercomplete and overcomplete dictionary cases, and show that the constituent components can be successfully recovered under some relatively mild assumptions up to a certain global sparsity level. Further, we corroborate our theoretical results by presenting empirical evaluations in terms of phase transitions in rank and sparsity for various dictionary sizes.

dimension-reduction
algorithms
machine-learning
inverse-problems
to-write-about
to-simulate
consider:feature-discovery
6 weeks ago by Vaguery

[1601.00670] Variational Inference: A Review for Statisticians

6 weeks ago by Vaguery

One of the core problems of modern statistics is to approximate difficult-to-compute probability densities. This problem is especially important in Bayesian statistics, which frames all inference about unknown quantities as a calculation involving the posterior density. In this paper, we review variational inference (VI), a method from machine learning that approximates probability densities through optimization. VI has been used in many applications and tends to be faster than classical methods, such as Markov chain Monte Carlo sampling. The idea behind VI is to first posit a family of densities and then to find the member of that family which is close to the target. Closeness is measured by Kullback-Leibler divergence. We review the ideas behind mean-field variational inference, discuss the special case of VI applied to exponential family models, present a full example with a Bayesian mixture of Gaussians, and derive a variant that uses stochastic optimization to scale up to massive data. We discuss modern research in VI and highlight important open problems. VI is powerful, but it is not yet well understood. Our hope in writing this paper is to catalyze statistical research on this class of algorithms.

machine-learning
statistics
feature-construction
to-understand
algorithms
6 weeks ago by Vaguery

[1905.10546] Protecting the Protected Group: Circumventing Harmful Fairness

7 weeks ago by Vaguery

Machine Learning (ML) algorithms shape our lives. Banks use them to determine if we are good borrowers; IT companies delegate them recruitment decisions; police apply ML for crime-prediction, and judges base their verdicts on ML. However, real-world examples show that such automated decisions tend to discriminate against protected groups. This potential discrimination generated a huge hype both in media and in the research community. Quite a few formal notions of fairness were proposed, which take a form of constraints a "fair" algorithm must satisfy. We focus on scenarios where fairness is imposed on a self-interested party (e.g., a bank that maximizes its revenue). We find that the disadvantaged protected group can be worse off after imposing a fairness constraint. We introduce a family of \textit{Welfare-Equalizing} fairness constraints that equalize per-capita welfare of protected groups, and include \textit{Demographic Parity} and \textit{Equal Opportunity} as particular cases. In this family, we characterize conditions under which the fairness constraint helps the disadvantaged group. We also characterize the structure of the optimal \textit{Welfare-Equalizing} classifier for the self-interested party, and provide an algorithm to compute it. Overall, our \textit{Welfare-Equalizing} fairness approach provides a unified framework for discussing fairness in classification in the presence of a self-interested party.

fairness
multiobjective-optimization
algorithms
machine-learning
technocracy
rather-interesting
the-mangle-in-practice
to-write-about
consider:not-using-the-same-framework-for-all-your-goals
7 weeks ago by Vaguery

[1905.12536] A Quaternion-based Certifiably Optimal Solution to the Wahba Problem with Outliers

8 weeks ago by Vaguery

The Wahba problem, also known as rotation search, seeks to find the best rotation to align two sets of vector observations given putative correspondences, and is a fundamental routine in many computer vision and robotics applications. This work proposes the first polynomial-time certifiably optimal approach for solving the Wahba problem when a large number of vector observations are outliers. Our first contribution is to formulate the Wahba problem using a Truncated Least Squares (TLS) cost that is insensitive to a large fraction of spurious correspondences. The second contribution is to rewrite the problem using unit quaternions and show that the TLS cost can be framed as a Quadratically-Constrained Quadratic Program (QCQP). Since the resulting optimization is still highly non-convex and hard to solve globally, our third contribution is to develop a convex Semidefinite Programming (SDP) relaxation. We show that while a naive relaxation performs poorly in general, our relaxation is tight even in the presence of large noise and outliers. We validate the proposed algorithm, named QUASAR (QUAternion-based Semidefinite relAxation for Robust alignment), in both synthetic and real datasets showing that the algorithm outperforms RANSAC, robust local optimization techniques, global outlier-removal procedures, and Branch-and-Bound methods. QUASAR is able to compute certifiably optimal solutions (i.e. the relaxation is exact) even in the case when 95% of the correspondences are outliers.

image-processing
optimization
rather-interesting
algorithms
to-write-about
consider:feature-discovery
consider:looking-to-see
consider:representation
8 weeks ago by Vaguery

[1906.07848] Symbolic regression by uniform random global search

8 weeks ago by Vaguery

Symbolic regression (SR) is a data analysis problem where we search for the mathematical expression that best fits a numerical dataset. It is a global optimization problem. The most popular approach to SR is by genetic programming (SRGP). It is a common paradigm to compare an algorithm's performance to that of random search, but the data comparing SRGP to random search is lacking. We describe a novel algorithm for SR, namely SR by uniform random global search (SRURGS), also known as pure random search. We conduct experiments comparing SRURGS with SRGP using 100 randomly generated equations. Our results suggest that a SRGP is faster than SRURGS in producing equations with good R^2 for simple problems. However, our experiments suggest that SRURGS is more robust than SRGP, able to produce good output in more challenging problems. As SRURGS is arguably the simplest global search algorithm, we believe it should serve as a control algorithm against which other symbolic regression algorithms are compared. SRURGS has only one tuning parameter, and is conceptually very simple, making it a useful tool in solving SR problems. The method produces random equations, which is useful for the generation of symbolic regression benchmark problems. We have released well documented and open-source python code, currently under formal peer-review, so that interested researchers can deploy the tool in practice.

genetic-programming
symbolic-regression
machine-learning
algorithms
guessing
to-write-about
8 weeks ago by Vaguery

A Geometric Proof of Brooks’s Trisection? – David Richeson: Division by Zero

8 weeks ago by Vaguery

For instance, I made this applet showing how to use the “cycloid of Ceva” to trisect an angle. (It is based on Archimedes’s neusis [marked straightedge] construction.)

geometry
plane-geometry
impossible-problems
define-your-terms
rather-interesting
algorithms
to-write-about
consider:genetic-programming
consider:rediscovery
consider:inverse-problem
consider:evolve-the-tool
8 weeks ago by Vaguery

[1811.05031] A Review of automatic differentiation and its efficient implementation

november 2019 by Vaguery

Derivatives play a critical role in computational statistics, examples being Bayesian inference using Hamiltonian Monte Carlo sampling and the training of neural networks. Automatic differentiation is a powerful tool to automate the calculation of derivatives and is preferable to more traditional methods, especially when differentiating complex algorithms and mathematical functions. The implementation of automatic differentiation however requires some care to insure efficiency. Modern differentiation packages deploy a broad range of computational techniques to improve applicability, run time, and memory management. Among these techniques are operation overloading, region based memory, and expression templates. There also exist several mathematical techniques which can yield high performance gains when applied to complex algorithms. For example, semi-analytical derivatives can reduce by orders of magnitude the runtime required to numerically solve and differentiate an algebraic equation. Open problems include the extension of current packages to provide more specialized routines, and efficient methods to perform higher-order differentiation.

algorithms
numerical-methods
machine-learning
automatic-differentiation
gradient-methods
to-understand
review
november 2019 by Vaguery

[1906.05637] Invariant Off-Diagonality: SICs as Equicoherent Quantum States

november 2019 by Vaguery

Coherence, treated as a resource in quantum information theory, is a basis-dependent quantity. Looking for states that have constant coherence under canonical changes of basis yields highly symmetric structures in state space. For the case of a qubit, we find an easy construction of qubit SICs (Symmetric Informationally Complete POVMs). SICs in dimension 3 and 8 are also shown to be equicoherent.

quantums
representation
rather-interesting
adjacent-possible
(sorry)
quantum-computing
matrices
algorithms
to-simulate
november 2019 by Vaguery

[1709.07715] Core-biased random walks in complex networks

november 2019 by Vaguery

A simple strategy to explore a network is to use a random-walk where the walker jumps from one node to an adjacent node at random. It is known that biasing the random jump, the walker can explore every walk of the same length with equal probability, this is known as a Maximal Entropy Random Walk (MERW). To construct a MERW requires the knowledge of the largest eigenvalue and corresponding eigenvector of the adjacency matrix, this requires global knowledge of the network. When this global information is not available, it is possible to construct a biased random walk which approximates the MERW using only the degree of the nodes, a local property. Here we show that it is also possible to construct a good approximation to a MERW by biasing the random walk via the properties of the network's core, which is a mesoscale property of the network. We present some examples showing that the core-biased random walk outperforms the degree-biased random walks.

network-theory
probability-theory
algorithms
rather-interesting
approximation
consider:feature-discovery
consider:performance-measures
november 2019 by Vaguery

[1802.00296] $S$-Leaping: An adaptive, accelerated stochastic simulation algorithm, bridging $τ$-leaping and $R$-leaping

november 2019 by Vaguery

We propose the S-leaping algorithm for the acceleration of Gillespie's stochastic simulation algorithm that combines the advantages of the two main accelerated methods; the τ-leaping and R-leaping algorithms. These algorithms are known to be efficient under different conditions; the τ-leaping is efficient for non-stiff systems or systems with partial equilibrium, while the R-leaping performs better in stiff system thanks to an efficient sampling procedure. However, even a small change in a system's set up can critically affect the nature of the simulated system and thus reduce the efficiency of an accelerated algorithm. The proposed algorithm combines the efficient time step selection from the τ-leaping with the effective sampling procedure from the R-leaping algorithm. The S-leaping is shown to maintain its efficiency under different conditions and in the case of large and stiff systems or systems with fast dynamics, the S-leaping outperforms both methods. We demonstrate the performance and the accuracy of the S-leaping in comparison with the τ-leaping and R-leaping on a number of benchmark systems involving biological reaction networks.

simulation
numerical-methods
Markov-models
Monte-Carlo-models
probability-theory
algorithms
horse-races
rather-interesting
to-write-about
performance-measure
approximation
november 2019 by Vaguery

[1803.08202] Person Following by Autonomous Robots: A Categorical Overview

november 2019 by Vaguery

A wide range of human-robot collaborative applications in diverse domains such as manufacturing, health care, the entertainment industry, and social interactions, require an autonomous robot to follow its human companion. Different working environments and applications pose diverse challenges by adding constraints on the choice of sensors, the degree of autonomy, and dynamics of a person-following robot. Researchers have addressed these challenges in many ways and contributed to the development of a large body of literature. This paper provides a comprehensive overview of the literature by categorizing different aspects of person-following by autonomous robots. Also, the corresponding operational challenges are identified based on various design choices for ground, underwater, and aerial scenarios. In addition, state-of-the-art methods for perception, planning, control, and interaction are elaborately discussed and their applicability in varied operational scenarios are presented. Then, some of the prominent methods are qualitatively compared, corresponding practicalities are illustrated, and their feasibility is analyzed for various use-cases. Furthermore, several prospective application areas are identified, and open problems are highlighted for future research.

robotics
review
rather-interesting
goal-balancing
planning
algorithms
experiment
looking-to-see
machine-learning
adaptive-control
adaptive-behavior
to-write-about
image-processing
november 2019 by Vaguery

[1804.02098] The evolution of the structure of ABC-minimal trees

october 2019 by Vaguery

The atom-bond connectivity (ABC) index is a degree-based molecular descriptor that found diverse chemical applications. Characterizing trees with minimum ABC-index remained an elusive open problem even after serious attempts and is considered by some as one of the most intriguing open problems in mathematical chemistry. In this paper, we describe the exact structure of the extremal trees with sufficiently many vertices and we show how their structure evolves when the number of vertices grows. An interesting fact is that their radius is at most~5 and that all vertices except for one have degree at most 54. In fact, all but at most O(1) vertices have degree 1, 2, 4, or 53. Let $\gamma_n = \min\{\abc(T) : T \text{ is a tree of order } n\}$. It is shown that γn=1365153‾‾‾√(1+2655‾‾‾√+156106‾‾‾‾√)n+O(1)≈0.67737178n+O(1).

theoretical-chemistry
graph-theory
algorithms
combinatorics
computational-complexity
rather-interesting
to-understand
feature-construction
to-write-about
to-simulate
october 2019 by Vaguery

[1401.6387] Squaring the square with integer linear programming

october 2019 by Vaguery

We consider so-called squaring the square-puzzles where a given square (or rectangle) should be dissected into smaller squares. For a specific instance of such problems we demonstrate that a mathematically rigorous solution can be quite involved. As an alternative to exhaustive enumeration using tailored algorithms we describe the general approach of formulating the problem as an integer linear program.

dissection-problems
mathematical-recreations
combinatorics
optimization
rather-interesting
have-seen-recently
nudge-targets
algorithms
consider:rediscovery
october 2019 by Vaguery

[1602.04181] Spectral Alignment of Graphs

september 2019 by Vaguery

Graph alignment refers to the problem of finding a bijective mapping across vertices of two graphs such that, if two nodes are connected in the first graph, their images are connected in the second graph. This problem arises in many fields such as computational biology, social sciences, and computer vision and is often cast as a quadratic assignment problem (QAP). Most standard graph alignment methods consider an optimization that maximizes the number of matches between the two graphs, ignoring the effect of mismatches. We propose a generalized graph alignment formulation that considers both matches and mismatches in a standard QAP formulation. This modification can have a major impact in aligning graphs with different sizes and heterogenous edge densities. Moreover, we propose two methods for solving the generalized graph alignment problem based on spectral decomposition of matrices. We compare the performance of proposed methods with some existing graph alignment algorithms including Natalie2, GHOST, IsoRank, NetAlign, Klau's approach as well as a semidefinite programming-based method over various synthetic and real graph models. Our proposed method based on simultaneous alignment of multiple eigenvectors leads to consistently good performance in different graph models. In particular, in the alignment of regular graph structures which is one of the most difficult graph alignment cases, our proposed method significantly outperforms other methods.

graph-theory
similarity-measures
clustering
distance
numerical-methods
algorithms
performance-measure
rather-interesting
consider:looking-to-see
consider:robustness
to-simulate
september 2019 by Vaguery

[1909.10140] A new coefficient of correlation

september 2019 by Vaguery

Is it possible to define a coefficient of correlation which is (a) as simple as the classical coefficients like Pearson's correlation or Spearman's correlation, and yet (b) consistently estimates some simple and interpretable measure of the degree of dependence between the variables, which is 0 if and only if the variables are independent and 1 if and only if one is a measurable function of the other, and (c) has a simple asymptotic theory under the hypothesis of independence, like the classical coefficients? This article answers this question in the affirmative, by producing such a coefficient. No assumptions are needed on the distributions of the variables. There are several coefficients in the literature that converge to 0 if and only if the variables are independent, but none that satisfy any of the other properties mentioned above.

statistics
algorithms
rather-interesting
engineering-design
performance-measure
define-your-terms
to-simulate
to-write-about
consider:rediscovery
september 2019 by Vaguery

[1808.05740] Extremality, Stationarity and Generalized Separation of Collections of Sets

september 2019 by Vaguery

The core arguments used in various proofs of the extremal principle and its extensions as well as in primal and dual characterizations of approximate stationarity and transversality of collections of sets are exposed, analyzed and refined, leading to a unifying theory, encompassing all existing approaches to obtaining 'extremal' statements. For that, we examine and clarify quantitative relationships between the parameters involved in the respective definitions and statements. Some new characterizations of extremality properties are obtained.

statistics
clustering
extreme-values
to-understand
discrimination
algorithms
rather-odd
rather-general-sounding
optimization
probability-theory
consider:weird-GP-stuff
september 2019 by Vaguery

[PDF] A brief review of image denoising algorithms and beyond

september 2019 by Vaguery

The recent advances in hardware and imaging systems made the digital cameras ubiquitous. Although the development of hardware has steadily improved the quality of images for the last several decades, image degradation is unavoidable due to the many factors affecting the image acquisition process and the subsequent post- processing. Image denoising, which aims to reconstruct a high quality image from its degraded observation, is a classical yet still very active topic in the area of low- level computer vision. It represents an important building block in real applications such as digital photography, medical image analysis, remote sensing, surveillance and digital entertainment. Also, image denoising constitutes an ideal test bed for evaluating image prior modeling methods. In this paper, we briefly review recent progresses in image denoising. We firstly present an overview of prior modeling approaches used in image denoising task. Then, we review conventional sparse representation based denoising algorithms, low-rank based denoising algorithms and recently proposed deep neural networks based approaches. At last, we discuss some emerging topics and open problems about image denoising.

image-processing
numerical-methods
approximation
rather-interesting
algorithms
machine-learning
to-write-about
to-simulate
september 2019 by Vaguery

The Connect-The-Dots family of puzzles

september 2019 by Vaguery

In this paper we introduce several innovative variants on the classic Connect-The-Dots puzzle. We study the underlying geometric principles and investigate methods for the automatic generation of high-quality puzzles from line drawings.

Specifically, we introduce three new variants of the classic Connect-The-Dots puzzle. These new variants use different rules for drawing connections, and have several advantages: no need for printed numbers in the puzzle (which look ugly in the final drawing), and perhaps more challenging "game play", making the puzzles suitable for different age groups. We study the rules of all four variants in the family, and design principles describing what makes a good puzzle. We identify general principles that apply across the different variants, as well as specific implementations of those principles in the different variants. We make these mathematically precise in the form of criteria a puzzle should satisfy.

Furthermore, we investigate methods for the automatic generation of puzzles from a plane graph that describes the input drawing. We show that the problem of generating a good puzzle --one satisfying the mentioned criteria-- is computationally hard, and present several heuristic algorithms.

Using our implementation for generating puzzles, we evaluate the quality of the resulting puzzles with respect to two parameters: one for similarity to the original line drawing, and one for ambiguity; i.e. what is the visual accuracy needed to solve the puzzle.

image-processing
feature-construction
algorithms
rather-interesting
optimization
performance-measure
consider:looking-to-see
consider:representation
Specifically, we introduce three new variants of the classic Connect-The-Dots puzzle. These new variants use different rules for drawing connections, and have several advantages: no need for printed numbers in the puzzle (which look ugly in the final drawing), and perhaps more challenging "game play", making the puzzles suitable for different age groups. We study the rules of all four variants in the family, and design principles describing what makes a good puzzle. We identify general principles that apply across the different variants, as well as specific implementations of those principles in the different variants. We make these mathematically precise in the form of criteria a puzzle should satisfy.

Furthermore, we investigate methods for the automatic generation of puzzles from a plane graph that describes the input drawing. We show that the problem of generating a good puzzle --one satisfying the mentioned criteria-- is computationally hard, and present several heuristic algorithms.

Using our implementation for generating puzzles, we evaluate the quality of the resulting puzzles with respect to two parameters: one for similarity to the original line drawing, and one for ambiguity; i.e. what is the visual accuracy needed to solve the puzzle.

september 2019 by Vaguery

[1401.4375] Fast regocnition of planar non unit distance graphs

september 2019 by Vaguery

We study criteria attesting that a given graph can not be embedded in the plane so that neighboring vertices are at unit distance apart and the straight line edges do not cross.

graph-theory
matchstick-graphs
rather-interesting
algorithms
heuristics
computational-complexity
to-understand
to-write-about
to-simulate
september 2019 by Vaguery

[1706.04939] Online Strip Packing with Polynomial Migration

september 2019 by Vaguery

We consider the relaxed online strip packing problem: Rectangular items arrive online and have to be packed without rotations into a strip of fixed width such that the packing height is minimized. Thereby, repacking of previously packed items is allowed. The amount of repacking is measured by the migration factor, defined as the total size of repacked items divided by the size of the arriving item. First, we show that no algorithm with constant migration factor can produce solutions with asymptotic ratio better than 4/3. Against this background, we allow amortized migration, i.e. to save migration for a later time step. As a main result, we present an AFPTAS with asymptotic ratio 1+(ϵ) for any ϵ>0 and amortized migration factor polynomial in 1/ϵ. To our best knowledge, this is the first algorithm for online strip packing considered in a repacking model.

operations-research
bin-packing
strip-packing
optimization
algorithms
heuristics
to-simulate
to-write-about
horse-races
computational-complexity
consider:genetic-programming
september 2019 by Vaguery

[1701.07396] LAREX - A semi-automatic open-source Tool for Layout Analysis and Region Extraction on Early Printed Books

september 2019 by Vaguery

A semi-automatic open-source tool for layout analysis on early printed books is presented. LAREX uses a rule based connected components approach which is very fast, easily comprehensible for the user and allows an intuitive manual correction if necessary. The PageXML format is used to support integration into existing OCR workflows. Evaluations showed that LAREX provides an efficient and flexible way to segment pages of early printed books.

OCR
digitization
machine-learning
algorithms
image-processing
image-segmentation
digital-humanities
to-understand
to-write-about
to-simulate
september 2019 by Vaguery

[math/0111080] Phase retrieval by iterated projections

september 2019 by Vaguery

Several strategies in phase retrieval are unified by an iterative "difference map" constructed from a pair of elementary projections and a single real parameter β. For the standard application in optics, where the two projections implement Fourier modulus and object support constraints respectively, the difference map reproduces the "hybrid" form of Fienup's input-output map for β=1. Other values of β are equally effective in retrieving phases but have no input-output counterparts. The geometric construction of the difference map illuminates the distinction between its fixed points and the recovered object, as well as the mechanism whereby stagnation is avoided. When support constraints are replaced by object histogram or atomicity constraints, the difference map lends itself to crystallographic phase retrieval. Numerical experiments with synthetic data suggest that structures with hundreds of atoms can be solved.

inverse-problems
mathematical-diffraction
rather-interesting
to-understand
signal-processing
algorithms
to-write-about
to-simulate
consider:genetic-programming
consider:performance-measures
consider:lexicase-for-spectra
september 2019 by Vaguery

[1403.0362] Determining pure discrete spectrum for some self-affine tilings

september 2019 by Vaguery

By the algorithm implemented in the paper [2] by Akiyama-Lee and some of its predecessors, we have examined the pure discreteness of the spectrum for all irreducible Pisot substitutions of trace less than or equal to 2, and some cases of planar tilings generated by boundary substitutions due to the paper [17] by Kenyon.

aperiodic-tiling
feature-construction
plane-geometry
tiling
rather-interesting
spectra
to-understand
to-simulate
algorithms
september 2019 by Vaguery

[1509.02241] The local optimality of the double lattice packing

september 2019 by Vaguery

This paper introduces a technique for proving the local optimality of packing configurations. Applying this technique to a general convex polygon, we prove that the construction of the optimal double lattice packing by Kuperberg and Kuperberg is also locally optimal in the full space of packings.

geometry
proof
techniques
algorithms
packing
plane-geometry
optimization
performance-measure
to-understand
to-write-about
consider:looking-to-see
consider:rediscovery
consider:robustness
september 2019 by Vaguery

[1603.09133] "Compress and eliminate" solver for symmetric positive definite sparse matrices

august 2019 by Vaguery

We propose a new approximate factorization for solving linear systems with symmetric positive definite sparse matrices. In a nutshell the algorithm is to apply hierarchically block Gaussian elimination and additionally compress the fill-in. The systems that have efficient compression of the fill-in mostly arise from discretization of partial differential equations. We show that the resulting factorization can be used as an efficient preconditioner and compare the proposed approach with state-of-art direct and iterative solvers.

numerical-methods
matrices
algorithms
computational-complexity
rather-interesting
to-write-about
consider:performance-measures
consider:feature-discovery
august 2019 by Vaguery

[1907.07795] Efficient computation of the Jacobi symbol

august 2019 by Vaguery

The family of left-to-right GCD algorithms reduces input numbers by repeatedly subtracting the smaller number, or multiple of the smaller number, from the larger number. This paper describes how to extend any such algorithm to compute the Jacobi symbol, using a single table lookup per reduction. For both quadratic time GCD algorithms (Euclid, Lehmer) and subquadratic algorithms (Knuth, Schönhage, Möller), the additional cost is linear, roughly one table lookup per quotient in the quotient sequence. This method was used for the 2010 rewrite of the Jacobi symbol computation in GMP.

number-theory
algorithms
numerical-methods
computational-complexity
rather-interesting
to-write-about
to-generalize
consider:rediscovery
consider:looking-to-see
august 2019 by Vaguery

[1908.07647] Line and Plane Cover Numbers Revisited

august 2019 by Vaguery

A measure for the visual complexity of a straight-line crossing-free drawing of a graph is the minimum number of lines needed to cover all vertices. For a given graph G, the minimum such number (over all drawings in dimension d∈{2,3}) is called the \emph{d-dimensional weak line cover number} and denoted by π1d(G). In 3D, the minimum number of \emph{planes} needed to cover all vertices of~G is denoted by π23(G). When edges are also required to be covered, the corresponding numbers ρ1d(G) and ρ23(G) are called the \emph{(strong) line cover number} and the \emph{(strong) plane cover number}.

Computing any of these cover numbers -- except π12(G) -- is known to be NP-hard. The complexity of computing π12(G) was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph~G, whether π12(G)=2. We further show that the universal stacked triangulation of depth~d, Gd, has π12(Gd)=d+1. Concerning~3D, we show that any n-vertex graph~G with ρ23(G)=2 has at most 5n−19 edges, which is tight.

graph-layout
optimization
algorithms
computational-complexity
computational-geometry
rather-interesting
to-simulate
feature-construction
Computing any of these cover numbers -- except π12(G) -- is known to be NP-hard. The complexity of computing π12(G) was posed as an open problem by Chaplick et al. [WADS 2017]. We show that it is NP-hard to decide, for a given planar graph~G, whether π12(G)=2. We further show that the universal stacked triangulation of depth~d, Gd, has π12(Gd)=d+1. Concerning~3D, we show that any n-vertex graph~G with ρ23(G)=2 has at most 5n−19 edges, which is tight.

august 2019 by Vaguery

[1606.09597] $π$-formulas and Gray code

august 2019 by Vaguery

In previous papers we introduced a class of polynomials which follow the same recursive formula as the Lucas-Lehmer numbers, studying the distribution of their zeros and remarking that this distribution follows a sequence related to the binary Gray code. It allowed us to give an order for all the zeros of every polynomial Ln. In this paper, the zeros, expressed in terms of nested radicals, are used to obtain two formulas for π: the first can be seen as a generalization of the known formula

π=limn→∞2n+1⋅2−2+2+2+...+2‾√‾‾‾‾‾‾‾‾‾‾√‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾√‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾√n‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾⎷ ,

related to the smallest positive zero of Ln; the second is an exact formula for π achieved thanks to some identities valid for Ln.

numerical-methods
approximation
continued-fractions
(sorta)
number-theory
algorithms
to-simulate
to-write-about
consider:genetic-programming
π=limn→∞2n+1⋅2−2+2+2+...+2‾√‾‾‾‾‾‾‾‾‾‾√‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾√‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾√n‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾⎷ ,

related to the smallest positive zero of Ln; the second is an exact formula for π achieved thanks to some identities valid for Ln.

august 2019 by Vaguery

[1705.06314] Tire tracks and integrable curve evolution

august 2019 by Vaguery

We study a simple model of bicycle motion: a segment of fixed length in multi-dimensional Euclidean space, moving so that the velocity of the rear end is always aligned with the segment. If the front track is prescribed, the trajectory of the rear wheel is uniquely determined via a certain first order differential equation -- the bicycle equation. The same model, in dimension two, describes another mechanical device, the hatchet planimeter.

Here is a sampler of our results. We express the linearized flow of the bicycle equation in terms of the geometry of the rear track; in dimension three, for closed front and rear tracks, this is a version of the Berry phase formula. We show that in all dimensions a sufficiently long bicycle also serves as a planimeter: it measures, approximately, the area bivector defined by the closed front track. We prove that the bicycle equation also describes rolling, without slipping and twisting, of hyperbolic space along Euclidean space. We relate the bicycle problem with two completely integrable systems: the AKNS (Ablowitz, Kaup, Newell and Segur) system and the vortex filament equation. We show that "bicycle correspondence" of space curves (front tracks sharing a common back track) is a special case of a Darboux transformation associated with the AKNS system. We show that the filament hierarchy, encoded as a single generating equation, describes a 3-dimensional bike of imaginary length. We show that a series of examples of "ambiguous" closed bicycle curves (front tracks admitting self bicycle correspondence), found recently F. Wegner, are buckled rings, or solitons of the planar filament equation. As a case study, we give a detailed analysis of such curves, arising from bicycle correspondence with multiply traversed circles.

plane-geometry
rather-interesting
topology
constraint-satisfaction
dynamical-systems
algorithms
consider:looking-to-see
to-simulate
to-write-about
consider:rediscovery
nudge-targets
Here is a sampler of our results. We express the linearized flow of the bicycle equation in terms of the geometry of the rear track; in dimension three, for closed front and rear tracks, this is a version of the Berry phase formula. We show that in all dimensions a sufficiently long bicycle also serves as a planimeter: it measures, approximately, the area bivector defined by the closed front track. We prove that the bicycle equation also describes rolling, without slipping and twisting, of hyperbolic space along Euclidean space. We relate the bicycle problem with two completely integrable systems: the AKNS (Ablowitz, Kaup, Newell and Segur) system and the vortex filament equation. We show that "bicycle correspondence" of space curves (front tracks sharing a common back track) is a special case of a Darboux transformation associated with the AKNS system. We show that the filament hierarchy, encoded as a single generating equation, describes a 3-dimensional bike of imaginary length. We show that a series of examples of "ambiguous" closed bicycle curves (front tracks admitting self bicycle correspondence), found recently F. Wegner, are buckled rings, or solitons of the planar filament equation. As a case study, we give a detailed analysis of such curves, arising from bicycle correspondence with multiply traversed circles.

august 2019 by Vaguery

[1609.04106] The Inverse Gamma Distribution and Benford's Law

august 2019 by Vaguery

According to Benford's Law, many data sets have a bias towards lower leading digits (about 30% are 1's). The applications of Benford's Law vary: from detecting tax, voter and image fraud to determining the possibility of match-fixing in competitive sports. There are many common distributions that exhibit such bias, i.e. they are almost Benford. These include the exponential and the Weibull distributions. Motivated by these examples and the fact that the underlying distribution of factors in protein structure follows an inverse gamma distribution, we determine the closeness of this distribution to a Benford distribution as its parameters change.

probability-theory
Benford's-law
counterintuitive-stuff
algorithms
rather-interesting
to-write-about
to-simulate
consider:rediscovery
august 2019 by Vaguery

[1801.06620] A high-performance analog Max-SAT solver and its application to Ramsey numbers

august 2019 by Vaguery

We introduce a continuous-time analog solver for MaxSAT, a quintessential class of NP-hard discrete optimization problems, where the task is to find a truth assignment for a set of Boolean variables satisfying the maximum number of given logical constraints. We show that the scaling of an invariant of the solver's dynamics, the escape rate, as function of the number of unsatisfied clauses can predict the global optimum value, often well before reaching the corresponding state. We demonstrate the performance of the solver on hard MaxSAT competition problems. We then consider the two-color Ramsey number R(m,m) problem, translate it to SAT, and apply our algorithm to the still unknown R(5,5). We find edge colorings without monochromatic 5-cliques for complete graphs up to 42 vertices, while on 43 vertices we find colorings with only two monochromatic 5-cliques, the best coloring found so far, supporting the conjecture that R(5,5)=43.

computational-complexity
analog-computing
algorithms
rather-interesting
to-write-about
satisfiability
optimization
combinatorics
august 2019 by Vaguery

[1810.08237] Large-scale Hierarchical Alignment for Data-driven Text Rewriting

august 2019 by Vaguery

We propose a simple unsupervised method for extracting pseudo-parallel monolingual sentence pairs from comparable corpora representative of two different text styles, such as news articles and scientific papers. Our approach does not require a seed parallel corpus, but instead relies solely on hierarchical search over pre-trained embeddings of documents and sentences. We demonstrate the effectiveness of our method through automatic and extrinsic evaluation on text simplification from the normal to the Simple Wikipedia. We show that pseudo-parallel sentences extracted with our method not only supplement existing parallel data, but can even lead to competitive performance on their own.

natural-language-processing
text-mining
translation
rather-interesting
algorithms
representation
machine-learning
clustering
unsupervised-learning
to-understand
august 2019 by Vaguery

[1811.03254] Optimal Parallelism Bound for Fully Asynchronous Coordinate Descent with Linear Speedup

august 2019 by Vaguery

When solving massive optimization problems in areas such as machine learning, it is a common practice to seek speedup via massive parallelism. However, especially in an asynchronous environment, there are limits on the possible parallelism. Accordingly, we seek tight bounds on the viable parallelism in asynchronous implementations of coordinate descent.

We focus on asynchronous coordinate descent (ACD) algorithms on convex functions F:ℝn→ℝ of the form

F(x)=f(x) + ∑k=1nΨk(xk),

where f:ℝn→ℝ is a smooth convex function, and each Ψk:ℝ→ℝ is a univariate and possibly non-smooth convex function.

Our approach is to quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a truly simple yet optimal analysis of the standard stochastic ACD in a partially asynchronous environment, which already generalizes and improves on the bounds in prior work. We also give a considerably more involved analysis for general asynchronous environments in which the only constraint is that each update can overlap with at most q others, where q is at most the number of processors times the ratio in the lengths of the longest and shortest updates. The main technical challenge is to demonstrate linear speedup in the latter environment. This stems from the subtle interplay of asynchrony and randomization. This improves Liu and Wright's (SIOPT'15) lower bound on the maximum degree of parallelism almost quadratically; the new bound is essentially optimal.

optimization
gradient-descent
algorithms
computational-complexity
asynchronous-computing
rather-interesting
to-understand
to-simulate
to-write-about
numerical-methods
We focus on asynchronous coordinate descent (ACD) algorithms on convex functions F:ℝn→ℝ of the form

F(x)=f(x) + ∑k=1nΨk(xk),

where f:ℝn→ℝ is a smooth convex function, and each Ψk:ℝ→ℝ is a univariate and possibly non-smooth convex function.

Our approach is to quantify the shortfall in progress compared to the standard sequential stochastic gradient descent. This leads to a truly simple yet optimal analysis of the standard stochastic ACD in a partially asynchronous environment, which already generalizes and improves on the bounds in prior work. We also give a considerably more involved analysis for general asynchronous environments in which the only constraint is that each update can overlap with at most q others, where q is at most the number of processors times the ratio in the lengths of the longest and shortest updates. The main technical challenge is to demonstrate linear speedup in the latter environment. This stems from the subtle interplay of asynchrony and randomization. This improves Liu and Wright's (SIOPT'15) lower bound on the maximum degree of parallelism almost quadratically; the new bound is essentially optimal.

august 2019 by Vaguery

[1807.01672] Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization

august 2019 by Vaguery

Adversarial self-play in two-player games has delivered impressive results when used with reinforcement learning algorithms that combine deep neural networks and tree search. Algorithms like AlphaZero and Expert Iteration learn tabula-rasa, producing highly informative training data on the fly. However, the self-play training strategy is not directly applicable to single-player games. Recently, several practically important combinatorial optimisation problems, such as the travelling salesman problem and the bin packing problem, have been reformulated as reinforcement learning problems, increasing the importance of enabling the benefits of self-play beyond two-player games. We present the Ranked Reward (R2) algorithm which accomplishes this by ranking the rewards obtained by a single agent over multiple games to create a relative performance metric. Results from applying the R2 algorithm to instances of a two-dimensional and three-dimensional bin packing problems show that it outperforms generic Monte Carlo tree search, heuristic algorithms and integer programming solvers. We also present an analysis of the ranked reward mechanism, in particular, the effects of problem instances with varying difficulty and different ranking thresholds.

machine-learning
reinforcement-learning
algorithms
self-play
mechanism-design
optimization
performance-measure
to-understand
operations-research
metaheuristics
august 2019 by Vaguery

[1412.8615] On Randomized Algorithms for Matching in the Online Preemptive Model

august 2019 by Vaguery

We investigate the power of randomized algorithms for the maximum cardinality matching (MCM) and the maximum weight matching (MWM) problems in the online preemptive model. In this model, the edges of a graph are revealed one by one and the algorithm is required to always maintain a valid matching. On seeing an edge, the algorithm has to either accept or reject the edge. If accepted, then the adjacent edges are discarded. The complexity of the problem is settled for deterministic algorithms.

Almost nothing is known for randomized algorithms. A lower bound of 1.693 is known for MCM with a trivial upper bound of 2. An upper bound of 5.356 is known for MWM. We initiate a systematic study of the same in this paper with an aim to isolate and understand the difficulty. We begin with a primal-dual analysis of the deterministic algorithm due to McGregor. All deterministic lower bounds are on instances which are trees at every step. For this class of (unweighted) graphs we present a randomized algorithm which is 2815-competitive. The analysis is a considerable extension of the (simple) primal-dual analysis for the deterministic case. The key new technique is that the distribution of primal charge to dual variables depends on the "neighborhood" and needs to be done after having seen the entire input. The assignment is asymmetric: in that edges may assign different charges to the two end-points. Also the proof depends on a non-trivial structural statement on the performance of the algorithm on the input tree.

The other main result of this paper is an extension of the deterministic lower bound of Varadaraja to a natural class of randomized algorithms which decide whether to accept a new edge or not using independent random choices.

algorithms
online-algorithms
dynamic-programming
machine-learning
graph-theory
to-understand
mechanism-design
to-write-about
something-in-it
Almost nothing is known for randomized algorithms. A lower bound of 1.693 is known for MCM with a trivial upper bound of 2. An upper bound of 5.356 is known for MWM. We initiate a systematic study of the same in this paper with an aim to isolate and understand the difficulty. We begin with a primal-dual analysis of the deterministic algorithm due to McGregor. All deterministic lower bounds are on instances which are trees at every step. For this class of (unweighted) graphs we present a randomized algorithm which is 2815-competitive. The analysis is a considerable extension of the (simple) primal-dual analysis for the deterministic case. The key new technique is that the distribution of primal charge to dual variables depends on the "neighborhood" and needs to be done after having seen the entire input. The assignment is asymmetric: in that edges may assign different charges to the two end-points. Also the proof depends on a non-trivial structural statement on the performance of the algorithm on the input tree.

The other main result of this paper is an extension of the deterministic lower bound of Varadaraja to a natural class of randomized algorithms which decide whether to accept a new edge or not using independent random choices.

august 2019 by Vaguery

[1801.03462] Online Maximum Matching with Recourse

august 2019 by Vaguery

We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter k. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most k such actions per edge take place, where k is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. [AMP13], whereas the special case k=2 was studied by Boyar et al. [BFKL17].

In the first part of this paper, we consider the {\em edge arrival} model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP given in [AMP13], by exploiting the structure of the matching problem. In addition, we extend the result of [BFKL17] and show that the greedy algorithm has competitive ratio 3/2 for every even k and ratio 2 for every odd k. Moreover, we present and analyze an improvement of the greedy algorithm which we call L-Greedy, and we show that for small values of k it outperforms the algorithm of [AMP13]. In terms of lower bounds, we show that no deterministic algorithm better than 1+1/(k−1) exists, improving upon the lower bound of 1+1/k shown in [AMP13].

The second part of the paper is devoted to the \emph{edge arrival/departure model}, which is the fully dynamic variant of online matching with recourse. The analysis of L-Greedy and AMP carry through in this model; moreover we show a lower bound of k2−3k+6k2−4k+7 for all even k≥4. For k∈{2,3}, the competitive ratio is 3/2.

online-algorithms
online-learning
rather-interesting
incremental-algorithms
decision-making
algorithms
machine-learning
combinatorics
to-understand
to-follow-downstream
to-write-about
ReQ
consider:backtracking
consider:performance-measures
In the first part of this paper, we consider the {\em edge arrival} model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP given in [AMP13], by exploiting the structure of the matching problem. In addition, we extend the result of [BFKL17] and show that the greedy algorithm has competitive ratio 3/2 for every even k and ratio 2 for every odd k. Moreover, we present and analyze an improvement of the greedy algorithm which we call L-Greedy, and we show that for small values of k it outperforms the algorithm of [AMP13]. In terms of lower bounds, we show that no deterministic algorithm better than 1+1/(k−1) exists, improving upon the lower bound of 1+1/k shown in [AMP13].

The second part of the paper is devoted to the \emph{edge arrival/departure model}, which is the fully dynamic variant of online matching with recourse. The analysis of L-Greedy and AMP carry through in this model; moreover we show a lower bound of k2−3k+6k2−4k+7 for all even k≥4. For k∈{2,3}, the competitive ratio is 3/2.

august 2019 by Vaguery

[1608.02153] OCR of historical printings with an application to building diachronic corpora: A case study using the RIDGES herbal corpus

august 2019 by Vaguery

This article describes the results of a case study that applies Neural Network-based Optical Character Recognition (OCR) to scanned images of books printed between 1487 and 1870 by training the OCR engine OCRopus [@breuel2013high] on the RIDGES herbal text corpus [@OdebrechtEtAlSubmitted]. Training specific OCR models was possible because the necessary *ground truth* is available as error-corrected diplomatic transcriptions. The OCR results have been evaluated for accuracy against the ground truth of unseen test sets. Character and word accuracies (percentage of correctly recognized items) for the resulting machine-readable texts of individual documents range from 94% to more than 99% (character level) and from 76% to 97% (word level). This includes the earliest printed books, which were thought to be inaccessible by OCR methods until recently. Furthermore, OCR models trained on one part of the corpus consisting of books with different printing dates and different typesets *(mixed models)* have been tested for their predictive power on the books from the other part containing yet other fonts, mostly yielding character accuracies well above 90%. It therefore seems possible to construct generalized models trained on a range of fonts that can be applied to a wide variety of historical printings still giving good results. A moderate postcorrection effort of some pages will then enable the training of individual models with even better accuracies. Using this method, diachronic corpora including early printings can be constructed much faster and cheaper than by manual transcription. The OCR methods reported here open up the possibility of transforming our printed textual cultural heritage into electronic text by largely automatic means, which is a prerequisite for the mass conversion of scanned books.

OCR
image-processing
natural-language-processing
algorithms
machine-learning
rather-interesting
commodity-software
digital-humanities
to-write-about
consider:swarms
consider:stochastic-resonance
august 2019 by Vaguery

[1812.11224] Planar maps, random walks and circle packing

august 2019 by Vaguery

These are lecture notes of the 48th Saint-Flour summer school, July 2018, on the topic of planar maps, random walks and the circle packing theorem.

packing
graph-theory
plane-geometry
representation
algorithms
combinatorics
review
to-read
dynamical-systems
august 2019 by Vaguery

[1807.01132] The power of thinning in balanced allocation

august 2019 by Vaguery

Balls are sequentially allocated into n bins as follows: for each ball, an independent, uniformly random bin is generated. An overseer may then choose to either allocate the ball to this bin, or else the ball is allocated to a new independent uniformly random bin. The goal of the overseer is to reduce the load of the most heavily loaded bin after Θ(n) balls have been allocated. We provide an asymptotically optimal strategy yielding a maximum load of (1+o(1))8lognloglogn‾‾‾‾‾‾‾√ balls.

queueing-theory
operations-research
optimization
online-algorithms
algorithms
branching-processes
probability-theory
to-simulate
to-write-about
consider:genetic-programming
august 2019 by Vaguery

[1812.07933] Dynamic Programming Approach to Template-based OCR

august 2019 by Vaguery

In this paper we propose a dynamic programming solution to the template-based recognition task in OCR case. We formulate a problem of optimal position search for complex objects consisting of parts forming a sequence. We limit the distance between every two adjacent elements with predefined upper and lower thresholds. We choose the sum of penalties for each part in given position as a function to be minimized. We show that such a choice of restrictions allows a faster algorithm to be used than the one for the general form of deformation penalties. We named this algorithm Dynamic Squeezeboxes Packing (DSP) and applied it to solve the two OCR problems: text fields extraction from an image of document Visual Inspection Zone (VIZ) and license plate segmentation. The quality and the performance of resulting solutions were experimentally proved to meet the requirements of the state-of-the-art industrial recognition systems.

OCR
image-segmentation
image-processing
algorithms
optimization
mathematical-programming
to-write-about
to-compare
august 2019 by Vaguery

[1004.3025] Outer Billiards and the Pinwheel Map

august 2019 by Vaguery

In this paper we establish a kind of bijection between the orbits of a polygonal outer billiards system and the orbits of a related (and simpler to analyze) system called the pinwheel map. One consequence of the result is that the outer billiards system has unbounded orbits if and only if the pinwheel map has unbounded orbits. As the pinwheel map is much easier to analyze directly, we think that this bijection will be helpful in attacking some of the main questions about polyonal outer billiards.

plane-geometry
construction
dynamical-systems
algorithms
iterated-systems
to-write-about
to-simulate
august 2019 by Vaguery

[1410.5115] Remarks on the the circumcenter of mass

august 2019 by Vaguery

Suppose that to every non-degenerate simplex Delta in n-dimensional Euclidean space a `center' C(Delta) is assigned so that the following assumptions hold: (i) The map that assigns C(Delta) to Delta commutes with similarities and is invariant under the permutations of the vertices of the simplex; (ii) The map that assigns Vol(Delta) C(Delta) to Delta is polynomial in the coordinates of the vertices of the simplex. Then C(Delta) is an affine combination of the center of mass and the circumcenter of Delta (with the coefficients independent of the simplex). The motivation for this theorem comes from the recent study of the circumcenter of mass of simplicial polytopes by the authors and by A. Akopyan.

plane-geometry
construction
algorithms
feature-construction
statistics
nudge-targets
consider:looking-to-see
august 2019 by Vaguery

[1802.07481] Celer: a Fast Solver for the Lasso with Dual Extrapolation

july 2019 by Vaguery

Convex sparsity-inducing regularizations are ubiquitous in high-dimensional machine learning, but solving the resulting optimization problems can be slow. To accelerate solvers, state-of-the-art approaches consist in reducing the size of the optimization problem at hand. In the context of regression, this can be achieved either by discarding irrelevant features (screening techniques) or by prioritizing features likely to be included in the support of the solution (working set techniques). Duality comes into play at several steps in these techniques. Here, we propose an extrapolation technique starting from a sequence of iterates in the dual that leads to the construction of improved dual points. This enables a tighter control of optimality as used in stopping criterion, as well as better screening performance of Gap Safe rules. Finally, we propose a working set strategy based on an aggressive use of Gap Safe screening rules. Thanks to our new dual point construction, we show significant computational speedups on multiple real-world problems.

machine-learning
statistics
horse-races
performance-measure
computational-complexity
to-read
algorithms
july 2019 by Vaguery

[1903.08056] On the general position problem on Kneser graphs

july 2019 by Vaguery

In a graph G, a geodesic between two vertices x and y is a shortest path connecting x to y. A subset S of the vertices of G is in general position if no vertex of S lies on any geodesic between two other vertices of S. The size of a largest set of vertices in general position is the general position number that we denote by gp(G). Recently, Ghorbani et al, proved that for any k if n≥k3−k2+2k−2, then gp(Knn,k)=(n−1k−1), where Knn,k denotes the Kneser graph. We improve on their result and show that the same conclusion holds for n≥2k+2 and this bound is best possible. Our main tools are a result on cross-intersecting families and a slight generalization of Bollobás's inequality on intersecting set pair systems.

combinatorics
graph-theory
feature-construction
rather-interesting
algorithms
to-write-about
july 2019 by Vaguery

A global postsynthesis optimization method for combinational circuits - IEEE Conference Publication

june 2019 by Vaguery

A genetic programming-based circuit synthesis method is proposed that enables to globally optimize the number of gates in circuits that have already been synthesized using common methods such as ABC and SIS. The main contribution is a proposal for a new fitness function that enables to significantly reduce the fitness evaluation time in comparison to the state of the art. The fitness function performs optimized equivalence checking using a SAT solver. It is shown that the equivalence checking time can significantly be reduced when knowledge of the parent circuit and its mutated offspring is taken into account. For a cost of a runtime, results of conventional synthesis conducted using SIS and ABC were improved by 20-40% for the LGSynth93 benchmarks.

genetic-programming
Cartesian-GP
boolean-networks
boolean-matching
discrete-mathematics
rather-interesting
algorithms
to-write-about
june 2019 by Vaguery

Copy this bookmark: