Journal: SIAM Journal On Computing

Found 19 papers in total
Gadgets, approximation, and linear programming
Gadgets, approximation, and linear programming
2000,
We present a linear programming-based method for finding ‘gadgets,’ i.e.,...
The angular-metric traveling salesman problem
The angular-metric traveling salesman problem
2000,
Motivated by applications in robotics, we formulate the problem of minimizing the...
A polynomial-time approximation scheme for minimum routing cost spanning trees
A polynomial-time approximation scheme for minimum routing cost spanning trees
2000,
Given an undirected graph with nonnegative costs on the edges, the routing cost of any...
Approximation algorithms for the orthogonal z-oriented three-dimensional packing problem
Approximation algorithms for the orthogonal z-oriented three-dimensional packing problem
2000,
We present approximation algorithms for the orthogonal z -oriented three-dimensional...
Finding an even simple path in a directed planar graph
Finding an even simple path in a directed planar graph
1999,
In this paper we show that the following problem, the even simple path (ESP) problem...
On the maximum scatter traveling salesperson problem
On the maximum scatter traveling salesperson problem
1999,
We study the problem of computing a Hamiltonian tour (cycle) or path on a set of...
Improved approximation guarantees for packing and covering integer programs
Improved approximation guarantees for packing and covering integer programs
1999,
Several important NP-hard combinatorial optimization problems can be posed as...
An optimal algorithm for Euclidean shortest paths in the plane
An optimal algorithm for Euclidean shortest paths in the plane
1999,
We propose an optimal-time algorithm for a classical problem in plane computational...
Optimal search in trees
Optimal search in trees
1999,
It is well known that the optimal solution for searching in a finite total order set...
Approximating capacitated routing and delivery problems
Approximating capacitated routing and delivery problems
1999,
We provide approximation algorithms for some capacitated vehicle routing and delivery...
New results on the old k-opt algorithm for the traveling salesman problem
New results on the old k-opt algorithm for the traveling salesman problem
1999,
Local search with k -change neighborhoods is perhaps the oldest and most widely used...
The construction of Huffman codes is a submodular (‘convex’) optimization problem over a lattice of binary trees
The construction of Huffman codes is a submodular (‘convex’) optimization problem over a lattice of binary trees
1999,
We show that the space of all binary Huffman codes for a finite alphabet defines a...
Tree data structures for N-body simulation
Tree data structures for N-body simulation
1999,
In this paper, we study data structures for use in N -body simulation. We concentrate...
An O (log k) approximate min-cut max-flow theorem and approximation algorithm
An O (log k) approximate min-cut max-flow theorem and approximation algorithm
1998,
It is shown that the minimum cut ratio is within a factor of O(log k ) of the maximum...
A sublinear time distributed algorithm for minimum-weight spanning trees
A sublinear time distributed algorithm for minimum-weight spanning trees
1998,
This paper considers the question of identifying the parameters governing the behavior...
Linear and O(n log n) time minimum-cost matching algorithms for quasi-convex tours
Linear and O(n log n) time minimum-cost matching algorithms for quasi-convex tours
1998,
Let G be a complete, weighted, undirected, bipartite graph with n red nodes, n ′...
Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs
Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs
1991,
Efficient algorithms are known for finding a maximum weight stable set, a minimum...
An O(n3/log(n))-time maximum-flow algorithm
An O(n3/log(n))-time maximum-flow algorithm
1996,
We show that a maximum flow in a network with n vertices can be computed...
Simple local search problems that are hard to solve
Simple local search problems that are hard to solve
1991,
Many algorithms for NP-hard optimization problems find solutions that are locally...
Papers per page: