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.

32 papers
2 author rows

Possible papers

32

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

TCS Journal 2022 Journal Article

Approximating activation edge-cover and facility location problems

  • Guy Kortsarz
  • Zeev Nutov
  • 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 θ 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 ⊆ V of terminals, and thresholds { t u e, t v e } for each uv-edge e ∈ E. The goal is to find an assignment a = { a v: v ∈ V } to the nodes minimizing ∑ v ∈ V a v, such that the edge set E a = { e = u v: a u ≥ t u e, a v ≥ t v e } activated by a covers R. We obtain ratio 1 + max x ≥ 1 ⁡ ln ⁡ x 1 + x / θ ≈ ln ⁡ θ − ln ⁡ ln ⁡ θ for the problem, where θ ≤ max e ∈ E ⁡ max ⁡ { t u e, t v e } min ⁡ { t u e, t v e } 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 ∈ N ⁡ H k − 1 1 + k / θ, where H k = ∑ i = 1 k 1 / i. For the Min-Power Edge-Cover problem we improve the ratio 1. 406 of [4] (achieved by iterative randomized rounding) to 1. 2785. For unit thresholds we improve the ratio 73 / 60 ≈ 1. 217 of [4] to 1555 1347 ≈ 1. 155.

Details DOI

TCS Journal 2020 Journal Article

Approximation algorithms for connected maximum cut and related problems

  • MohammadTaghi Hajiaghayi
  • Guy Kortsarz
  • Robert MacDavid
  • Manish Purohit
  • Kanthi Sarpatwar

An instance of the Connected Maximum Cut problem consists of an undirected graph G = ( V, E ) and the goal is to find a subset of vertices S ⊆ V that maximizes the number of edges in the cut δ ( S ) such that the induced graph G [ S ] is connected. We present the first non-trivial Ω ( 1 log ⁡ n ) approximation algorithm for the Connected Maximum Cut problem in general graphs using novel techniques. We then extend our algorithm to edge weighted case and obtain a poly-logarithmic approximation algorithm. Interestingly, in contrast to the classical Max-Cut problem that can be solved in polynomial time on planar graphs, we show that the Connected Maximum Cut problem remains NP-hard on unweighted, planar graphs. On the positive side, we obtain a polynomial time approximation scheme for the Connected Maximum Cut problem on planar graphs and more generally on bounded genus graphs.

Details DOI

TCS Journal 2020 Journal Article

Radio aggregation scheduling

  • Rajiv Gandhi
  • Magnús M. Halldórsson
  • Christian Konrad
  • Guy Kortsarz
  • Hoon Oh

We consider the aggregation problem in radio networks: find a spanning tree in a given graph and a conflict-free schedule of the edges so as to minimize the latency of the computation. While a large body of literature exists on this and related problems, we give the first approximation results in graphs that are not induced by unit ranges in the plane. We give a polynomial-time O ˜ ( d n ) -approximation algorithm, where d is the average degree and n the number of vertices in the graph, and show that the problem is Ω ( n 1 − ϵ ) -hard (and Ω ( ( d n ) 1 / 2 − ϵ ) -hard) to approximate even on bipartite graphs, for any ϵ > 0, rendering our algorithm essentially optimal. We also obtain a O ( log ⁡ n ) -approximation in interval graphs.

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

TCS Journal 2019 Journal Article

Improved approximation algorithms for minimum power covering problems

  • Gruia Calinescu
  • Guy Kortsarz
  • Zeev Nutov

