Arrow Research search

Author name cluster

Guy Kortsarz

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.

31 papers
2 author rows

Possible papers

31

TCS Journal 2026 Journal Article

A logarithmic approximation algorithm for the activation edge-multicover problem

  • Zeev Nutov
  • Avner Huri
  • Guy Kortsarz

In the Activation Edge-Multicover problem we are given a multigraph G=(V,E) with activation costs for every edge and degree requirements for every vertex. The goal is to find an edge subset J of minimum activation cost such that every vertex has at least its required number of neighbors in the graph. Let k be the maximum requirement and theta be the maximum quotient between the two costs of an edge. For theta equal to 1 the problem admits approximation ratio O(log k). For k equal to 1 it generalizes the Set Cover problem and admits a tight approximation ratio O(log n). This implies approximation ratio O(k log n) for general k and theta, and no better approximation ratio was known. We obtain the first logarithmic approximation ratio O(log k + log min{theta,n}), bridging the two known ratios O(log k) for theta equal to 1 and O(log n) for k equal to 1. This also implies an approximation ratio for the Activation k-Connected Subgraph problem based on the best known approximation ratio for the ordinary min-cost version of the problem.

Details DOI

MFCS Conference 2019 Conference Paper

Approximating Activation Edge-Cover and Facility Location Problems

  • Zeev Nutov
  • Guy Kortsarz
  • Eli Shalom

What approximation ratio can we achieve for the Facility Location problem if whenever a client u connects to a facility v, the opening cost of v is at most theta times the service cost of u? We show that this and many other problems are a particular case of the Activation Edge-Cover problem. Here we are given a multigraph G=(V, E), a set R subseteq V of terminals, and thresholds {t^e_u, t^e_v} for each uv-edge e in E. The goal is to find an assignment a={a_v: v in V} to the nodes minimizing sum_{v in V} a_v, such that the edge set E_a={e=uv: a_u >= t^e_u, a_v >= t^e_v} activated by a covers R. We obtain ratio 1+max_{x>=1}(ln x)/(1+x/theta)~= ln theta - ln ln theta for the problem, where theta is a problem parameter. This result is based on a simple generic algorithm for the problem of minimizing a sum of a decreasing and a sub-additive set functions, which is of independent interest. As an application, we get the same ratio for the above variant of {Facility Location}. If for each facility all service costs are identical then we show a better ratio 1+max_{k in N}(H_k-1)/(1+k/theta), where H_k=sum_{i=1}^k 1/i. For the Min-Power Edge-Cover problem we improve the ratio 1. 406 of [Calinescu et al, 2019] (achieved by iterative randomized rounding) to 1. 2785. For unit thresholds we improve the ratio 73/60~=1. 217 of [Calinescu et al, 2019] to 1555/1347~=1. 155.

Details

SODA Conference 2017 Conference Paper

Approximating Spanners and Directed Steiner Forest: Upper and Lower Bounds

  • Eden Chlamtac
  • Michael Dinitz
  • Guy Kortsarz
  • Bundit Laekhanukit

It was recently found that there are very close connectionsbetween the existence of additive spanners (subgraphs where all distances are preserved up to an additive stretch), distance preservers (subgraphs in which demand pairs have their distance preserved exactly), and pairwise spanners (subgraphs in which demand pairs have their distance preserved up to a multiplicative or additive stretch) [Abboud-Bodwin SODA ‘16, Bodwin-Williams SODA ‘16]. We study these problemsfrom an optimization point of view, where ratherthan studying the existence of extremal instances we are given an instance and are asked to find the sparsest possible spanner/preserver. We give an O ( n 3/5+∊ )-approximation for distance preservers and pairwisespanners (for arbitrary constant ∊ > 0). This is the first nontrivial upper bound for either problem, both of which are known to be as hard to approximate as Label Cover. We also prove Label Cover hardness for approximating additive spanners, even for the cases of additive 1 stretch (where one might expect a polylogarithmic approximation, since the related multiplicative 2-spanner problem admits an O (log n )-approximation) and additive polylogarithmic stretch (where the related multiplicative spanner problem has an O (1)-approximation). Interestingly, the techniques we use in our approximation algorithm extend beyond distance-based problem to pure connectivity network design problems. In particular, our techniques allow us to give an O ( n 3/5+∊ )- approximation for the Directed Steiner Forest problem (for arbitrary constant ∊ > 0) when all edges have uniform costs, improving the previous best O ( n 2/3+∊ )- approximation due to Berman et al. [ICALP ‘11] (whichholds for general edge costs).

Details

FOCS Conference 2017 Conference Paper

