All reports by Author Marek Karpinski:

__
TR15-097
| 16th June 2015
__

Marek Karpinski#### Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies

__
TR14-065
| 2nd May 2014
__

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska#### Approximate Counting of Matchings in $(3,3)$-Hypergraphs

__
TR13-103
| 24th July 2013
__

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha#### Generalized Wong sequences and their applications to Edmonds' problems

__
TR13-066
| 25th April 2013
__

Marek Karpinski, Richard Schmied#### Approximation Hardness of Graphic TSP on Cubic Graphs

__
TR13-045
| 26th March 2013
__

Marek Karpinski, Michael Lampis, Richard Schmied#### New Inapproximability Bounds for TSP

__
TR12-176
| 14th December 2012
__

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu#### Optimal Cuts and Partitions in Tree Metrics in Polynomial Time

__
TR12-068
| 25th May 2012
__

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Deterministic Polynomial Factoring and Association Schemes

__
TR12-008
| 30th January 2012
__

Marek Karpinski, Richard Schmied#### On Approximation Lower Bounds for TSP with Bounded Metrics

Revisions: 1

__
TR11-156
| 23rd November 2011
__

Marek Karpinski, Richard Schmied#### Improved Lower Bounds for the Shortest Superstring and Related Problems

Revisions: 1

__
TR11-098
| 11th July 2011
__

Marek Karpinski, Richard Schmied, Claus Viehmann#### Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs

__
TR09-058
| 4th July 2009
__

Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Deterministic Polynomial Time Algorithms for Matrix Completion Problems

__
TR08-101
| 20th November 2008
__

Marek Karpinski, Warren Schudy#### Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems

__
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

__
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

__
TR08-043
| 12th April 2008
__

Gábor Ivanyos, Marek Karpinski, Nitin Saxena#### Schemes for Deterministic Polynomial Factoring

__
TR07-119
| 5th December 2007
__

Piotr Berman, Bhaskar DasGupta, Marek Karpinski#### Approximating Transitive Reductions for Directed Networks

__
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

__
TR06-124
| 25th September 2006
__

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Approximation of Global MAX-CSP Problems

__
TR06-104
| 25th August 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### On the Sample Complexity of MAX-CUT

__
TR06-101
| 22nd August 2006
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Approximation Complexity of Nondense Instances of MAX-CUT

__
TR05-151
| 7th December 2005
__

Magnus Bordewich, Martin Dyer, Marek Karpinski#### Metric Construction, Stopping Times and Path Coupling.

__
TR05-069
| 11th July 2005
__

Piotr Berman, Marek Karpinski#### 8/7-Approximation Algorithm for (1,2)-TSP

Revisions: 2

__
TR05-002
| 6th January 2005
__

Magnus Bordewich, Martin Dyer, Marek Karpinski#### Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs

__
TR04-118
| 21st December 2004
__

Marek Karpinski, Yakov Nekrich#### A Note on Traversing Skew Merkle Trees

__
TR04-111
| 30th November 2004
__

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott#### Computational Complexity of Some Restricted Instances of 3SAT

__
TR04-049
| 15th June 2004
__

Piotr Berman, Marek Karpinski, Yakov Nekrich#### Optimal Trade-Off for Merkle Tree Traversal

__
TR03-056
| 29th July 2003
__

Piotr Berman, Marek Karpinski#### Approximability of Hypergraph Minimum Bisection

__
TR03-049
| 25th June 2003
__

Piotr Berman, Marek Karpinski, Alexander D. Scott#### Approximation Hardness of Short Symmetric Instances of MAX-3SAT

__
TR03-022
| 11th April 2003
__

Piotr Berman, Marek Karpinski, Alexander D. Scott#### Approximation Hardness and Satisfiability of Bounded Occurrence Instances of SAT

__
TR03-008
| 11th February 2003
__

Piotr Berman, Marek Karpinski#### Improved Approximation Lower Bounds on Small Occurrence Optimization

__
TR02-070
| 13th December 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### 9/8-Approximation Algorithm for Random MAX-3SAT

Revisions: 1

__
TR02-046
| 16th July 2002
__

Marek Karpinski#### On Approximability of Minimum Bisection Problem

__
TR02-044
| 16th July 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### A Polynomial Time Approximation Scheme for Subdense MAX-CUT

__
TR02-041
| 2nd July 2002
__

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon#### A Polynomial Time Approximation Scheme for Metric MIN-BISECTION

__
TR02-029
| 3rd June 2002
__

Marek Karpinski, Yakov Nekrich#### Parallel Construction of Minimum Redundancy Length-Limited Codes

__
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

__
TR02-018
| 22nd March 2002
__

Piotr Berman, Marek Karpinski, Yakov Nekrich#### Approximating Huffman Codes in Parallel

__
TR01-100
| 14th December 2001
__

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Random Sampling and Approximation of MAX-CSP Problems

__
TR01-097
| 11th December 2001
__

Piotr Berman, Marek Karpinski#### Improved Approximations for General Minimum Cost Scheduling

