Danny Segev

Department of Statistics, University of Haifa
Haifa 31905, Israel
Rabin Complex, room 8070
Phone: 04-8249683
Email: segevd@stat.haifa.ac.il
 

Research Themes

My current research broadly focuses on the design and analysis of algorithmic tools leading to exact, approximate, and online solutions with provably good performance guarantees. I am especially interested in real-life problems that have highly practical importance, yet leave plenty of room for theoretical investigations.

Applications: Transportation, supply-chain management, inventory, pricing, telecommunications, healthcare.

Theory: Network design, facility location, scheduling, routing, stochastic optimization.

Techniques: Mathematical programming, polyhedral combinatorics, randomization, algebraic methods, simulation.

Background

Teaching

Fall 2009/10: Workshop - Simulation in Logistics

Spring 2009/10: Optimization Methods

Papers and Manuscripts

Remarks: (1) Unless specified otherwise, authors are listed in alphabetical order; (2) Please email me if you are interested in a paper that is unavailable here.

• Iftah Gamzu and Danny Segev
  A Sublogarithmic Approximation for Highway and Tollbooth Pricing
  Manuscript, 2010.
  [full version]

• *Farhad Ghassemi, *Danny Segev, Retsef Levi, Wilton Levine, Peter Dunn, and Warren Sandberg
  Matching Staffing to Demand in a Very Large Academic Multispecialty Anesthesia Department
  21th Annual Production and Operations Management Society Conference (POMS), 2010.
  * Equal contribution; authors are listed according to medical / healthcare conventions

• *Danny Segev, Retsef Levi, Peter Dunn, and Warren Sandberg
  A Generalized Simulation Tool to Model Patient Transportation Systems
  21th Annual Production and Operations Management Society Conference (POMS), 2010.
  * Authors are listed according to medical / healthcare conventions

