88 citations · 251 across the 29 of their papers we have counts for
6 papers · 1 filter
Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems
Sandor P. Fekete, Henk Meijer, Andre Rohe +1
We consider geometric instances of the Maximum Weighted Matching Problem (MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000 vertices. Making use of a geo…
Traveling Salesmen in the Presence of Competition
Sandor P. Fekete, Rudolf Fleischer, Aviezri Fraenkel +1
We propose the ``Competing Salesmen Problem'' (CSP), a 2-player competitive version of the classical Traveling Salesman Problem. This problem arises when considering two competing…
Characterizing Matchings as the Intersection of Matroids
Sandor P. Fekete, Robert T. Firla, Bianca Spille
This paper deals with the problem of representing the matching independence system in a graph as the intersection of finitely many matroids. After characterizing the graphs for whi…
On the Reflexivity of Point Sets
Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado +4
We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivity rho(S) of S is given by the smallest nu…
An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures
Esther M. Arkin, Sandor P. Fekete, Joseph S. B. Mitchell
We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non…
The Geometric Maximum Traveling Salesman Problem
Alexander Barvinok, Sandor P. Fekete, David S. Johnson +3
We consider the traveling salesman problem when the cities are points in R^d for some fixed d and distances are computed according to geometric distances, determined by some norm.…