__
TR01-053
| 17th July 2001
__

Piotr Berman, Marek Karpinski#### Efficient Amplifiers and Bounded Degree Optimization

__
TR01-047
| 3rd July 2001
__

Piotr Berman, Sridhar Hannenhalli, Marek Karpinski#### 1.375-Approximation Algorithm for Sorting by Reversals

__
TR01-042
| 31st May 2001
__

Marek Karpinski#### Approximating Bounded Degree Instances of NP-Hard Problems

__
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

__
TR01-026
| 3rd April 2001
__

Piotr Berman, Marek Karpinski#### Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

__
TR01-025
| 28th March 2001
__

Piotr Berman, Marek Karpinski#### Approximating Minimum Unsatisfiability of Linear Equations

__
TR00-091
| 21st December 2000
__

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski#### Approximability of Dense Instances of NEAREST CODEWORD Problem

__
TR00-089
| 1st December 2000
__

Lars Engebretsen, Marek Karpinski#### Approximation Hardness of TSP with Bounded Metrics

Revisions: 1

__
TR00-064
| 29th August 2000
__

Klaus Jansen, Marek Karpinski, Andrzej Lingas#### A Polynomial Time Approximation Scheme for MAX-BISECTION on Planar Graphs

__
TR00-051
| 14th July 2000
__

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas#### Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs

__
TR00-043
| 21st June 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### A Note on Approximating MAX-BISECTION on Regular Graphs

__
TR00-021
| 19th April 2000
__

Uriel Feige, Marek Karpinski, Michael Langberg#### Improved Approximation of MAX-CUT on Graphs of Bounded Degree

__
TR00-001
| 14th January 2000
__

Piotr Berman, Moses Charikar, Marek Karpinski#### On-Line Load Balancing for Related Machines

__
TR99-027
| 17th July 1999
__

Marek Karpinski, Igor E. Shparlinski#### On the computational hardness of testing square-freeness of sparse polynomials

__
TR99-020
| 9th June 1999
__

Marek Karpinski#### Randomized Complexity of Linear Arrangements and Polyhedra

__
TR99-009
| 26th March 1999
__

Marek Karpinski, Rustam Mubarakzjanov#### A Note on Las Vegas OBDDs

__
TR98-065
| 6th November 1998
__

Piotr Berman, Marek Karpinski#### On Some Tighter Inapproximability Results, Further Improvements

__
TR98-064
| 6th November 1998
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### Polynomial Time Approximation of Dense Weighted Instances of MAX-CUT

__
TR98-038
| 9th July 1998
__

Marek Karpinski#### On the Computational Power of Randomized Branching Programs

__
TR98-029
| 27th May 1998
__

Piotr Berman, Marek Karpinski#### On Some Tighter Inapproximability Results

__
TR98-024
| 28th April 1998
__

Wenceslas Fernandez de la Vega, Marek Karpinski#### On Approximation Hardness of Dense TSP and other Path Problems

__
TR98-014
| 6th February 1998
__

Gunter Blache, Marek Karpinski, Juergen Wirtgen#### On Approximation Intractability of the Bandwidth Problem

__
TR98-011
| 29th January 1998
__

Farid Ablayev, Marek Karpinski#### A Lower Bound for Integer Multiplication on Randomized Read-Once Branching Programs

__
TR98-004
| 13th January 1998
__

Farid Ablayev, Marek Karpinski#### On the Power of Randomized Ordered Branching Programs

__
TR97-041
| 18th September 1997
__

Marek Karpinski, Juergen Wirtgen#### On Approximation Hardness of the Bandwidth Problem

__
TR97-024
| 9th June 1997
__

Marek Karpinski#### Polynomial Time Approximation Schemes for Some Dense Instances of NP-Hard Optimization Problems

__
TR97-017
| 5th May 1997
__

Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky#### An Approximation Algorithm for the Bandwidth Problem on Dense Graphs

__
TR97-004
| 19th February 1997
__

Marek Karpinski, Alexander Zelikovsky#### Approximating Dense Cases of Covering Problems

Comments: 1

__
TR96-058
| 25th November 1996
__

Dima Grigoriev, Marek Karpinski#### Randomized $\mathbf{\Omega (n^2)}$ Lower Bound for Knapsack

__
TR95-063
| 19th December 1995
__

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky#### A Lower Bound for Randomized Algebraic Decision Trees

__
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

__
TR95-055
| 24th November 1995
__

Marek Karpinski, Angus Macintyre#### VC Dimension of Sigmoidal and General Pfaffian Networks

__
TR95-054
| 24th November 1995
__

Farid Ablayev, Marek Karpinski#### On the Power of Randomized Branching Programs

__
TR95-030
| 20th June 1995
__

Marek Karpinski, Alexander Zelikovsky#### New Approximation Algorithms for the Steiner Tree Problems

__
TR95-022
| 2nd May 1995
__

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara#### Pattern-Matching for Strings with Short Descriptions

