Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > APPROXIMATION ALGORITHMS:
Reports tagged with Approximation Algorithms:
TR95-003 | 1st January 1995
Marek Karpinski, Alexander Zelikovsky

#### 1.757 and 1.267-Approximation Algorithms for the Network and and Rectilinear Steiner Tree Problems

The Steiner tree problem requires to find a shortest tree connection
a given set of terminal points in a metric space. We suggest a better
and fast heuristic for the Steiner problem in graphs and in
rectilinear plane. This heuristic finds a Steiner tree at ... more >>>

TR95-023 | 16th May 1995
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh Vazirani

#### On Syntactic versus Computational views of Approximability

We attempt to reconcile the two distinct views of approximation
classes: syntactic and computational.
Syntactic classes such as MAX SNP allow for clean complexity-theoretic
results and natural complete problems, while computational classes such
as APX allow us to work with problems whose approximability is
well-understood. Our results give a computational ... more >>>

TR95-030 | 20th June 1995
Marek Karpinski, Alexander Zelikovsky

#### New Approximation Algorithms for the Steiner Tree Problems

The Steiner tree problem asks for the shortest tree connecting
a given set of terminal points in a metric space. We design
new approximation algorithms for the Steiner tree problems
using a novel technique of choosing Steiner points in dependence
on the possible deviation from ... more >>>

TR95-053 | 15th October 1995
Petr Slavik

#### Improved Performance of the Greedy Algorithm for the Minimum Set Cover and Minimum Partial Cover Problems

We establish significantly improved bounds on the performance of the greedy
algorithm for approximating MINIMUM SET COVER and MINIMUM PARTIAL COVER. Our
improvements result from a new approach to both problems. In particular,
(a) we improve the known bound on the performance ratio of the greedy ... more >>>

TR96-057 | 18th November 1996
Oded Goldreich, Dana Ron

#### Property Testing and its connection to Learning and Approximation

In this paper, we consider the question of determining whether
a function $f$ has property $P$ or is $\e$-far from any
function with property $P$.
The property testing algorithm is given a sample of the value
of $f$ on instances drawn according to some distribution.
In some cases,
more >>>

TR96-062 | 3rd December 1996
Sanjeev Khanna, Madhu Sudan, David P. Williamson

#### A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