From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

  • Parinya Chalermsook
  • Marek Cygan
  • Guy Kortsarz
  • Bundit Laekhanukit
  • Pasin Manurangsi
  • Danupon Nanongkai
  • Luca Trevisan 0001

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e. g. , [1], [2], [3]) are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any functions t and f that are independent of N (for Clique, we want f(OPT) = ω(1))? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i. e. , there is no o(OPT)-FPT-approximation algorithm for Clique and no f(OPT)-FPT-approximation algorithm for DomSet, for any function f (e. g. , this holds even if f is an exponential or the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (GapETH) [4], [5], which states that no 2 o(n) -time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - ε)-satisfiable for some constant ε > 0. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e. g. , Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [6], [7], [8]. Additionally, we rule out k o(1) -FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm. To the best of our knowledge, prior results only rule out constant factor approximation for Clique [9], [10] and log 1/4+ε (OPT) approximation for DomSet for any constant ε > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

Details

FOCS Conference 2006 Conference Paper

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design

  • Chandra Chekuri
  • MohammadTaghi Hajiaghayi
  • Guy Kortsarz
  • Mohammad R. Salavatipour

We consider approximation algorithms for non-uniform buy-at-bulk network design problems. The first non-trivial approximation algorithm for this problem is due to Charikar and Karagiozova (STOC 05); for an instance on h pairs their algorithm has an approximation guarantee of exp(O(radic(log h log log h)))for the uniform-demand case, and log D middot exp(O(radic(log h log log h))) for the general demand case, where D is the total demand. We improve upon this result, by presenting the first poly-logarithmic approximation for this problem. The ratio we obtain is O(log 3 h middot min{log D, gamma(h 2 )}) where his the number of pairs and gamma(n) is the worst case distortion in embedding the metric induced by a n vertex graph into a distribution over its spanning trees. Using the best known upper bound on gamma(n) we obtain an O(min{log 3 h middot log D, log 5 h log log h}) ratio approximation. We also give poly-logarithmic approximations for some variants of the single-source problem that we need for the multicommodity problem

Details

MFCS Conference 2004 Invited Paper

Multicoloring: Problems and Techniques

  • Magnús M. Halldórsson
  • Guy Kortsarz

Abstract A multicoloring is an assignment where each vertex is assigned not just a single number (a “color”) but a set of numbers. The number of colors assigned to the vertex is specified by the length (or color requirement ) parameter of that vertex in the input. As usual, adjacent vertices cannot receive the same color; thus here, the sets of colors they receive must be disjoint. Multicolorings are therefore proper generalizations of ordinary graph colorings. The purpose of this paper is to summarize some of the techniques that have been developed specifically for obtaining good approximate multicolorings in different classes of graphs.

Details

STOC Conference 2002 Conference Paper

Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem

  • Michael Elkin
  • Guy Kortsarz

(MATH) Consider a synchronous network of processors, modeled by directed or undirected graph G = ( V,E ), in which on each round every processor is allowed to choose one of its neighbors and to send him a message. Given a processor s ε V , and a subset T ⊆ V of processors, the telephone multicast problem requires to compute the shortest schedule (in terms of the number of rounds) that delivers a message from s to all the processors of T . The particular case T = V is called telephone broadcast problem.These problems have multiple applications in distributed computing. Several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the undirected variants of these problems are known. However, all these algorithms involve solving large linear programs. Devising a polylogarithmic approximation algorithm for the directed variants of these problems is anopen problem, posed in [15].We devise a combinatorial logarithmic approximation algorithm for these problems, that applies also for the directed broadcast problem. Our algorithm has significantly smaller running time, and seems to reveal more information about the combinatorial structure of the solution, than the previous algorithms, that are based on linear programming.(MATH) We also improve the lower bounds on the approximation threshold of these problems. Both problems are known to be 3/2-inapproximable. For the undirected (resp., directed) broadcast problem we show that it is NP-hard (resp., impossible unless $NP ⊇ DTIME( n O(log n ) )) to approximate it within a ratio of 3 —ε for any ε ρ 0 (resp., ω(\sqrt log n )).Finally, we study the radio broadcast problem. Its setting is similar to the telephone broadcast problem, but in every round every processor may either send a message to all its neighbors or may not send it at all. A processor is informed in a certain round if and only if it receives a message from precisely one neighbor .(MATH) This problem was known to admit O (log 2 n )-approximation algorithm, but no hardness of approximation was known. In this paper we show that the problem is ω(log n )-inapproximable unless NP ⊆ BPTIME( n log log n } ).

Details

FOCS Conference 1993 Conference Paper

On Choosing a Dense Subgraph (Extended Abstract)

  • Guy Kortsarz
  • David Peleg

This paper concerns the problem of computing the densest k-vertex subgraph of a given graph, namely, the subgraph with the most edges, or with the highest edges-to-vertices ratio. A sequence of approximation algorithms is developed for the problem, with each step yielding a better ratio at the cost of a more complicated solution. The approximation ratio of our final algorithm is O/spl tilde/(n/sup 0. 3885/). We also present a method for converting an approximation algorithm for an unweighted graph problem (from a specific class of maximization problems) into one for the corresponding weighted problem, and apply it to the densest subgraph problem. >

Details