Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MAREK KARPINSKI:
All reports by Author Marek Karpinski:

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 >>>


TR14-065 | 2nd May 2014
Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

Approximate Counting of Matchings in $(3,3)$-Hypergraphs

We design a fully polynomial time approximation scheme (FPTAS) for counting the number of matchings (packings) in arbitrary 3-uniform hypergraphs of maximum degree three, referred to as $(3,3)$-hypergraphs. It is the first polynomial time approximation scheme for that problem, which includes also, as a special case, the 3D Matching counting ... more >>>


TR13-103 | 24th July 2013
Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

Generalized Wong sequences and their applications to Edmonds' problems

We design two deterministic polynomial time algorithms for variants of a problem introduced by Edmonds in 1967: determine the rank of a matrix $M$ whose entries are homogeneous linear polynomials over the integers. Given a linear subspace $\mathcal{B}$ of the $n \times n$ matrices over some field $\mathbb{F}$, we consider ... 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-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 >>>


TR12-176 | 14th December 2012
Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

We present a polynomial time dynamic programming algorithm for optimal partitions in the shortest path metric induced by a tree. This resolves, among other things, the exact complexity status of the optimal partition problems in one dimensional geometric metric settings. Our method of solution could be also of independent interest ... more >>>


TR12-068 | 25th May 2012
Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Deterministic Polynomial Factoring and Association Schemes

The problem of finding a nontrivial factor of a polynomial $f(x)$ over a finite field $\mathbb{F}_q$ has many known efficient, but randomized, algorithms. The deterministic complexity of this problem is a famous open question even assuming the generalized Riemann hypothesis (GRH). In this work we improve the state of the ... 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 >>>


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 >>>


TR11-098 | 11th July 2011
Marek Karpinski, Richard Schmied, Claus Viehmann

Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

more >>>

TR09-058 | 4th July 2009
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Deterministic Polynomial Time Algorithms for Matrix Completion Problems

We present new deterministic algorithms for several cases of the maximum rank matrix completion
problem (for short matrix completion), i.e. the problem of assigning values to the variables in
a given symbolic matrix as to maximize the resulting matrix rank. Matrix completion belongs to
the fundamental problems in computational complexity ... 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 >>>


TR08-099 | 19th November 2008
Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

Trading GRH for algebra: algorithms for factoring polynomials and related structures

In this paper we develop techniques that eliminate the need of the Generalized
Riemann Hypothesis (GRH) from various (almost all) known results about deterministic
polynomial factoring over finite fields. Our main result shows that given a
polynomial f(x) of degree n over a finite field k, we ... 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-043 | 12th April 2008
Gábor Ivanyos, Marek Karpinski, Nitin Saxena

Schemes for Deterministic Polynomial Factoring

In this work we relate the deterministic
complexity of factoring polynomials (over
finite
fields) to certain combinatorial objects we
call
m-schemes. We extend the known conditional
deterministic subexponential time polynomial
factoring algorithm for finite fields to get an
underlying m-scheme. We demonstrate ... 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 >>>


TR06-155 | 15th December 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

Trading Tensors for Cloning: Constant Time Approximation Schemes for Metric MAX-CSP

Revisions: 1

We construct the first constant time value approximation schemes (CTASs) for Metric and Quasi-Metric MAX-rCSP problems for any $r \ge 2$ in a preprocessed metric model of computation, improving over the previous results of [FKKV05] proven for the general core-dense MAX-rCSP problems. They entail also the first sublinear approximation schemes ... 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-104 | 25th August 2006
Wenceslas Fernandez de la Vega, Marek Karpinski

On the Sample Complexity of MAX-CUT

We give a simple proof for the sample complexity bound $O~(1/\epsilon^4)$ of absolute approximation of MAX-CUT. The proof depends on a new analysis method for linear programs (LPs) underlying MAX-CUT which could be also of independent interest.

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 >>>


TR05-151 | 7th December 2005
Magnus Bordewich, Martin Dyer, Marek Karpinski

Metric Construction, Stopping Times and Path Coupling.

In this paper we examine the importance of the choice of metric in path coupling, and the relationship of this to \emph{stopping time analysis}. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we prove a stronger theorem for path coupling ... 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-002 | 6th January 2005
Magnus Bordewich, Martin Dyer, Marek Karpinski

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

We give a new method for analysing the mixing time of a Markov chain using
path coupling with stopping times. We apply this approach to two hypergraph
problems. We show that the Glauber dynamics for independent sets in a
hypergraph mixes rapidly as long as the maximum degree $\Delta$ of ... more >>>


TR04-118 | 21st December 2004
Marek Karpinski, Yakov Nekrich

