Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LINEAR EQUATIONS:
Reports tagged with Linear Equations:
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-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-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 >>>

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

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

TR14-096 | 29th July 2014
Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Toran

#### Solving Linear Equations Parameterized by Hamming Weight

Given a system of linear equations $Ax=b$ over the binary field $\mathbb{F}_2$ and an integer $t\ge 1$, we study the following three algorithmic problems:
1. Does $Ax=b$ have a solution of weight at most $t$?
2. Does $Ax=b$ have a solution of weight exactly $t$?
3. Does $Ax=b$ have a ... 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-130 | 30th August 2020
Amey Bhangale, Subhash Khot

#### Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups

A seminal result of H\r{a}stad [J. ACM, 48(4):798–859, 2001] shows that it is NP-hard to find an assignment that satisfies $\frac{1}{|G|}+\varepsilon$ fraction of the constraints of a given $k$-LIN instance over an abelian group, even if there is an assignment that satisfies $(1-\varepsilon)$ fraction of the constraints, for any constant ... more >>>

TR21-112 | 30th July 2021
Vikraman Arvind, Venkatesan Guruswami

#### CNF Satisfiability in a Subspace and Related Problems

We introduce the problem of finding a satisfying assignment to a CNF formula that must further belong to a prescribed input subspace. Equivalent formulations of the problem include finding a point outside a union of subspaces (the Union-of-Subspace Avoidance (USA) problem), and finding a common zero of a system of ... more >>>

ISSN 1433-8092 | Imprint