In this paper we study the approximability of boolean constraint
satisfaction problems. A problem in this class consists of some
collection of constraints'' (i.e., functions
$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set
of constraints applied to specified subsets of $n$ boolean
variables. Schaefer earlier ... more >>>

TR96-064 | 11th December 1996
Sanjeev Khanna, Madhu Sudan, Luca Trevisan

#### Constraint satisfaction: The approximability of minimization problems.

This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F ... more >>>

TR97-001 | 8th January 1997
Marco Cesati, Luca Trevisan

#### On the Efficiency of Polynomial Time Approximation Schemes

A polynomial time approximation scheme (PTAS) for an optimization
problem $A$ is an algorithm that on input an instance of $A$ and
$\epsilon > 0$ finds a $(1+\epsilon)$-approximate solution in time
that is polynomial for each fixed $\epsilon$. Typical running times
are $n^{O(1/\epsilon)}$ or $2^{1/\epsilon^{O(1)}} ... more >>> TR97-004 | 19th February 1997 Marek Karpinski, Alexander Zelikovsky #### Approximating Dense Cases of Covering Problems Comments: 1 We study dense instances of several covering problems. An instance of the set cover problem with$m$sets is dense if there is$\epsilon>0$such that any element belongs to at least$\epsilon m$sets. We show that the dense set cover problem can be approximated with ... more >>> TR97-017 | 5th May 1997 Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky #### An Approximation Algorithm for the Bandwidth Problem on Dense Graphs The bandwidth problem is the problem of numbering the vertices of a given graph$G$such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and is known to be NP-complete Papadimitriou [Pa76]. Only few special cases ... more >>> TR97-024 | 9th June 1997 Marek Karpinski #### Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems We survey recent results on the existence of polynomial time approximation schemes for some dense instances of NP-hard optimization problems. We indicate further some inherent limits for existence of such schemes for some other dense instances of the optimization problems. more >>> TR97-040 | 17th September 1997 Dorit Dor, Shay Halperin, Uri Zwick #### All Pairs Almost Shortest Paths Let G=(V,E) be an unweighted undirected graph on n vertices. A simple argument shows that computing all distances in G with an additive one-sided error of at most 1 is as hard as Boolean matrix multiplication. Building on recent work of Aingworth, Chekuri and Motwani, we describe an \tilde{O}(min{n^{3/2}m^{1/2},n^{7/3}) time more >>> TR97-041 | 18th September 1997 Marek Karpinski, Juergen Wirtgen #### On Approximation Hardness of the Bandwidth Problem The bandwidth problem is the problem of enumerating the vertices of a given graph$G$such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications and is ... more >>> TR97-056 | 1st December 1997 Oded Goldreich #### Combinatorial Property Testing (a survey). Comments: 1 We consider the question of determining whether a given object has a predetermined property or is far'' from any object having the property. Specifically, objects are modeled by functions, and distance between functions is measured as the fraction of the domain on which the functions differ. We ... more >>> TR98-014 | 6th February 1998 Gunter Blache, Marek Karpinski, Juergen Wirtgen #### On Approximation Intractability of the Bandwidth Problem The bandwidth problem is the problem of enumerating the vertices of a given graph$G$such that the maximum difference between the numbers of adjacent vertices is minimal. The problem has a long history and a number of applications. There was not ... more >>> TR98-029 | 27th May 1998 Piotr Berman, Marek Karpinski #### On Some Tighter Inapproximability Results We prove a number of improved inaproximability results, including the best up to date explicit approximation thresholds for MIS problem of bounded degree, bounded occurrences MAX-2SAT, and bounded degree Node Cover. We prove also for the first time inapproximability of the problem of Sorting by ... more >>> TR98-031 | 4th May 1998 Dimitris Fotakis, Paul Spirakis #### Graph Properties that Facilitate Travelling In this work, we study two special cases of the metric Travelling Salesman Problem, Graph TSP and TSP(1,2). At first, we show that dense instances of TSP(1,2) and Graph TSP are essentially as hard to approximate as general instances of TSP(1,2). Next, we present an NC algorithm for TSP(1,2) that ... more >>> TR98-065 | 6th November 1998 Piotr Berman, Marek Karpinski #### On Some Tighter Inapproximability Results, Further Improvements Improved inaproximability results are given, including the best up to date explicit approximation thresholds for bounded occurence satisfiability problems, like MAX-2SAT and E2-LIN-2, and problems in bounded degree graphs, like MIS, Node Cover and MAX CUT. We prove also for the first time inapproximability more >>> TR99-029 | 31st August 1999 Ilya Dumer, Daniele Micciancio, Madhu Sudan #### Hardness of approximating the minimum distance of a linear code We show that the minimum distance of a linear code (or equivalently, the weight of the lightest codeword) is not approximable to within any constant factor in random polynomial time (RP), unless NP equals RP. Under the stronger assumption that NP is not contained in RQP (random ... more >>> TR99-039 | 24th September 1999 Johan Håstad #### On approximating CSP-B We prove that any constraint satisfaction problem where each variable appears a bounded number of times admits a nontrivial polynomial time approximation algorithm. more >>> TR00-007 | 14th December 1999 Pavlos S. Efraimidis, Paul Spirakis #### Randomized Approximation Schemes for Scheduling Unrelated Parallel Machines The problem of Scheduling$n$Independent Jobs on$m$Unrelated Parallel Machines, when$m$is fixed, is considered. The standard problem of minimizing the makespan of the schedule (SUM) and the bicriteria problem of scheduling with bounded makespan and cost (SUMC), are addressed, and randomized fully linear time more >>> TR00-019 | 20th March 2000 Edward Hirsch #### Worst-case time bounds for MAX-k-SAT w.r.t. the number of variables using local search During the past three years there was an explosion of algorithms solving MAX-SAT and MAX-2-SAT in worst-case time of the order c^K, where c<2 is a constant, and K is the number of clauses in the input formula. Such bounds w.r.t. the number of variables instead of the number of ... more >>> TR00-021 | 19th April 2000 Uriel Feige, Marek Karpinski, Michael Langberg #### Improved Approximation of MAX-CUT on Graphs of Bounded Degree We analyze the addition of a simple local improvement step to various known randomized approximation algorithms. Let$\alpha \simeq 0.87856$denote the best approximation ratio currently known for the Max Cut problem on general graphs~\cite{GW95}. We consider a semidefinite relaxation of the Max Cut problem, round it using the ... more >>> TR00-043 | 21st June 2000 Uriel Feige, Marek Karpinski, Michael Langberg #### A Note on Approximating MAX-BISECTION on Regular Graphs We design a$0.795$approximation algorithm for the Max-Bisection problem restricted to regular graphs. In the case of three regular graphs our results imply an approximation ratio of$0.834$. more >>> TR00-047 | 29th June 2000 Tobias Polzin, Siavash Vahdati Daneshmand #### Primal-Dual Approaches to the Steiner Problem We study several old and new algorithms for computing lower and upper bounds for the Steiner problem in networks using dual-ascent and primal-dual strategies. These strategies have been proven to be very useful for the algorithmic treatment of the Steiner problem. We show that none of the known algorithms ... more >>> TR00-051 | 14th July 2000 Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas #### Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree$k$-regular graphs for ... more >>> TR00-064 | 29th August 2000 Klaus Jansen, Marek Karpinski, Andrzej Lingas #### A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs The Max-Bisection and Min-Bisection are the problems of finding partitions of the vertices of a given graph into two equal size subsets so as to maximize or minimize, respectively, the number of edges with exactly one endpoint in each subset. In this paper we design the first ... more >>> TR00-073 | 28th August 2000 Venkatesan Guruswami, Sanjeev Khanna #### On the Hardness of 4-coloring a 3-colorable Graph We give a new proof showing that it is NP-hard to color a 3-colorable graph using just four colors. This result is already known (Khanna, Linial, Safra 1992), but our proof is novel as it does not rely on the PCP theorem, while the earlier one does. This ... more >>> TR00-079 | 12th September 2000 Mark Jerrum, Eric Vigoda #### A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries. more >>> TR00-091 | 21st December 2000 Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski #### Approximability of Dense Instances of NEAREST CODEWORD Problem We give a polynomial time approximation scheme (PTAS) for dense instances of the NEAREST CODEWORD problem. more >>> TR01-025 | 28th March 2001 Piotr Berman, Marek Karpinski #### Approximating Minimum Unsatisfiability of Linear Equations We consider the following optimization problem: given a system of m linear equations in n variables over a certain field, a feasible solution is any assignment of values to the variables, and the minimized objective function is the number of equations that are not satisfied. For ... more >>> TR01-026 | 3rd April 2001 Piotr Berman, Marek Karpinski #### Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for graphs. MIN-LIN2 is an optimization problem for a given system of linear equations mod 2 to construct a solution that satisfies the minimum number of them. E3-OCC-MIN-E3-LIN2 ... more >>> TR01-034 | 30th April 2001 Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski #### Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN-CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT-formulas, ... more >>> TR01-042 | 31st May 2001 Marek Karpinski #### Approximating Bounded Degree Instances of NP-Hard Problems We present some of the recent results on computational complexity of approximating bounded degree combinatorial optimization problems. In particular, we present the best up to now known explicit nonapproximability bounds on the very small degree optimization problems which are of particular importance on the intermediate stages ... more >>> TR01-047 | 3rd July 2001 Piotr Berman, Sridhar Hannenhalli, Marek Karpinski #### 1.375-Approximation Algorithm for Sorting by Reversals Analysis of genomes evolving by inversions leads to a general combinatorial problem of {\em Sorting by Reversals}, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. This combinatorial problem has a long history, and a number of other motivations. It was studied in a great ... more >>> TR01-053 | 17th July 2001 Piotr Berman, Marek Karpinski #### Efficient Amplifiers and Bounded Degree Optimization This paper studies the existence of efficient (small size) amplifiers for proving explicit inaproximability results for bounded degree and bounded occurrence combinatorial optimization problems, and gives an explicit construction for such amplifiers. We use this construction also later to improve the currently best known approximation lower bounds more >>> TR01-063 | 5th August 2001 Michal Parnas, Dana Ron, Alex Samorodnitsky #### Proclaiming Dictators and Juntas or Testing Boolean Formulae Revisions: 1 We consider the problem of determining whether a given function f : {0,1}^n -> {0,1} belongs to a certain class of Boolean functions F or whether it is far from the class. More precisely, given query access to the function f and given a distance parameter epsilon, we would ... more >>> TR01-097 | 11th December 2001 Piotr Berman, Marek Karpinski #### Improved Approximations for General Minimum Cost Scheduling We give improved trade-off results on approximating general minimum cost scheduling problems. more >>> TR01-100 | 14th December 2001 Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski #### Random Sampling and Approximation of MAX-CSP Problems We present a new efficient sampling method for approximating r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on n variables up to an additive error \epsilon n^r.We prove a new general paradigm in that it suffices, for a given set of constraints, to pick a small uniformly random ... more >>> TR02-018 | 22nd March 2002 Piotr Berman, Marek Karpinski, Yakov Nekrich #### Approximating Huffman Codes in Parallel In this paper we present some new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and ... more >>> TR02-041 | 2nd July 2002 Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon #### A Polynomial Time Approximation Scheme for Metric MIN-BISECTION We design a polynomial time approximation scheme (PTAS) for the problem of Metric MIN-BISECTION of dividing a given finite metric space into two halves so as to minimize the sum of distances across that partition. The method of solution depends on a new metric placement partitioning ... more >>> TR02-044 | 16th July 2002 Wenceslas Fernandez de la Vega, Marek Karpinski #### A Polynomial Time Approximation Scheme for Subdense MAX-CUT We prove that the subdense instances of MAX-CUT of average degree Omega(n/logn) posses a polynomial time approximation scheme (PTAS). We extend this result also to show that the instances of general 2-ary maximum constraint satisfaction problems (MAX-CSP) of the same average density have PTASs. Our results ... more >>> TR02-046 | 16th July 2002 Marek Karpinski #### On Approximability of Minimum Bisection Problem We survey some recent results on the complexity of computing approximate solutions for instances of the Minimum Bisection problem and formulate some intriguing and still open questions about the approximability status of that problem. Some connections to other optimization problems are also indicated. more >>> TR02-070 | 13th December 2002 Wenceslas Fernandez de la Vega, Marek Karpinski #### 9/8-Approximation Algorithm for Random MAX-3SAT Revisions: 1 We prove that MAX-3SAT can be approximated in polynomial time within a factor 9/8 on random instances. more >>> TR02-073 | 12th December 2002 Janka Chlebíková, Miroslav Chlebik #### Approximation Hardness for Small Occurrence Instances of NP-Hard Problem The paper contributes to the systematic study (started by Berman and Karpinski) of explicit approximability lower bounds for small occurrence optimization problems. We present parametrized reductions for some packing and covering problems, including 3-Dimensional Matching, and prove the best known inapproximability results even for highly restricted versions of ... more >>> TR03-008 | 11th February 2003 Piotr Berman, Marek Karpinski #### Improved Approximation Lower Bounds on Small Occurrence Optimization We improve a number of approximation lower bounds for bounded occurrence optimization problems like MAX-2SAT, E2-LIN-2, Maximum Independent Set and Maximum-3D-Matching. more >>> TR03-031 | 8th April 2003 Birgit Schelm #### Average-Case Complexity Theory of Approximation Problems Both average-case complexity and the study of the approximability properties of NP-optimization problems are well established and active fields of research. By applying the notion of average-case complexity to approximation problems we provide a formal framework that allows the classification of NP-optimization problems according to their average-case approximability. Thus, known ... more >>> TR03-032 | 16th April 2003 Andreas Björklund, Thore Husfeldt, Sanjeev Khanna #### Approximating Longest Directed Path We investigate the hardness of approximating the longest path and the longest cycle in directed graphs on$n$vertices. We show that neither of these two problems can be polynomial time approximated within$n^{1-\epsilon}$for any$\epsilon>0$unless$\text{P}=\text{NP}$. In particular, the result holds for more >>> TR03-035 | 21st May 2003 Eran Halperin, Guy Kortsarz, Robert Krauthgamer #### Tight lower bounds for the asymmetric k-center problem In the {\sc$k$-center} problem, the input is a bound$k$and$n$points with the distance between every two of them, such that the distances obey the triangle inequality. The goal is to choose a set of$k$points to serve as centers, so that the maximum distance ... more >>> TR03-038 | 15th May 2003 Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Seffi Naor #### Asymmetric k-center is log^*n-hard to Approximate We show that the asymmetric$k$-center problem is$\Omega(\log^* n)$-hard to approximate unless${\rm NP} \subseteq {\rm DTIME}(n^{poly(\log \log n)})$. Since an$O(\log^* n)$-approximation algorithm is known for this problem, this essentially resolves the approximability of this problem. This is the first natural problem whose approximability threshold does not polynomially ... more >>> TR03-056 | 29th July 2003 Piotr Berman, Marek Karpinski #### Approximability of Hypergraph Minimum Bisection We prove that the problems of minimum bisection on k-uniform hypergraphs are almost exactly as hard to approximate, up to the factor k/3, as the problem of minimum bisection on graphs. On a positive side, our argument gives also the first approximation ... more >>> TR04-010 | 26th January 2004 Michal Parnas, Dana Ron, Ronitt Rubinfeld #### Tolerant Property Testing and Distance Approximation A standard property testing algorithm is required to determine with high probability whether a given object has property P or whether it is \epsilon-far from having P, for any given distance parameter \epsilon. An object is said to be \epsilon-far from having ... more >>> TR04-051 | 10th June 2004 Zdenek Dvorák, Daniel Král, Ondrej Pangrác #### Locally consistent constraint satisfaction problems An instance of a constraint satisfaction problem is$l$-consistent if any$l$constraints of it can be simultaneously satisfied. For a set$\Pi$of constraint types,$\rho_l(\Pi)$denotes the largest ratio of constraints which can be satisfied in any$l$-consistent instance composed by constraints from the set$\Pi$. In the ... more >>> TR04-119 | 8th December 2004 Uriel Feige, Daniel Reichman #### On The Hardness of Approximating Max-Satisfy Max-Satisfy is the problem of finding an assignment that satisfies the maximum number of equations in a system of linear equations over$\mathbb{Q}$. We prove that unless NP$\subseteq $BPP there is no polynomial time algorithm for the problem achieving an approximation ratio of$1/n^{1-\epsilon}$, where$n$is the number of ... more >>> TR05-029 | 2nd March 2005 Frank Neumann, Marco Laumanns #### Speeding Up Approximation Algorithms for NP-hard Spanning Forest Problems by Multi-objective Optimization Revisions: 1 We give faster approximation algorithms for the generalization of two NP-hard spanning tree problems. First, we investigate the problem of minimizing the degree of minimum spanning forests. The task is to compute for each number of connected components a minimum spanning forest whose degree is as small as possible. Fischer more >>> TR05-069 | 11th July 2005 Piotr Berman, Marek Karpinski #### 8/7-Approximation Algorithm for (1,2)-TSP Revisions: 2 We design a polynomial time 8/7-approximation algorithm for the Traveling Salesman Problem in which all distances are either one or two. This improves over the best known approximation factor of 7/6 for that problem. As a direct application we get a 7/6-approximation algorithm for the Maximum Path Cover Problem, similarily ... more >>> TR05-094 | 9th August 2005 Michal Parnas, Dana Ron #### On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms Revisions: 1 We consider the problem of estimating the size,$VC(G)$, of a minimum vertex cover of a graph$G$, in sublinear time, by querying the incidence relation of the graph. We say that an algorithm is an$(\alpha,\eps)$-approximation algorithm if it outputs with high probability an estimate$\widehat{VC}$such that ... more >>> TR05-125 | 2nd November 2005 Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam Smith #### Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size We raise the question of approximating compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present algorithms and lower bounds for approximating compressibility with respect to ... more >>> TR05-131 | 7th November 2005 Don Coppersmith, Lisa Fleischer, Atri Rudra #### Ordering by weighted number of wins gives a good ranking for weighted tournaments We consider the following simple algorithm for feedback arc set problem in weighted tournaments --- order the vertices by their weighted indegrees. We show that this algorithm has an approximation guarantee of$5$if the weights satisfy \textit{probability constraints} (for any pair of vertices$u$and$v$,$w_{uv}+w_{vu}=1$). Special cases ... more >>> TR06-045 | 13th March 2006 Jan Arpe, Bodo Manthey #### Approximability of Minimum AND-Circuits Revisions: 1 Given a set of monomials, the Minimum AND-Circuit problem asks for a circuit that computes these monomials using AND-gates of fan-in two and being of minimum size. We prove that the problem is not polynomial time approximable within a factor of less than 1.0051 unless P = NP, even if more >>> TR06-101 | 22nd August 2006 Wenceslas Fernandez de la Vega, Marek Karpinski #### Approximation Complexity of Nondense Instances of MAX-CUT We prove existence of approximation schemes for instances of MAX-CUT with$\Omega(\frac{n^2}{\Delta})$edges which work in$2^{O^\thicksim(\frac{\Delta}{\varepsilon^2})}n^{O(1)}$time. This entails in particular existence of quasi-polynomial approximation schemes (QPTASs) for mildly sparse instances of MAX-CUT with$\Omega(\frac{n^2}{\operatorname{polylog} n})$edges. The result depends on new sampling method for smoothed linear programs that ... more >>> TR06-124 | 25th September 2006 Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski #### Approximation of Global MAX-CSP Problems We study the problem of absolute approximability of MAX-CSP problems with the global constraints. We prove existence of an efficient sampling method for the MAX-CSP class of problems with linear global constraints and bounded feasibility gap. It gives for the first time a polynomial in epsilon^-1 sample complexity bound for ... more >>> TR06-152 | 6th December 2006 Konstantinos Georgiou, Avner Magen, Iannis Tourlakis #### Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy We prove that the integrality gap after tightening the standard LP relaxation for Vertex Cover with Omega(sqrt(log n/log log n)) rounds of the SDP LS+ system is 2-o(1). more >>> TR07-011 | 19th December 2006 Bodo Manthey #### On Approximating Restricted Cycle Covers A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L. The weight of a cycle cover of an edge-weighted graph ... more >>> TR07-101 | 10th September 2007 Patrick Briest, Martin Hoefer, Piotr Krysta #### Stackelberg Network Pricing Games Revisions: 1 We study a multi-player one-round game termed Stackelberg Network Pricing Game, in which a leader can set prices for a subset of m pricable edges in a graph. The other edges have a fixed cost. Based on the leader's decision one or more followers optimize a polynomial-time solvable combinatorial minimization ... more >>> TR07-106 | 10th September 2007 Yijia Chen, Martin Grohe, Magdalena Grüber #### On Parameterized Approximability Combining classical approximability questions with parameterized complexity, we introduce a theory of parameterized approximability. The main intention of this theory is to deal with the efficient approximation of small cost solutions for optimisation problems. more >>> TR07-119 | 5th December 2007 Piotr Berman, Bhaskar DasGupta, Marek Karpinski #### Approximating Transitive Reductions for Directed Networks We consider <i>minimum equivalent digraph</i> (<i>directed network</i>) problem (also known as the <i>strong transitive reduction</i>), its maximum optimization variant, and some extensions of those two types of problems. We prove the existence of polynomial time approximation algorithms with ratios 1.5 for all the minimization problems and 2 for all the ... more >>> TR08-094 | 10th October 2008 Piotr Berman, Marek Karpinski, Alexander Zelikovsky #### 1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem. more >>> TR08-101 | 20th November 2008 Marek Karpinski, Warren Schudy #### Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>> TR09-076 | 19th August 2009 Christian Glaßer, Christian Reitwießner, Maximilian Witek #### Improved and Derandomized Approximations for Two-Criteria Metric Traveling Salesman Revisions: 1 We improve and derandomize the best known approximation algorithm for the two-criteria metric traveling salesman problem (2-TSP). More precisely, we construct a deterministic 2-approximation which answers an open question by Manthey. Moreover, we show that 2-TSP is randomized$(3/2+\epsilon ,2)$-approximable, and we give the first randomized approximations for the two-criteria ... more >>> TR10-041 | 11th March 2010 Sanjeev Arora, Russell Impagliazzo, William Matthews, David Steurer #### Improved Algorithms for Unique Games via Divide and Conquer We present two new approximation algorithms for Unique Games. The first generalizes the results of Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi who give polynomial time approximation algorithms for graphs with high conductance. We give a polynomial time algorithm assuming only good local conductance, i.e. high conductance for small subgraphs. ... more >>> TR10-132 | 18th August 2010 Mahdi Cheraghchi, Johan Håstad, Marcus Isaksson, Ola Svensson #### Approximating Linear Threshold Predicates We study constraint satisfaction problems on the domain$\{-1,1\}$, where the given constraints are homogeneous linear threshold predicates. That is, predicates of the form$\mathrm{sgn}(w_1 x_1 + \cdots + w_n x_n)$for some positive integer weights$w_1, \dots, w_n$. Despite their simplicity, current techniques fall short of providing a classification ... more >>> TR11-156 | 23rd November 2011 Marek Karpinski, Richard Schmied #### Improved Lower Bounds for the Shortest Superstring and Related Problems Revisions: 1 We study the approximation hardness of the Shortest Superstring, the Maximal Compression and the Maximum Asymmetric Traveling Salesperson (MAX-ATSP) problem. We introduce a new reduction method that produces strongly restricted instances of the Shortest Superstring problem, in which the maximal orbit size is eight (with no ... more >>> TR12-008 | 30th January 2012 Marek Karpinski, Richard Schmied #### On Approximation Lower Bounds for TSP with Bounded Metrics Revisions: 1 We develop a new method for proving explicit approximation lower bounds for TSP problems with bounded metrics improving on the best up to now known bounds. They almost match the best known bounds for unbounded metric TSP problems. In particular, we prove the best known lower bound for TSP with ... more >>> TR12-170 | 30th November 2012 Scott Aaronson, Travis Hance #### Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent Around 2002, Leonid Gurvits gave a striking randomized algorithm to approximate the permanent of an n×n matrix A. The algorithm runs in O(n^2/?^2) time, and approximates Per(A) to within ±?||A||^n additive error. A major advantage of Gurvits's algorithm is that it works for arbitrary matrices, not just for nonnegative matrices. ... more >>> TR13-045 | 26th March 2013 Marek Karpinski, Michael Lampis, Richard Schmied #### New Inapproximability Bounds for TSP In this paper, we study the approximability of the metric Traveling Salesman Problem, one of the most widely studied problems in combinatorial optimization. Currently, the best known hardness of approximation bounds are 185/184 for the symmetric case (due to Lampis) and 117/116 for the asymmetric case (due to Papadimitriou and ... more >>> TR13-066 | 25th April 2013 Marek Karpinski, Richard Schmied #### Approximation Hardness of Graphic TSP on Cubic Graphs We prove explicit approximation hardness results for the Graphic TSP on cubic and subcubic graphs as well as the new inapproximability bounds for the corresponding instances of the (1,2)-TSP. The proof technique uses new modular constructions of simulating gadgets for the restricted cubic and subcubic instances. The modular constructions used ... more >>> TR13-095 | 24th June 2013 Uriel Feige, Rani Izsak #### Welfare Maximization and the Supermodular Degree Given a set of items and a collection of players, each with a nonnegative monotone valuation set function over the items, the welfare maximization problem requires that every item be allocated to exactly one player, and one wishes to maximize the sum of values obtained by the players, as computed ... more >>> TR15-097 | 16th June 2015 Marek Karpinski #### Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies We present in this paper some of the recent techniques and methods for proving best up to now explicit approximation hardness bounds for metric symmetric and asymmetric Traveling Salesman Problem (TSP) as well as related problems of Shortest Superstring and Maximum Compression. We attempt to shed some light on the ... more >>> TR20-145 | 23rd September 2020 Andrew Drucker #### An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against Nature "Games against Nature" [Papadimitriou '85] are two-player games of perfect information, in which one player's moves are made randomly (here, uniformly); the final payoff to the non-random player is given by some$[0, 1]$-valued function of the move history. Estimating the value of such games under optimal play, and computing ... more >>> TR21-141 | 28th September 2021 Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz #### On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization Revisions: 1 We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function$f : D \to \mathbb{R}_{\geq 0}$by making oracle queries to a heuristic$h_f\$ satisfying
\[
\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot ... more >>>

ISSN 1433-8092 | Imprint