• Leah Epstein, Asaf Levin, Julián Mestre, and Danny Segev
  Improved Approximation Guarantees for Weighted Matching in the Semi-Streaming Model
  Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science (STACS), 2010, to appear.
  [abstract] [proceedings] [full version] [slides-25min]

  We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (STACS '08) by devising a deterministic approach whose performance guarantee is $4.91 + \eps$. In addition, we study preemptive online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of $4.967$ on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching.

• Vineet Goyal , Retsef Levi, and Danny Segev
  Near-Optimal Algorithms for the Assortment Planning Problem under Dynamic Substitution and Stochastic Demand
  Submitted to Operations Research. Presented in: Manufacturing and Service Operations Management Society Annual Conference (MSOM), 2009. Also in: International Symposium on Mathematical Programming (ISMP), 2009. Also in: INFORMS Annual Meeting, 2009.
  [abstract] [slides-25min]

  Assortment planning of substitutable products is a major operational issue that arises in many industries, such as retailing, airlines and consumer electronics. We consider a single-period joint assortment and inventory planning problem under dynamic substitution with stochastic demands, and provide complexity and algorithmic results, as well as insightful structural characterizations of near-optimal solutions for several variants of the problem. First, we show that the assortment planning problem is NP-hard even for the very simple consumer choice model where there is only a single consumer, who may prefer at most two items at a time. Moreover, we prove that the problem under consideration is NP-hard to approximate within a constant better than $1-1/e$ for a general consumer choice model and only one consumer. Second, we show that for several interesting and practical customer choice models, one can devise a polynomial-time approximation scheme (PTAS), implying that the problem can be solved efficiently to within any level of accuracy. To the best of our knowledge, this is the first efficient algorithm with provably near-optimal performance guarantees for assortment planning problems under dynamic substitution. Quite surprisingly, the algorithm we propose stocks only a constant number of different products types, depending only on the desired accuracy level. This provides an important managerial insight that assortments with a relatively small number of product types can obtain almost all of the potential profit.

• Anupam Gupta, Ravishankar Krishnaswamy, Amit Kumar, and Danny Segev
  Scheduling with Outliers
  Proceedings of the 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 149-162, 2009.
  [abstract] [proceedings] [APPROX version] [full version] [slides-25min]

  In classical scheduling problems, we are given jobs and machines, and have to schedule all the jobs to minimize some objective function. What if each job has a specified profit, and we are no longer required to process all jobs? Instead, we can schedule any subset of jobs whose total profit is at least a (hard) target profit requirement, while still trying to approximately minimize the objective function.
  
  We refer to this class of problems as scheduling with outliers. This model was initiated by Charikar and Khuller (SODA '06) for minimum max-response time in broadcast scheduling. In this paper, we consider three other well-studied scheduling objectives: the generalized assignment problem, average weighted completion time, and average flow time, for which LP-based approximation algorithms are provided. Our main results are:

  1. For the minimum average flow time problem on identical machines, we give a logarithmic approximation algorithm based on LP-rounding, and complement this result by presenting a matching integrality gap.

  2. For the average weighted completion time problem on unrelated machines, we give a constant-factor approximation. The algorithm is based on randomized rounding of the time-indexed LP relaxation strengthened by knapsack-cover inequalities.

  3. For the generalized assignment problem with outliers, we outline a simple reduction to GAP without outliers to obtain an algorithm whose makespan is within $3$ times the optimum makespan, and whose cost is at most $(1+\epsilon)$ times the optimal cost.

• Amitai Armon, Iftah Gamzu, and Danny Segev
  Mobile Facility Location: Combinatorial Filtering via Weighted Occupancy
  Manuscript.

• Iftah Gamzu and Danny Segev
  A Polylogarithmic Approximation for Computing Non-Metric Terminal Steiner Trees
  Submitted to Information Processing Letters.

• Danny Segev
  Approximating k-Generalized Connectivity via Collapsing HSTs
  Journal of Combinatorial Optimization, to appear.
  [abstract] [JOCO] [full version]

  An instance of the $k$-generalized connectivity problem consists of an undirected graph $G = (V,E)$, whose edges are associated with non-negative costs, and a collection ${\cal D} = \{ (S_1, T_1), \ldots, (S_d, T_d) \}$ of distinct demands, each of which comprises a pair of disjoint vertex sets. We say that a subgraph ${\cal H} \subseteq G$ connects a demand $(S_i, T_i)$ when it contains a path with one endpoint in $S_i$ and the other in $T_i$. Given an integer parameter $k$, the goal is to identify a minimum cost subgraph that connects at least $k$ demands in ${\cal D}$.
  
  Alon, Awerbuch, Azar, Buchbinder and Naor (SODA '04) seem to have been the first to consider the generalized connectivity paradigm as a unified machinery for incorporating multiple-choice decisions into network formation settings. Their main contribution in this context was to devise a multiplicative-update online algorithm for computing log-competitive fractional solutions, and to propose provably-good rounding procedures for important special cases. Nevertheless, approximating the generalized connectivity problem in its unconfined form, where one makes no structural assumptions about the underlying graph and collection of demands, has remained an open question up until a recent $O( \log^2 n \log^2 d )$ approximation due to Chekuri, Even, Gupta and Segev (SODA '08). Unfortunately, the latter result does not extend to connecting a pre-specified number of demands. Furthermore, even the simpler case of singleton demands has been established as a challenging computational task, when Hajiaghayi and Jain (SODA~'06) related its inapproximability to that of dense $k$-subgraph.
  
  In this paper, we present the first non-trivial approximation algorithm for $k$-generalized connectivity, which is derived by synthesizing several techniques originating in probabilistic embeddings of finite metrics, network design, and randomization. Specifically, our algorithm constructs, with constant probability, a feasible subgraph whose cost is within a factor of $O( n^{ 2/3 } \cdot \polylog(n,k) )$ of optimal. We believe that the fundamental approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.

• Chandra Chekuri, Guy Even, Anupam Gupta, and Danny Segev
  Set Connectivity Problems in Undirected Graphs and the Directed Steiner Network Problem
  ACM Transactions on Algorithms, to appear. Also in: Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 532-541, 2008.
  [abstract] [remarks] [proceedings] [SODA version] [full version] [slides-25min]

  In the generalized connectivity problem, we are given an edge-weighted graph $G = (V,E)$ and a collection ${\cal D} = \{ (S_1, T_1), ..., (S_k, T_k) \}$ of distinct demands, each of which comprises a pair of disjoint vertex sets. We say that a subgraph $F \subseteq G$ connects a demand $(S_i, T_i)$ when it contains a path with one endpoint in $S_i$ and the other in $T_i$. The goal is to identify a minimum weight subgraph that connects all demands in ${\cal D}$. Alon et al. (SODA '04) introduced this paradigm as a unified machinery for handling online network formation settings, showing that it captures many extensively-studied problems, such as Steiner forest, non-metric facility location, tree multicast, and group Steiner tree. Nevertheless, approximating the generalized connectivity problem in its unconfined form has remained an open question. Our starting point is the first polylogarithmic approximation for generalized connectivity, attaining a performance guarantee of $O(\log^2 n \log^2 k )$. We also prove that the cut-covering relaxation of this problem has an $O(\log^3 n \log^2 k)$ integrality gap.
  
  Building upon the above-mentioned findings, we propose improved algorithms for two computational tasks that contain generalized connectivity as a special case. For the directed Steiner network problem, we obtain an $O( k^{ 1/2 + \eps } )$ approximation, which improves on the currently best performance guarantee of $\tilde{O}( k^{ 2/3 } )$ due to Charikar et al. (SODA '98). For the set connector problem, recently introduced by Fukunaga and Nagamochi (IPCO '07), we present the first polylogarithmic approximation; this result improves on the currently best ratio, which might be linear in the worst case.

  In a very recent manuscript, Feldman, Kortsarz and Nutov [ECCC TR07-120] achieve a performance guarantee of $O( n^{ 4/5 + eps } )$ for directed Steiner network, which can be viewed as the first sub-linear approximation for this problem. They also match our main result in this context, an $O( k^{1/2 + eps } )$ approximation, by employing a more efficient algorithm (albeit a more involved upper bound proof on the density of in-star-out-tree junction structures).

• Dan Feldman, Amos Fiat, Danny Segev, and Micha Sharir
  Bi-Criteria Linear-Time Approximations for Generalized k-Mean/Median/Center
  Proceedings of the 23rd Annual ACM Symposium on Computational Geometry (SOCG), pages 19-26, 2007.
  [abstract] [proceedings] [SOCG version] [slides-25min]

  We consider the computational task of approximating a set $P$ of $n$ points in $R^d$ by a collection of $j$-dimensional flats, under the median / mean / center measures, in which we wish to minimize, respectively, the sum of distances from each point to its nearest flat, the sum of squared distances, or the maximal such distance. While not admitting any approximation unless $P=NP$, these problems are known to have bi-criteria heuristics, allowing some leeway in the number of flats. We suggest an elegant bi-criteria algorithm, which exceeds the optimal objective value by a factor of no more than $2^{O(j)}$, and produces at most $\log n (j k \log\log n)^{O(j)}$ flats. Given this bi-criteria approximation, we can arbitrarily improve on its performance guarantee, at the cost of increasing the number of flats. Our algorithm has many advantages over previous work, as it is much more applicable (wider set of objective functions and classes of clusters) and much more efficient, reducing the currently best running time from $O(n^{poly(k,j)})$ to $d n (jk)^{O(j)}$.

• Refael Hassin, Jérôme Monnot, and Danny Segev
  The Complexity of Bottleneck Labeled Graph Problems
  Algorithmica, to appear. Also in: Proceedings of the 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG), pages 328-340, 2007.
  [abstract] [Algorithmica] [proceedings] [WG version] [full version] [slides-25min]

  In the present paper, we study bottleneck labeled optimization problems arising in the context of graph theory. This long-established model partitions the set of edges into classes, each of which is identified by a unique color. The generic objective is to construct a subgraph of prescribed structure (such as that of being an $s$-$t$ path, a spanning tree, or a perfect matching) while trying to avoid over-picking or under-picking edges from any given color.

• Iftah Gamzu and Danny Segev
  Improved Online Algorithms for the Sorting Buffer Problem on Line Metrics
  ACM Transactions on Algorithms, 6(1), article 15, 2009. Also in: Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 658-669, 2007.
  [abstract] [remarks] [TALG] [proceedings] [STACS version] [full version] [slides-25min, 50min_A, 50min_B]

  An instance of the sorting buffer problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. An additional ingredient of the input is an online sequence of requests, each of which is characterized by a destination in the given metric; whenever a request arrives, it must be stored in the sorting buffer. At any point in time, a currently pending request can be served by drawing it out of the buffer and moving the server to its corresponding destination. The objective is to serve all input requests in a way that minimizes the total distance traveled by the server.
  
  In this paper, we focus our attention on instances of the problem in which the underlying metric is either an evenly-spaced line metric or a continuous line metric. Although such restricted settings may appear to be very simple at first glance, we demonstrate that they still capture one of the most fundamental problems in the design of storage systems, known as the disk arm scheduling problem. Our main findings can be briefly summarized as follows:

  1.  We present a deterministic $O(\log n)$-competitive algorithm for $n$-point evenly-spaced line metrics. This result improves on a randomized $O(\log^{2} n)$-competitive algorithm due to Khandekar and Pandit (STACS '06). It also refutes their conjecture, stating that a deterministic strategy is unlikely to obtain a non-trivial competitive ratio.

  2.  We devise a deterministic $O(\log N \log\log N)$-competitive algorithm for continuous line metrics, where $N$ denotes the length of the input sequence. In this context, we introduce a novel discretization technique, which is of independent interest, as it may be applicable in other settings as well.

  3.  We establish the first non-trivial lower bound for the evenly-spaced case, by proving that the competitive ratio of any deterministic algorithm is at least $\frac{2 + \sqrt{3}}{ \sqrt{3} } \approx 2.154$. This result settles, to some extent, an open question due to Khandekar and Pandit (STACS '06), who posed the task of attaining lower bounds on the achievable competitive ratio as a foundational objective for future research.

  The most fundamental open question in this context has recently been answered by Englert, Räcke and Westermann [STOC '07], who attained a randomized polylogarithmic competitive ratio for general metrics. In addition, for the offline version of uniformly-spaced line metrics, Khandekar and Pandit [ISAAC '06, pages 81-89] proposed a quasi-polynomial time constant-factor approximation. On a different note, we already know how to eliminate the O(\log\log{N}) factor in our competitive ratio for continuous line metrics, by employing a new partitioning scheme.

• Danny Segev and Gil Segev
  Approximate k-Steiner Forests via the Lagrangian Relaxation Technique with Internal Preprocessing
  Algorithmica, 56(4):529-549, 2010. Also in: Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pages 600-611, 2006.
  [abstract] [remarks] [Algorithmica] [proceedings] [ESA version] [full version] [slides-50min, 25min]

  An instance of the $k$-Steiner forest problem consists of an undirected graph $G = (V,E)$, the edges of which are associated with non-negative costs, and a collection ${\cal D} = \{ (s_1, t_1), \ldots, (s_d, t_d) \}$ of distinct pairs of vertices, interchangeably referred to as demands. We say that a forest ${\cal F} \subseteq G$ connects a demand $(s_i, t_i)$ when it contains an $s_i$-$t_i$ path. Given a requirement parameter $k \leq |{\cal D}|$, the goal is to find a minimum cost forest that connects at least $k$ demands in ${\cal D}$. This problem has recently been studied by Hajiaghayi and Jain [SODA '06], whose main contribution in this context was to relate the inapproximability of $k$-Steiner forest to that of the dense $k$-subgraph problem. However, Hajiaghayi and Jain did not provide any algorithmic result for the respective settings, and posed this objective as an important direction for future research.

  In this paper, we present the first non-trivial approximation algorithm for the $k$-Steiner forest problem, which is based on a novel extension of the Lagrangian relaxation technique. Specifically, our algorithm constructs a feasible forest whose cost is within a factor of $O( \min \{ n^{ 2/3 }, \sqrt{d} \} \cdot \log d )$ of optimal, where $n$ is the number of vertices in the input graph and $d$ is the number of demands. We believe that the approach illustrated in the current writing is of independent interest, and may be applicable in other settings as well.

  Several recent papers discuss the closely-related prize-collecting Steiner forest problem. For example: Hajiaghayi and Jain [SODA '06, pages 631-640]; Sharma, Swamy and Williamson [SODA '07]; Gupta, Könemann, Leonardi, Ravi and Schäfer [SODA '07]. In addition, we have resolved the main open question presented in Section 4, regarding the approximability of generalized demands.

• Jochen Könemann, Ojas Parekh, and Danny Segev
  A Unified Approach to Approximating Partial Covering Problems
  Algorithmica, to appear. Also in: Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pages 468-479, 2006.
  [abstract] [remarks] [Algorithmica] [proceedings] [ESA version] [full version] [slides-25min]

  An instance of the generalized partial cover problem consists of a ground set $U$ and a family of subsets ${\cal S} \subseteq 2^U$. Each element $e \in U$ is associated with a profit $p(e)$, whereas each subset $S \in {\cal S}$ has a cost $c(S)$. The objective is to find a minimum cost subcollection ${\cal S}'\subseteq {\cal S}$ such that the combined profit of the elements covered by ${\cal S}'$ is at least $P$, a specified profit bound. In the prize-collecting version of this problem, there is no strict requirement to cover any element; however, if the subsets we pick leave an element $e \in U$ uncovered, we incur a penalty of $\pi(e)$. The goal is to identify a subcollection ${\cal S}' \subseteq {\cal S}$ that minimizes the cost of ${\cal S}'$ plus the penalties of uncovered elements.
  
  Although problem-specific connections between the partial cover and the prize-collecting variants of a given covering problem have been explored and exploited, a more general connection remained open. The main contribution of this paper is to establish a formal relationship between these two variants. As a result, we present a unified framework for approximating problems that can be formulated or interpreted as special cases of generalized partial cover. We demonstrate the applicability of our method on a diverse collection of covering problems, for some of which we obtain the first non-trivial approximability results.

  Julián Mestre suggested an elegant way of (essentially) eliminating the \epsilon term, that appears at first glance to be inherent to our approach; this modification will probably appear in the journal version.

• Ojas Parekh and Danny Segev
  Path Hitting in Acyclic Graphs
  Algorithmica, 52(4):466-486, 2008. Also in: Proceedings of the 14th Annual European Symposium on Algorithms (ESA), pages 564-575, 2006.
  [abstract] [Algorithmica] [proceedings] [ESA version] [full version] [slides-25min]

  An instance of the path hitting problem consists of two families of paths, ${\cal D}$ and ${\cal H}$, in a common undirected graph, where each path in ${\cal H}$ is associated with a non-negative cost. We refer to ${\cal D}$ and ${\cal H}$ as the sets of demand and hitting paths, respectively. When $p \in {\cal H}$ and $q \in {\cal D}$ share at least one mutual edge, we say that $p$ hits $q$. The objective is to find a minimum cost subset of ${\cal H}$ whose members collectively hit those of ${\cal D}$. In this paper we provide constant factor approximation algorithms for path hitting, confined to instances in which the underlying graph is a tree, a spider, or a star. Although such restricted settings may appear to be very simple, we demonstrate that they still capture some of the most basic covering problems in graphs. Our approach combines several novel ideas: We extend the algorithm of Garg, Vazirani and Yannakakis [Algorithmica, 18:3--20, 1997] for approximate multicuts and multicommodity flows in trees to prove new integrality properties; we present a reduction that involves multiple calls to this extended algorithm; and we introduce a polynomial-time solvable variant of the edge cover problem, which may be of independent interest.

• Refael Hassin, Jérôme Monnot, and Danny Segev
  Approximation Algorithms and Hardness Results for Labeled Connectivity Problems
  Journal of Combinatorial Optimization, 14(4):437-453, 2007. Also in: Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 480-491, 2006.
  [abstract] [JOCO] [proceedings] [MFCS version] [full version] [slides-25min]

  Let $G = (V,E)$ be a connected multigraph, whose edges are associated with labels specified by an integer-valued function ${\cal L} : E \to \bbN$. In addition, each label $\ell \in \bbN$ has a non-negative cost $c( \ell )$. The minimum label spanning tree problem (MinLST) asks to find a spanning tree in $G$ that minimizes the overall cost of the labels used by its edges. Equivalently, we aim at finding a minimum cost subset of labels $I \subseteq \bbN$ such that the edge set $\{ e \in E : {\cal L}( e ) \in I \}$ forms a connected subgraph spanning all vertices. Similarly, in the minimum label $s$-$t$ path problem (MinLP) the goal is to identify an $s$-$t$ path minimizing the combined cost of its labels. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP.

• Asaf Levin and Danny Segev
  Partial Multicuts in Trees
  Theoretical Computer Science, 369(1-3):384-395, 2006. Also in: Proceedings of the 3rd International Workshop on Approximation and Online Algorithms (WAOA), pages 320-333, 2005.
  [abstract] [remarks] [TCS] [proceedings] [WAOA version] [full version] [slides-25min]

  Let $T = (V,E)$ be an undirected tree, in which each edge is associated with a non-negative cost, and let $\{ s_1, t_1 \}, \ldots, \{ s_k, t_k \}$ be a collection of $k$ distinct pairs of vertices. Given a requirement parameter $t \leq k$, the partial multicut on a tree problem asks to find a minimum cost set of edges whose removal from $T$ disconnects at least $t$ out of these $k$ pairs. This problem generalizes the well-known multicut on a tree problem, in which we are required to disconnect all given pairs.
  
  The main contribution of this paper is an $( \frac{ 8 }{ 3 } + \epsilon )$-approximation algorithm for partial multicut on a tree, whose run time is strongly polynomial for any fixed $\epsilon > 0$. This result is achieved by introducing problem-specific insight to the general framework of using the Lagrangian relaxation technique in approximation algorithms. Our algorithm utilizes a heuristic for the closely related prize-collecting variant, in which we are not required to disconnect all pairs, but rather incur penalties for failing to do so. We provide a Lagrangian multiplier preserving algorithm for the latter problem, with an approximation factor of 2. Finally, we present a new 2-approximation algorithm for multicut on a tree, based on LP-rounding.

  Some of our results were independently obtained by Golovin, Nagarajan and Singh [SODA '06, pages 621-630].

• Danny Segev
  An Improved Approximation Algorithm for the Crossing Spanning Tree Problem
  Unpublished manuscript, 2005.
  [synopsis]

  In this short note I suggest a polylogarithmic approximation for the crossing spanning tree problem. This improves an earlier result due to Bilo, Goyal, Ravi and Singh [APPROX 2004, pages 51-64]. However, in the full version of their paper Bilo et al. achieve an even better approximation. Very recently, Bansal, Khandekar and Nagarajan [STOC 2008] were able to obtain an additive approximation guarantee.

• Refael Hassin and Danny Segev
  The Set Cover with Pairs Problem
  Proceedings of the 25th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 164-176, 2005.
  [abstract] [remarks] [proceedings] [FSTTCS version] [full version] [slides-25min]

  We consider a generalization of the set cover problem, in which elements are covered by pairs of objects, and we are required to find a minimum cost subset of objects that induces a collection of pairs covering all elements. Formally, let $U$ be a ground set of elements and let ${\cal S}$ be a set of objects, where each object $i$ has a non-negative cost $w_i$. For every $\{ i, j \} \subseteq {\cal S}$, let ${\cal C}(i,j)$ be the collection of elements in $U$ covered by the pair $\{ i, j \}$. The Set Cover with Pairs problem asks to find a subset $A \subseteq {\cal S}$ such that $\bigcup_{ \{ i, j \} \subseteq A } {\cal C}(i,j) = U$ and such that $\sum_{ i \in A } w_i$ is minimized.
  
  In addition to studying this general problem, we are also concerned with developing polynomial time approximation algorithms for interesting special cases. The problems we consider in this framework arise in the context of domination in metric spaces and separation of point sets.

  The avid reader may also be interested in this paper by Hajiaghayi, Jain, Lau, Mandoiu, Russell and Vazirani.

• Refael Hassin and Danny Segev
  Rounding to an Integral Program
  Operations Research Letters, 36(3):321-326, 2008. Also in: Proceedings of the 4th International Workshop on Efficient and Experimental Algorithms (WEA), pages 44-54, 2005.
  [abstract] [ORL] [proceedings] [WEA version] [full version]

  We present a general framework for approximating several NP-hard problems that have two underlying properties in common. First, the problems we consider can be formulated as integer covering programs, possibly with additional side constraints. Second, the number of covering options is restricted in some sense, although this property may be well hidden.
  
  Our method is a natural extension of the threshold rounding technique: Instead of rounding an optimal fractional solution $x^*$ to an integral solution, we round $x^*$ to an integral program. In other words, using $x^*$ and a threshold parameter $\lambda$, we construct a new linear program such that any feasible solution to the new linear program is also feasible to the original program and such that it is defined over an integer polyhedron $P^*$. By solving the new linear program, we obtain an integral solution to the original problem, and prove that its cost is within factor $\frac{ 1 }{ \lambda }$ of optimum by fitting $x^*$ into the polyhedron $P^*$, that is, we show that $\frac{ 1 }{ \lambda } x^* \in P^*$.

• Refael Hassin and Danny Segev
  The Multi-Radius Cover Problem
  Proceedings of the 9th International Workshop on Algorithms and Data Structures (WADS), pages 24-35, 2005.
  [abstract] [remarks] [proceedings] [WADS version] [full version] [slides-50min, 25min]

  Let $G = (V,E)$ be a graph with a non-negative edge length $l_{u,v}$ for every $(u,v) \in E$. The vertices of $G$ represent locations at which transmission stations are positioned, and each edge of $G$ represents a continuum of demand points to which we should transmit. A station located at $v$ is associated with a set $R_v$ of allowed transmission radii, where the cost of transmitting to radius $r \in R_v$ is given by $c_v(r)$. The multi-radius cover problem asks to determine for each station a transmission radius, such that for each edge $(u,v) \in E$ the sum of the radii in $u$ and $v$ is at least $l_{u,v}$, and such that the total cost is minimized.
  
  In this paper we present LP-rounding and primal-dual approximation algorithms for discrete and continuous variants of multi-radius cover. Our algorithms cope with the special structure of the problems we consider by utilizing greedy rounding techniques and a novel method for constructing primal and dual solutions.

  Subsequent work on MRC can be found in this paper, by Julián Mestre.

• Refael Hassin and Danny Segev
  Robust Subgraphs for Trees and Paths
  ACM Transactions on Algorithms, 2(2):263-281, 2006. Also in: Proceedings of the 9th Scandinavian Workshop on Algorithm Theory (SWAT), pages 51-63, 2004.
  [abstract] [TALG] [proceedings] [SWAT version] [full version] [slides-25min]

  Consider a graph problem which is associated with a parameter, for example, that of finding a longest tour spanning $k$ vertices. The following question is natural: Is there a small subgraph which contains an optimal or near optimal solution for every possible value of the given parameter? Such a subgraph is said to be robust. In this paper we consider the problems of finding heavy paths and heavy trees of $k$ edges. In these two cases we prove surprising bounds on the size of a robust subgraph for a variety of approximation ratios. For both problems we show that in every complete weighted graph on $n$ vertices there exists a subgraph with approximately $\frac{ \alpha }{ 1 - \alpha^2 } n$ edges which contains an $\alpha$-approximate solution for every $k = 1, \ldots, n-1$. In the analysis of the tree problem we also describe a new result regarding balanced decomposition of trees. In addition, we consider variants in which the subgraph itself is restricted to be a path or a tree. For these problems we describe polynomial time algorithms and corresponding proofs of negative results.

PhD Thesis

Approximation Algorithms for NP-Hard Combinatorial Optimization Problems [abstract]

Haifa Links

Departments: Statistics, Economics, Mathematics, Computer Science

Administration: Calendar, Webmail, Computing Services, Parking, Research Authority, Library

More Links

DBLP, CS Bibliographies, Google Scholar, CiteSeer

ACM Digital Library, SIAM Digital Library, IEEE Explore, ECCC, arXiv

Theory blogs, Accepted Papers, Deadlines