Search results for "MathematicsofComputing_DISCRETEMATHEMATICS"
showing 10 items of 123 documents
A GRASP heuristic for the mixed Chinese postman problem
2002
Abstract Arc routing problems (ARPs) consist of finding a traversal on a graph satisfying some conditions related to the links of the graph. In the Chinese postman problem (CPP) the aim is to find a minimum cost tour (closed walk) traversing all the links of the graph at least once. Both the Undirected CPP, where all the links are edges that can be traversed in both ways, and the Directed CPP, where all the links are arcs that must be traversed in a specified way, are known to be polynomially solvable. However, if we deal with a mixed graph (having edges and arcs), the problem turns out to be NP -hard. In this paper, we present a heuristic algorithm for this problem, the so-called Mixed CPP…
Generalized Dimension Distortion under Mappings of Sub-Exponentially Integrable Distortion
2010
We prove a dimension distortion estimate for mappings of sub-exponentially integrable distortion in Euclidean spaces, which is essentially sharp in the plane.
Vertical representation of C∞-words
2015
We present a new framework for dealing with C ∞ -words, based on their left and right frontiers. This allows us to give a compact representation of them, and to describe the set of C ∞ -words through an infinite directed acyclic graph G. This graph is defined by a map acting on the frontiers of C ∞ -words. We show that this map can be defined recursively and with no explicit reference to C ∞ -words. We then show that some important conjectures on C ∞ -words follow from analogous statements on the structure of the graph G.
Steiner systems and configurations of points
2020
AbstractThe aim of this paper is to make a connection between design theory and algebraic geometry/commutative algebra. In particular, given any Steiner SystemS(t, n, v) we associate two ideals, in a suitable polynomial ring, defining a Steiner configuration of points and its Complement. We focus on the latter, studying its homological invariants, such as Hilbert Function and Betti numbers. We also study symbolic and regular powers associated to the ideal defining a Complement of a Steiner configuration of points, finding its Waldschmidt constant, regularity, bounds on its resurgence and asymptotic resurgence. We also compute the parameters of linear codes associated to any Steiner configur…
A fast heuristic for solving the D1EC coloring problem
2010
In this paper we propose an efficient heuristic for solving the Distance-1 Edge Coloring problem (D1EC) for the on-the-fly assignment of orthogonal wireless channels in wireless as soon as a topology change occurs. The coloring algorithm exploits the simulated annealing paradigm, i.e., a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a sub optimal coloring scheme even for the case of dynamic channel allocation. However, a stateful implementation of the D1EC scheme is needed in order to speed-up the network coloring upon topology changes. In fact, a stateful D1EC reduces the algorithm’s convergen…
A tabu thresholding algorithm for arc crossing minimization in bipartite graphs
1996
Acyclic directed graphs are commonly used to model complex systems. The most important criterion to obtain a readable map of an acyclic graph is that of minimizing the number of arc crossings. In this paper, we present a heuristic for solving the problem of minimizing the number of arc crossings in a bipartite graph. It consists of a novel and easier implementation of fundamental tabu search ideas without explicit use of memory structures (a tabu thresholding approach). Computational results are reported on a set of 250 randomly generated test problems. Our algorithm has been compared with the two best heuristics published in the literature and with the optimal solutions for the test proble…
A note on the separation of subtour elimination constraints in elementary shortest path problems
2013
Abstract This note proposes an alternative procedure for identifying violated subtour elimination constraints (SECs) in branch-and-cut algorithms for elementary shortest path problems. The procedure is also applicable to other routing problems, such as variants of travelling salesman or shortest Hamiltonian path problems, on directed graphs. The proposed procedure is based on computing the strong components of the support graph. The procedure possesses a better worst-case time complexity than the standard way of separating SECs, which uses maximum flow algorithms, and is easier to implement.
Using a TSP heuristic for routing order pickers in warehouses
2010
In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner travelling salesman problem (TSP), exact algorithms only exist for warehouses with at most three cross aisles, while for other warehouse types literature provides a selection of dedicated construction heuristics. We evaluate to what extent reformulating and solving the problem as a classical TSP leads to performance improvements compared to existing dedicated heuristics. We report average savings in route distance of up to 47% when using the LKH (Lin-Kernighan-Helsgaun) TSP heuristic. Additionally, we examine if combining problem-sp…
Edge Orientation and the Design of Problem-Specific Crossover Operators for the OCST Problem
2012
In the Euclidean optimal communication spanning tree problem, the edges in optimal trees not only have small weights but also point with high probability toward the center of the graph. These characteristics of optimal solutions can be used for the design of problem-specific evolutionary algorithms (EAs). Recombination operators of direct encodings like edge-set and NetDir can be extended such that they prefer not only edges with small distance weights but also edges that point toward the center of the graph. Experimental results show higher performance and robustness in comparison to EAs using existing crossover strategies.
Incremental bipartite drawing problem
2001
Abstract Layout strategies that strive to preserve perspective from earlier drawings are called incremental. In this paper we study the incremental arc crossing minimization problem for bipartite graphs. We develop a greedy randomized adaptive search procedure (GRASP) for this problem. We have also developed a branch-and-bound algorithm in order to compute the relative gap to the optimal solution of the GRASP approach. Computational experiments are performed with 450 graph instances to first study the effect of changes in grasp search parameters and then to test the efficiency of the proposed procedure. Scope and purpose Many information systems require graphs to be drawn so that these syst…