A Note on Traversing Skew Merkle Trees

We consider the problem of traversing skew (unbalanced) Merkle
trees and design an algorithm for traversing a skew Merkle tree
in time O(log n/log t) and space O(log n (t/log t)), for any choice
of parameter t\geq 2.
This algorithm can be of special interest in situations when
more >>>


TR04-111 | 30th November 2004
Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

Computational Complexity of Some Restricted Instances of 3SAT

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times.

more >>>

TR04-049 | 15th June 2004
Piotr Berman, Marek Karpinski, Yakov Nekrich

Optimal Trade-Off for Merkle Tree Traversal

We prove upper and lower bounds for computing Merkle tree
traversals, and display optimal trade-offs between time
and space complexity of that problem.

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 >>>


TR03-049 | 25th June 2003
Piotr Berman, Marek Karpinski, Alexander D. Scott

Approximation Hardness of Short Symmetric Instances of MAX-3SAT

We prove approximation hardness of short symmetric instances
of MAX-3SAT in which each literal occurs exactly twice, and
each clause is exactly of size 3. We display also an explicit
approximation lower bound for that problem. The bound two on
the number ... more >>>


TR03-022 | 11th April 2003
Piotr Berman, Marek Karpinski, Alexander D. Scott

Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

We study approximation hardness and satisfiability of bounded
occurrence uniform instances of SAT. Among other things, we prove
the inapproximability for SAT instances in which every clause has
exactly 3 literals and each variable occurs exactly 4 times,
and display an explicit ... 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 >>>

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-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-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-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-029 | 3rd June 2002
Marek Karpinski, Yakov Nekrich

Parallel Construction of Minimum Redundancy Length-Limited Codes

This paper presents new results on parallel constructions of the
length-limited prefix-free codes with the minimum redundancy.
We describe an algorithm for the construction of length-limited codes
that works in $O(L)$ time with $n$ processors for $L$ the
maximal codeword length.
We also describe an algorithm for a construction ... more >>>


TR02-025 | 26th April 2002
Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

Polynomial Time Approximation Schemes for Metric Min-Sum Clustering

We give polynomial time approximation schemes for the problem
of partitioning an input set of n points into a fixed number
k of clusters so as to minimize the sum over all clusters of
the total pairwise distances in a cluster. Our algorithms work
for arbitrary metric spaces as well ... 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 >>>


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 >>>


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-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-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-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-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-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-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 >>>


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 >>>

TR00-089 | 1st December 2000
Lars Engebretsen, Marek Karpinski

Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

The general asymmetric (and metric) TSP is known to be approximable
only to within an O(log n) factor, and is also known to be
approximable within a constant factor as soon as the metric is
bounded. In this paper we study the asymmetric and symmetric TSP
problems with bounded metrics ... 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-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-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-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-001 | 14th January 2000
Piotr Berman, Moses Charikar, Marek Karpinski

On-Line Load Balancing for Related Machines

We consider the problem of scheduling permanent jobs on related machines
in an on-line fashion. We design a new algorithm that achieves the
competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic
version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,
improving the previous competitive ratios ... more >>>


TR99-027 | 17th July 1999
Marek Karpinski, Igor E. Shparlinski

On the computational hardness of testing square-freeness of sparse polynomials

We show that deciding square-freeness of a sparse univariate
polynomial over the integer and over the algebraic closure of a
finite field is NP-hard. We also discuss some related open
problems about sparse polynomials.

more >>>

TR99-020 | 9th June 1999
Marek Karpinski

Randomized Complexity of Linear Arrangements and Polyhedra

We survey some of the recent results on the complexity of recognizing
n-dimensional linear arrangements and convex polyhedra by randomized
algebraic decision trees. We give also a number of concrete applications
of these results. In particular, we derive first nontrivial, in fact
quadratic, ... more >>>


TR99-009 | 26th March 1999
Marek Karpinski, Rustam Mubarakzjanov

A Note on Las Vegas OBDDs

We prove that the error-free (Las Vegas) randomized OBDDs
are computationally equivalent to the deterministic OBDDs.
In contrast, it is known the same is not true for the
Las Vegas read-once branching programs.

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 >>>


TR98-064 | 6th November 1998
Wenceslas Fernandez de la Vega, Marek Karpinski

Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

We give the first polynomial time approximability characterization
of dense weighted instances of MAX-CUT, and some other dense
weighted NP-hard problems in terms of their empirical weight
distributions. This gives also the first almost sharp
characterization of inapproximability of unweighted 0,1
MAX-BISECTION instances ... more >>>


TR98-038 | 9th July 1998
Marek Karpinski

On the Computational Power of Randomized Branching Programs