__
TR95-021
| 20th April 1995
__

Marek Karpinski, Rutger Verbeek#### On Randomized Versus Deterministic Computation

__
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

__
TR94-024
| 12th December 1994
__

Marek Karpinski, Angus Macintyre#### Polynomial Bounds for VC Dimension of Sigmoidal Neural Networks

Marek Karpinski

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

Andrzej Dudek , Marek Karpinski, Andrzej Rucinski, Edyta Szymanska

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

Gábor Ivanyos, Marek Karpinski, Youming Qiao, Miklos Santha

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

Marek Karpinski, Richard Schmied

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

Marek Karpinski, Michael Lampis, Richard Schmied

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

Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu

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

Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena

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

Marek Karpinski, Richard Schmied

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

Marek Karpinski, Richard Schmied

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

Marek Karpinski, Richard Schmied, Claus Viehmann

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

more >>>Gábor Ivanyos, Marek Karpinski, Nitin Saxena

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

Marek Karpinski, Warren Schudy

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

Gábor Ivanyos, Marek Karpinski, Lajos Rónyai, Nitin Saxena

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

Piotr Berman, Marek Karpinski, Alexander Zelikovsky

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 >>>Gábor Ivanyos, Marek Karpinski, Nitin Saxena

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

Piotr Berman, Bhaskar DasGupta, Marek Karpinski

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

Wenceslas Fernandez de la Vega, Marek Karpinski

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

Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

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

Wenceslas Fernandez de la Vega, Marek Karpinski

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 >>>Wenceslas Fernandez de la Vega, Marek Karpinski

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

Magnus Bordewich, Martin Dyer, Marek Karpinski

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

Piotr Berman, Marek Karpinski

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

Magnus Bordewich, Martin Dyer, Marek Karpinski

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

Marek Karpinski, Yakov Nekrich

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

Piotr Berman, Marek Karpinski, Alexander D. Scott, Alexander D. Scott

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

more >>>Piotr Berman, Marek Karpinski, Yakov Nekrich

We prove upper and lower bounds for computing Merkle tree

traversals, and display optimal trade-offs between time

and space complexity of that problem.

Piotr Berman, Marek Karpinski

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

Piotr Berman, Marek Karpinski, Alexander D. Scott

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

Piotr Berman, Marek Karpinski, Alexander D. Scott

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

Piotr Berman, Marek Karpinski

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.

Wenceslas Fernandez de la Vega, Marek Karpinski

We prove that MAX-3SAT can be approximated in polynomial time

within a factor 9/8 on random instances.

Marek Karpinski

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.

Wenceslas Fernandez de la Vega, Marek Karpinski

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

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon

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

Marek Karpinski, Yakov Nekrich

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

Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani

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

Piotr Berman, Marek Karpinski, Yakov Nekrich

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

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

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

Piotr Berman, Marek Karpinski

We give improved trade-off results on approximating general

minimum cost scheduling problems.

Piotr Berman, Marek Karpinski

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

Piotr Berman, Sridhar Hannenhalli, Marek Karpinski

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

Marek Karpinski

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

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

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

Piotr Berman, Marek Karpinski

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

Piotr Berman, Marek Karpinski

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

Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

We give a polynomial time approximation scheme (PTAS) for dense

instances of the NEAREST CODEWORD problem.

Lars Engebretsen, Marek Karpinski

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

Klaus Jansen, Marek Karpinski, Andrzej Lingas

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

Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas

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

Uriel Feige, Marek Karpinski, Michael Langberg

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

Uriel Feige, Marek Karpinski, Michael Langberg

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

Piotr Berman, Moses Charikar, Marek Karpinski

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

Marek Karpinski, Igor E. Shparlinski

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.

Marek Karpinski

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

Marek Karpinski, Rustam Mubarakzjanov

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.

Piotr Berman, Marek Karpinski

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

Wenceslas Fernandez de la Vega, Marek Karpinski

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

Marek Karpinski

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

Piotr Berman, Marek Karpinski

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

Wenceslas Fernandez de la Vega, Marek Karpinski

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

Gunter Blache, Marek Karpinski, Juergen Wirtgen

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

Farid Ablayev, Marek Karpinski

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

Farid Ablayev, Marek Karpinski

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

Marek Karpinski, Juergen Wirtgen

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

Marek Karpinski

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.

Marek Karpinski, Juergen Wirtgen, Alexander Zelikovsky

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

Marek Karpinski, Alexander Zelikovsky

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

Dima Grigoriev, Marek Karpinski

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

Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky

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

Dima Grigoriev, Marek Karpinski, A. C. Yao

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

Marek Karpinski, Angus Macintyre

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

Farid Ablayev, Marek Karpinski

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

Marek Karpinski, Alexander Zelikovsky

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

Marek Karpinski, Wojciech Rytter, Ayumi Shinohara

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

Marek Karpinski, Rutger Verbeek

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

Marek Karpinski, Alexander Zelikovsky

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

Marek Karpinski, Angus Macintyre

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