Arrow Research search

Author name cluster

Yefim Dinitz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

SoCS Conference 2024 Conference Paper

Generalized Longest Simple Path Problems: Speeding up Search Using SPQR Trees

  • Gal Dahan
  • Itay Tabib
  • Solomon Eyal Shimony
  • Yefim Dinitz

The longest simple path and snake-in-a-box are combinatorial search problems of considerable research interest. Recent work has recast these problems as special cases of a generalized longest simple path (GLSP) framework, and showed how to generate improved search heuristics for them. The greatest reduction in search effort was based on SPQR tree rules, but it was posed as an open problem how to use them optimally. Unrelated to search, a theoretical paper on the existence of simple cycles that include three given edges answers such queries in linear time with SPQR trees. These theoretical results are utilized in this paper to develop advanced heuristics and search partitioning for GLSP. Empirical results on grid-based graphs show that these heuristics can result in orders of magnitude reduction in the number of expansions, as well as significantly reduced overall runtime in most cases.

Details

FOCS Conference 2008 Conference Paper

Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners

  • Yefim Dinitz
  • Michael Elkin
  • Shay Solomon

We show that for every n-point metric space M and positive integer k, there exists a spanning tree T with unweighted diameter O(k) and weight w(T) = O(k ldr n 1/k ) ldr w(MST(M)), and a spanning tree T' with weight w(T') = O(k) ldr w(MST(M)) and unweighted diameter O(k ldr n 1/k ). Moreover, there is a designated point rt such that for every other point v, both dist T (rt, v) and dist T (rt, v) are at most (1 + epsiv) ldr dist M (rt, v), for an arbitrarily small constant epsiv > 0. We prove that the above tradeoffs are tight up to constant factors in the entire range of parameters. Furthermore, our lower bounds apply to a basic one-dimensional Euclidean space. Finally, our lower bounds for the particular case of unweighted diameter O(log n) settle a long-standing open problem in Computational Geometry.

Details

FOCS Conference 1998 Conference Paper

On the Single-Source Unsplittable Flow Problem

  • Yefim Dinitz
  • Naveen Garg 0001
  • Michel X. Goemans

Let G=(V, E) be a capacitated directed graph with a source s and k terminals t/sub i/ with demands d/sub i/, 1/spl les/i/spl les/k. We would like to concurrently route every demand on a single path from s to the corresponding terminal without violating the capacities. There are several interesting and important variations of this unsplittable flow problem. If the necessary cut condition is satisfied, we show how to compute an unsplittable flow satisfying the demands such that the total flow through any edge exceeds its capacity by at most the maximum demand. For graphs in which all capacities are at least the maximum demand, we therefore obtain an unsplittable flow with congestion at most 2, and this result is best possible. Furthermore, we show that all demands can be routed unsplittable in 5 rounds, i. e. , all demands can be collectively satisfied by the union of 5 unsplittable flows. Finally, we show that 22. 6% of the total demand can be satisfied unsplittably. These results are extended to the case when the cut condition is not necessarily satisfied. We derive a 2-approximation algorithm for congestion, a 5-approximation algorithm for the number of rounds and a 4. 43=1/0. 226-approximation algorithm for the maximum routable demand.

Details