Danny Segev

I&C Journal 2018 Journal Article

Improved bounds for randomized preemptive online matching

• Leah Epstein
• Asaf Levin
• Danny Segev
• Oren Weimann

Preemptive online algorithms for the maximum matching problem maintain a valid matching M while edges of the underlying graph are presented one after the other. When presented with an edge e, the algorithm should decide whether to augment the matching M by adding e (in which case e may be removed later on) or to keep M in its current form without adding e (in which case e is lost for good). The objective is to eventually hold a matching M with maximum weight. The main contribution of this paper is to establish new lower and upper bounds on the competitive ratio achievable by randomized preemptive online algorithms: • We provide a lower bound of 1 + ln ⁡ 2 ≈ 1. 693 on the competitive ratio of any randomized algorithm for the maximum cardinality matching problem. • We devise a randomized algorithm that achieves an expected competitive ratio of 5. 356 for maximum weight matching.

NeurIPS Conference 2016 Conference Paper

Assortment Optimization Under the Mallows model

• Antoine Desir
• Vineet Goyal
• Srikanth Jagabathula
• Danny Segev

We consider the assortment optimization problem when customer preferences follow a mixture of Mallows distributions. The assortment optimization problem focuses on determining the revenue/profit maximizing subset of products from a large universe of products; it is an important decision that is commonly faced by retailers in determining what to offer their customers. There are two key challenges: (a) the Mallows distribution lacks a closed-form expression (and requires summing an exponential number of terms) to compute the choice probability and, hence, the expected revenue/profit per customer; and (b) finding the best subset may require an exhaustive search. Our key contributions are an efficiently computable closed-form expression for the choice probability under the Mallows model and a compact mixed integer linear program (MIP) formulation for the assortment problem.

TCS Journal 2013 Journal Article

Approximation algorithms for orienting mixed graphs

• Michael Elberfeld
• Danny Segev
• Colin R. Davidson
• Dana Silverbush
• Roded Sharan

Graph orientation is a fundamental problem in graph theory that has recently arisen in the study of signaling-regulatory pathways in protein networks. Given a graph and a list of source–target vertex pairs, one wishes to assign directions to the edges so as to maximize the number of pairs that admit a directed source-to-target path. When the input graph is undirected, a sub-logarithmic approximation is known for this problem. However, the approximability of the biologically-relevant variant, in which the input graph has both directed and undirected edges, was left open. Here we give the first approximation algorithms to this problem. Our algorithms provide a sub-linear guarantee in the general case, and logarithmic guarantees for structured instances.

SODA Conference 2008 Conference Paper

Set connectivity problems in undirected graphs and the directed Steiner network problem

• Chandra Chekuri
• Guy Even
• Anupam Gupta 0001
• Danny Segev

MFCS Conference 2006 Conference Paper

Approximation Algorithms and Hardness Results for Labeled Connectivity Problems

• Refael Hassin
• Jérôme Monnot
• Danny Segev

Abstract Let G = ( V, E ) be a connected multigraph, whose edges are associated with labels specified by an integer-valued function \({\mathcal{L}}: E \rightarrow \mathbb{N}\). In addition, each label ℓ ∈ ℕ to which at least one edge is mapped has a non-negative cost c ( ℓ). 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 ⊆ ℕ such that the edge set \(\{ e \in E: {\mathcal {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, where s and t are provided as part of the input. The main contributions of this paper are improved approximation algorithms and hardness results for MinLST and MinLP. As a secondary objective, we make a concentrated effort to relate the algorithmic methods utilized in approximating these problems to a number of well-known techniques, originally studied in the context of integer covering.

TCS Journal 2006 Journal Article

Partial multicuts in trees

• Asaf Levin
• Danny Segev

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 }, …, { s k, t k } be a collection of k distinct pairs of vertices. Given a requirement parameter t ⩽ 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 ( 8 3 + ε ) -approximation algorithm for partial multicut on a tree, whose run time is strongly polynomial for any fixed ε > 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.