All reports by Author Piotr Berman:

__
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

__
TR07-119
| 5th December 2007
__

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

__
TR07-092
| 10th July 2007
__

Piotr Berman, Bhaskar DasGupta#### Approximating the Online Set Multicover Problems Via Randomized Winnowing

__
TR06-030
| 17th January 2006
__

Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar#### Packing to angles and sectors

__
TR05-069
| 11th July 2005
__

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

Revisions: 2

__
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-018
| 22nd March 2002
__

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

__
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-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-001
| 14th January 2000
__

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

__
TR98-065
| 6th November 1998
__

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

__
TR98-029
| 27th May 1998
__

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

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

Piotr Berman, Bhaskar DasGupta

In this paper, we consider the weighted online set k-multicover problem. In this problem, we have an universe V of elements, a family SS of subsets of V with a positive real cost for every S\in SS, and a ``coverage factor'' (positive integer) k. A subset \{i_0,i_1,\ldots\ \subseteq V of ... more >>>

Piotr Berman, Jieun Jeong, Shiva Prasad Kasiviswanathan, Bhuvan Urgaonkar

In our problem we are given a set of customers, their positions on the

plane and their demands. Geometrically, directional antenna with

parameters $\alpha,\rho,R$ is a set

of points with radial coordinates $(\theta,r)$ such that

$\alpha \le \theta \le \alpha+\rho$ and $r \le R$. Given a set of

possible directional ...
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 >>>

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.

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

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

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

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

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

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