Given an undirected graph with edge costs, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider two network design problems under the power minimization criteria. In both problems we are given a graph G = ( V, E ) with edge costs and a set T ⊆ V of terminals. The goal is to find a minimum power edge subset F ⊆ E such that the graph H = ( V, F ) satisfies some prescribed requirements. In the Min-Power Edge-Cover problem, H should contain an edge incident to every terminal. Using the Iterative Randomized Rounding (IRR) method, we give an algorithm with expected approximation ratio 1. 41; the ratio is reduced to 73 / 60 < 1. 217 when T is an independent set in G. In the case of unit costs we also achieve ratio 73/60, and in addition give a simple efficient combinatorial algorithm with ratio 5/4. For all these NP-hard problems the previous best known ratio was 3/2. In the related Min-Power Terminal Backup problem, H should contain a path from every t ∈ T to some node in T ∖ { t }. We obtain ratio 3/2 for this NP-hard problem, improving the trivial ratio of 2.

Details DOI

TCS Journal 2017 Journal Article

Approximating source location and star survivable network problems

  • Guy Kortsarz
  • Zeev Nutov

In Source Location (SL) problems the goal is to select a minimum cost source set S ⊆ V such that the connectivity (or flow) ψ ( S, v ) from S to any node v is at least the demand d v of v. In many SL problems ψ ( S, v ) = d v if v ∈ S, so the demand of nodes selected to S is completely satisfied. In a variant suggested recently by Fukunaga [7], every node v selected to S gets a “bonus” p v ≤ d v, and ψ ( S, v ) = p v + κ ( S ∖ { v }, v ) if v ∈ S and ψ ( S, v ) = κ ( S, v ) otherwise, where κ ( S, v ) is the maximum number of internally disjoint ( S, v ) -paths. While the approximability of many SL problems was seemingly settled to Θ ( ln ⁡ d ( V ) ) in [20], for his variant on undirected graphs Fukunaga achieved ratio O ( k ln ⁡ k ), where k = max v ∈ V ⁡ d v is the maximum demand. We improve this by achieving ratio min ⁡ { p ⁎ ln ⁡ k, k } ⋅ O ( ln ⁡ k ) for a more general version with node capacities, where p ⁎ = max v ∈ V ⁡ p v is the maximum bonus. In particular, for the most natural case p ⁎ = 1 we improve the ratio from O ( k ln ⁡ k ) to O ( ln 2 ⁡ k ). To derive these results, we consider a particular case of the Survivable Network (SN) problem when all edges of positive cost form a star. We obtain ratio O ( min ⁡ { ln ⁡ n, ln 2 ⁡ k } ) for this variant, improving over the best ratio known for the general case O ( k 3 ln ⁡ n ) of Chuzhoy and Khanna [4]. Finally, we obtain a logarithmic ratio for a generalization of SL where we also have edge-costs and flow-cost bounds { b v: v ∈ V }, and require that the minimum cost of a flow of value d v from S to every node v is at most b v.

Details DOI

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

TCS Journal 2012 Journal Article

Approximating fault-tolerant group-Steiner problems

  • Rohit Khandekar
  • Guy Kortsarz
  • Zeev Nutov

In this paper, we initiate the study of designing approximation algorithms for Fault-Tolerant Group-Steiner (FTGS) problems. The motivation is to protect the well-studied group-Steiner networks from edge or vertex failures. In Fault-Tolerant Group-Steiner problems, we are given a graph with edge- (or vertex-) costs, a root vertex, and a collection of subsets of vertices called groups. The objective is to find a minimum-cost subgraph that has two edge- (or vertex-) disjoint paths from each group to the root. We present approximation algorithms and hardness results for several variants of this basic problem, e. g. , edge-costs vs. vertex-costs, edge-connectivity vs. vertex-connectivity, and 2-connecting a single vertex vs. two distinct vertices from each group. The main contributions of our paper include the introduction of general structural lemmas on connectivity and a charging scheme that may find more applications in the future. Our algorithmic results are supplemented by inapproximability results, which are tight in some cases.

Details DOI

TCS Journal 2012 Journal Article

The checkpoint problem

  • MohammadTaghi Hajiaghayi
  • Rohit Khandekar
  • Guy Kortsarz
  • Julián Mestre