We survey some upper and lower bounds established recently on
the sizes of randomized branching programs computing explicit
boolean functions. In particular, we display boolean
functions on which randomized read-once ordered branching
programs are exponentially more powerful than deterministic
or nondeterministic read-$k$-times branching programs for ... 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-024 | 28th April 1998
Wenceslas Fernandez de la Vega, Marek Karpinski

On Approximation Hardness of Dense TSP and other Path Problems

TSP(1,2), the Traveling Salesman Problem with distances 1 and 2, is
the problem of finding a tour of minimum length in a complete
weighted graph where each edge has length 1 or 2. Let $d_o$ satisfy
$0<d_o<1/2$. We show that TSP(1,2) has no PTAS on the set ... 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-011 | 29th January 1998
Farid Ablayev, Marek Karpinski

A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs

We prove an exponential lower bound ($2^{\Omega(n/\log n)}$) on the
size of any randomized ordered read-once branching program
computing integer multiplication. Our proof depends on proving
a new lower bound on Yao's randomized one-way communication
complexity of certain boolean functions. It generalizes to some
other ... more >>>


TR98-004 | 13th January 1998
Farid Ablayev, Marek Karpinski

On the Power of Randomized Ordered Branching Programs

We introduce a model of a {\em randomized branching program}
in a natural way similar to the definition of a randomized circuit.
We exhibit an explicit boolean function
$f_{n}:\{0,1\}^{n}\to\{0,1\}$ for which we prove that:

1) $f_{n}$ can be computed by a polynomial size randomized
... 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-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-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-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 >>>


TR96-058 | 25th November 1996
Dima Grigoriev, Marek Karpinski

Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

We prove $\Omega (n^2)$ complexity \emph{lower bound} for the
general model of \emph{randomized computation trees} solving
the \emph{Knapsack Problem}, and more generally \emph{Restricted
Integer Programming}. This is the \emph{first nontrivial} lower
bound proven for this model of computation. The method of the ... more >>>


TR95-063 | 19th December 1995
Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

A Lower Bound for Randomized Algebraic Decision Trees

We extend the lower bounds on the depth of algebraic decision trees
to the case of {\em randomized} algebraic decision trees (with
two-sided error) for languages being finite unions of hyperplanes
and the intersections of halfspaces, solving a long standing open
problem. As an application, among ... more >>>


TR95-057 | 24th November 1995
Dima Grigoriev, Marek Karpinski, A. C. Yao

An Exponential Lower Bound on the Size of Algebraic Decision Trees for MAX

We prove an exponential lower bound on the size of any
fixed-degree algebraic decision tree for solving MAX, the
problem of finding the maximum of $n$ real numbers. This
complements the $n-1$ lower bound of Rabin \cite{R72} on
the depth of ... more >>>


TR95-055 | 24th November 1995
Marek Karpinski, Angus Macintyre

VC Dimension of Sigmoidal and General Pfaffian Networks

We introduce a new method for proving explicit upper bounds
on the VC Dimension of general functional basis networks,
and prove as an application, for the first time, that the
VC Dimension of analog neural networks with the sigmoidal
activation function $\sigma(y)=1/1+e^{-y}$ ... more >>>


TR95-054 | 24th November 1995
Farid Ablayev, Marek Karpinski

On the Power of Randomized Branching Programs

We define the notion of a randomized branching program in
the natural way similar to the definition of a randomized
circuit. We exhibit an explicit function $f_{n}$ for which
we prove that:
1) $f_{n}$ can be computed by polynomial size randomized
... 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-022 | 2nd May 1995
Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

Pattern-Matching for Strings with Short Descriptions

We consider strings which are succinctly described. The description
is in terms of straight-line programs in which the constants are
symbols and the only operation is the concatenation. Such
descriptions correspond to the systems of recurrences or to
context-free grammars generating single words. The descriptive ... more >>>


TR95-021 | 20th April 1995
Marek Karpinski, Rutger Verbeek

On Randomized Versus Deterministic Computation

In contrast to deterministic or nondeterministic computation, it is
a fundamental open problem in randomized computation how to separate
different randomized time classes (at this point we do not even know
how to separate linear randomized time from ${\mathcal O}(n^{\log n})$
randomized time) or how to ... more >>>


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 >>>


TR94-024 | 12th December 1994
Marek Karpinski, Angus Macintyre

Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks

We introduce a new method for proving explicit upper bounds on the VC
Dimension of general functional basis networks, and prove as an
application, for the first time, the VC Dimension of analog neural
networks with the sigmoid activation function $\sigma(y)=1/1+e^{-y}$
to ... more >>>




ISSN 1433-8092 | Imprint