All Questions

12,972 questions
Filter by
Sorted by
Tagged with
44 views

Can you fix integral LP variables for a non-integral polytope without affecting the existence of integral optima?

Suppose I have a linear program $LP1=\{\mbox{Maximize }c^\top x \mid x\in \mathcal{P}\}$ for some polytope $\mathcal{P}\subseteq [0,1]^n$, which is known to have fractional extreme points. Suppose ...
• 341
38 views

Bipartite Matching with a Partition Constraint over the Vertices

Let $G = (X,Y,E)$ be a bipartite graph and let $X_1,\ldots,X_r$ be a partition of $X$. For some $i \in \{1,\ldots, r\}$ and $E' \subseteq E$ we say that constraint $X_i$ is covered by some $E'$ if ...
• 412
70 views

What work on min max connectivity problems has there been?

For instance has min max spanning/steiner/prize-collecting tree been studied. i.e. each edge $e$ has costs $c_{v,e}$ of each resource $i$. And we wish to find a spanning tree minimizing the maximum ...
• 228
28 views

How can I optimize the assignment of object sets to workers with pre-existing caches to minimize discrepancy?

I am working on a problem where I have $n$ workers, each with a cache that already contains a specific set of objects. Additionally, I receive $n \times m$ sets of objects. My task is to assign ...
• 33
169 views

Polynomial Identity Testing for $\prod \sum \prod$

I am reading a survey on polynomial identity testing by Saxena. On page 6 he writes that PIT for depth-3 circuits of the form $\prod \sum \prod$ is trivial. He gives no citation and as such I believe ...
34 views

Find the weighted perfect "1-to-k" matching algorithm with minimum aggregated k max weight

Similar with Weighted matching algorithm for minimizing max weight. Consider the following matching problem: Input: a complete weighted bipartite graph with $n+(k*n)$ vertices, given by $n$, $k*n$, ...
• 33
65 views

Has multiobjective prize collecting steiner tree or TSP been studied?

Suppose we have a graph $G$ a root $r$ and each node $v$ has some amount of $c_{v,i}$ of each resource $i$. I connect a set of nodes to the root that maximizes the minimum amount of any resource using ...
• 228
102 views

Higher dimensional automata?

An NFA is just the data of a labelled, directed multigraph with a accepting predicate over the vertices. Simplicial sets generalize directed multigraphs by allowing the existence of higher dimensional ...
56 views

175 views

This is a variant of the unsolved problem of $a^6+b^6+c^6≠d^6+e^6+f^6$, for distinct primes. Does it have any significance for Exact Three Cover?

Suppose, I'm solving Exact 3 Cover, given a list with no duplicates $S$ of $3m$ whole numbers and a collection $C$ of subsets of $S$, each containing exactly three elements. The goal is to decide if ...
• 159
47 views

On a modular inverse graph construction

Given a balanced bipartite graph $G_1$ on $2n$ vertices on the condition $PM(G_1)\equiv1\bmod2$, an integer $i$ of size $\Omega(n\log n)$, can we find a balanced bipartite graph $G_2$ on $poly(n)$ ...
• 13k
157 views

Resources on how to write good TCS papers

I am looking for good resources on how to write papers, which could be useful for graduate students in TCS. The internet seems to be full with style books, papers, and online talks on the subject, but ...
• 5,615
136 views

• 13k
52 views

Partial Hamiltonian Path Optimization Problem

Let $G = (V,E)$ be a directed graph. Define the optimization problem in which the goal is to find a subset of edges in $G$ of maximum cardinality, such that (i) the in-degree and out-degree of each ...
• 412
68 views

Addition chains are a well-known way of building up a number from 1 by adding two previously computed numbers. It is a long-standing open problem to determine the complexity of computing the length of ...
• 14k
112 views

Hardnnes of Approximation of Minimum Vertex Cover on 3-Regular Graphs

The paper [Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs, Austrin, Khot, Safra] Shows that assuming the Unique Game Conjecture (UGC) the minimum vertex cover problem ...
• 412
149 views

Help understand why FOL wff are enumerable, but FOL is undecidable

I am very new to this. I am trying to understand some basics about what kinds of enumerations in FOL are possible, and which are not. If you accept that FOL is defined in terms of a finite number of ...
53 views

Hardness of deciding fractional chromatic number at most $k$

I want to find a reference for the following statement. Here, $\chi_f(G)$ denotes the fractional chromatic number of a graph $G$. For every fixed $r>2$, deciding $\chi_f(G) \leq r$ for a given ...
29 views

Variants of weak optimization problems for convex sets

In their famous book, Grotschel Lovasz and Schrijver (1993) present several algorithmic problems on convex sets. Each of these problems has a strong variant and a weak variant. In particular, the ...
• 2,262
64 views

Is there a complexity class defined as fixed Boolean combinations of problems in $\mathsf{BPP} \cup \mathsf{BH}$?

I have 2 type of decision problems: either in $\mathsf{BPP}$ or in $\mathsf{NP}$; and I want to decide fixed Boolean combinations of them. Since $\mathsf{BPP}$ is closed under Boolean combinations and ...
87 views

94 views

Does there exist a cryptographic associative hash function?

Does there exist a function $f(x,y)$ with these properties: Computing $f(x,y)$ is in P. $f$ is associative: $f(x, f(y, z)) = f(f(x, y), z)$. $f$ is one-way (assuming P $\neq$ NP): Given the value ...
• 251
639 views

Complexity of NFA cofiniteness

What is the complexity, given as input an NFA, of determining if it is cofinite (i.e., the complement of its language is finite)? Surely this must be known but I can't find a reference. Note that the ...
• 1,429
44 views

For which k can we decide whether an input k-gon tiles?

Can we decide whether a given polygon can tile the whole plane? First, let me briefly summarize what is known about this problem. If we only allow translations, then the problem is always decidable in ...
• 14k
58 views

70 views

Reductions That Acts on Witnesses

We say that a language $X$ is polynomial time reducible to $Y$, intuitively, if given an algorithm for solving $Y$, there's an algorithm for solving $X$. I know this can be formalized using Karp ...