In this paper, we consider the checkpoint problem. The input consists of an undirected graph G, a set of source–destination pairs { ( s 1, t 1 ), ( s 2, t 2 ), …, ( s k, t k ) }, and a collection P of paths connecting the ( s i, t i ) pairs. A feasible solution is a multicut E ′, namely, a set of edges whose removal disconnects every source–destination pair. For each p ∈ P we define cp E ′ ( p ) = | p ∩ E ′ |. In the sum checkpoint (SCP) problem the goal is to minimize ∑ p ∈ P cp E ′ ( p ), while in the maximum checkpoint (MCP) problem the goal is to minimize max p ∈ P cp E ′ ( p ). These problems have several natural applications, e. g. , in urban transportation and network security. In a sense, they combine the multicut problem and the minimum membership set cover problem. For the sum objective we show that weighted SCP is equivalent, with respect to approximability, to undirected multicut. Thus there exists an O ( log n ) approximation for SCP in general graphs. Our current approximability results for the max objective have a wide gap: we provide an approximation factor of O ( n log n / opt ) for MCP and a hardness of 2 under the assumption P ≠ NP. The hardness holds for trees. This solves an open problem of Nelson (2009) [25]. We complement the lower bound by an almost matching upper bound with an asymptotic approximation factor of 2. On trees with all s i, t i having an ancestor–descendant relation, we give a combinatorial exact algorithm. Besides the algorithm being combinatorial, its running time improves by many orders of magnitude the LP algorithm that follows from total unimodularity. Finally, we show strong hardness for the well-known problem of finding a path with minimum forbidden pairs, which in a sense can be considered the dual to the checkpoint problem. Despite various works on this problem, hardness of approximation was not known prior to this work. We show that the problem cannot be approximated within c n for some constant c > 0, unless P = NP. This is the strongest type of hardness possible. It carries over to directed acyclic graphs and is a huge improvement over the plain NP -hardness of Gabow [H. N. Gabow, Finding paths and cycles of superpolylogarithmic length, SIAM J. Comput. 36 (6) (2007) 1648–1671].

Details DOI

TCS Journal 2011 Journal Article

Approximating some network design problems with node costs

  • Guy Kortsarz
  • Zeev Nutov

We study several multi-criteria undirected network design problems with node costs and lengths. All these problems are related to the Multicommodity Buy at Bulk (MBB) problem in which we are given a graph G = ( V, E ), demands { d s t: s, t ∈ V }, and a family { c v: v ∈ V } of subadditive cost functions. For every s, t ∈ V we seek to send d s t flow units from s to t, so that ∑ v c v ( f v ) is minimized, where f v is the total amount of flow through v. It is shown in Andrews and Zhang (2002) [2] that with a loss of 2 − ε in the ratio, we may assume that each s t -flow is unsplittable, namely, uses only one path. In the Multicommodity Cost–Distance (MCD) problem we are also given lengths { ℓ ( v ): v ∈ V }, and seek a subgraph H of G that minimizes c ( H ) + ∑ s, t ∈ V d s t ⋅ ℓ H ( s, t ), where ℓ H ( s, t ) is the minimum ℓ -length of an s t -path in H. The approximability of these two problems is equivalent up to a factor 2 − ε [2]. We give an O ( log 3 n ) -approximation algorithm for both problems for the case of the demands polynomial in n. The previously best known approximation ratio for these problems was O ( log 4 n ) (Chekuri et al. , 2006, 2007) [5, 6]. We also consider the Maximum Covering Tree (MaxCT) problem which is closely related to MBB: given a graph G = ( V, E ), costs { c ( v ): v ∈ V }, profits { p ( v ): v ∈ V }, and a bound C, find a subtree T of G with c ( T ) ≤ C and p ( T ) maximum. The best known approximation algorithm for MaxCT (Moss and Rabani, 2001) [18] computes a tree T with c ( T ) ≤ 2 C and p ( T ) = Ω ( opt / log n ). We provide the first nontrivial lower bound on approximation by proving that the problem admits no better than Ω ( 1 / ( log log n ) ) approximation assuming NP ⊈ Quasi(P). This holds true even if the solution is allowed to violate the budget by a constant ρ, as was done in [18] with ρ = 2. Our result disproves a conjecture of [18]. Another problem related to MBB is the Shallow Light Steiner Tree (SLST) problem, in which we are given a graph G = ( V, E ), costs { c ( v ): v ∈ V }, lengths { ℓ ( v ): v ∈ V }, a set U ⊆ V of terminals, and a bound L. The goal is to find a subtree T of G containing U with diam ℓ ( T ) ≤ L and c ( T ) minimum. We give an algorithm that computes a tree T with c ( T ) = O ( log 2 n ) ⋅ opt and diam ℓ ( T ) = O ( log n ) ⋅ L. Previously, a polylogarithmic bicriteria approximation was known only for the case of edge costs and edge lengths.

Details DOI

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

STOC Conference 2004 Conference Paper

Approximation algorithm for k-node connected subgraphs via critical graphs

  • Guy Kortsarz
  • Zeev Nutov

We present two new approximation algorithms for the problem of finding a k -node connected spanning subgraph (directed or undirected) of minimum cost. The best known approximation guarantees for this problem were O (min ( k , n /√ n - k )) for both directed and undirected graphs, and O (ln k ) for undirected graphs with n ≥ 6 k 2 , where n is the number of nodes in the input graph. Our first algorithm has approximation ratio O ( k / n - k ln 2 k , which is O (ln 2 k ) except for very large values of k , namely, k = n - o ( n ). This algorithm is based on a new result on l -connected p -critical graphs, which is of independent interest in the context of graph theory. Our second algorithm uses the primal-dual method and has approximation ratio O (√ n ln k ) for all values of n,k . Combining these two gives an algorithm with approximation ratio O (ln k • min (√ k , k / n - k ln k )), which asymptotically improves the best known approximation guarantee for directed graphs for all values of n,k , and for undirected graphs for k > √ n ⁄6. Moreover, this is the first algorithm that has an approximation guarantee better than Θ( k ) for all values of n,k . Our approximation ratio also provides an upper bound on the integrality gap of the standard LP-relaxation to the problem.As a byproduct, we also get the following result which is of independent interest. To get a faster implementation of our algorithms, we consider the problem of adding a minimum-cost edge set to increase the outconnectivity of a directed graph by Δ a graph is said to be l -outconnected from its node r if it contains l internally disjoint paths from r to any other node. The best known time complexity for the later problem is O ( m 3 ). For the particular case of Δ=1, we give a primal-dual algorithm with running time O ( m 2 ).

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

I&C Journal 2003 Journal Article

Multicoloring trees

  • Magnús M. Halldórsson
  • Guy Kortsarz
  • Andrzej Proskurowski
  • Ravit Salman
  • Hadas Shachnai
  • Jan Arne Telle

Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case.

Details DOI

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

TCS Journal 2001 Journal Article

Generalized submodular cover problems and applications

  • Judit Bar-Ilan
  • Guy Kortsarz
  • David Peleg

The greedy approach has been successfully applied in the past to produce logarithmic ratio approximations to NP-hard problems under certain conditions. The problems for which these conditions hold are known as submodular cover problems. The current paper 3 3 A preliminary version of this paper has appeared as an extended abstract in Proc. 4th Israel Symp. on the Theory of Computing and Systems, Jerusalem, Israel, June 1996. extends the applicability of the greedy approach to wider classes of problems. The usefulness of our extensions is illustrated by giving new approximate solutions for two different types of problems. The first problem is that of finding the spanning tree of minimum weight among those whose diameter is bounded by D. A logarithmic ratio approximation algorithm is given for the cases of D=4 and 5. This approximation ratio is also proved to be the best possible, unless P=NP. The second type involves some (known and new) center selection problems, for which new logarithmic ratio approximation algorithms are given. Again, it is shown that the ratio must be at least logarithmic unless P=NP.

Details DOI

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
v2026.09.13