# zbMATH — the first resource for mathematics

Compute Distance To:
 Documents Indexed: 277 Publications since 1976, including 13 Books Biographic References: 2 Publications
all top 5

all top 5

#### Serials

 25 Journal of Computer and System Sciences 20 SIAM Journal on Computing 15 Journal of the Association for Computing Machinery 12 Theoretical Computer Science 9 Information Processing Letters 6 Journal of the ACM 5 Mathematics of Operations Research 5 Journal of Algorithms 5 Algorithmica 4 Information and Computation 4 Games and Economic Behavior 3 Information and Control 3 Networks 2 Discrete Mathematics 2 Journal of Graph Theory 2 Operations Research 2 Bulletin of the Greek Mathematical Society 2 SIAM Journal on Algebraic and Discrete Methods 2 Operations Research Letters 2 Combinatorica 2 Journal of Complexity 2 Proceedings of the National Academy of Sciences of the United States of America 2 Annals of Mathematics and Artificial Intelligence 2 Internet Mathematics 1 Acta Informatica 1 Artificial Intelligence 1 Discrete Applied Mathematics 1 ACM Transactions on Database Systems 1 Computing 1 Journal of Economic Theory 1 Kiberneticheskiĭ Sbornik. Novaya Seriya 1 Mathematical Programming 1 Mathematical Systems Theory 1 Naval Research Logistics 1 SIAM Journal on Control and Optimization 1 Theoretical Population Biology 1 ACM Transactions on Programming Languages and Systems 1 Systems & Control Letters 1 The Journal of Logic Programming 1 Probability Theory and Related Fields 1 Complex Systems 1 ORSA Journal on Computing 1 Distributed Computing 1 RAIRO. Informatique Théorique et Applications 1 Mathematical Programming. Series A. Series B 1 The Journal of Artificial Intelligence Research (JAIR) 1 Journal of Combinatorial Optimization 1 RIMS Kokyuroku 1 Bulletin Société Mathématique de Grèce. Nouvelle Série 1 Lecture Notes in Computer Science 1 LIPIcs – Leibniz International Proceedings in Informatics 1 Journal of Theoretical Biology 1 Computer Science Review
all top 5

#### Fields

 241 Computer science (68-XX) 65 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 58 Operations research, mathematical programming (90-XX) 44 Combinatorics (05-XX) 19 Mathematical logic and foundations (03-XX) 9 General and overarching topics; collections (00-XX) 8 Numerical analysis (65-XX) 6 History and biography (01-XX) 6 Information and communication theory, circuits (94-XX) 4 Biology and other natural sciences (92-XX) 3 Probability theory and stochastic processes (60-XX) 2 Linear and multilinear algebra; matrix theory (15-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Geometry (51-XX) 2 Systems theory; control (93-XX) 1 Number theory (11-XX) 1 Group theory and generalizations (20-XX) 1 Operator theory (47-XX) 1 Calculus of variations and optimal control; optimization (49-XX) 1 Convex and discrete geometry (52-XX) 1 General topology (54-XX) 1 Algebraic topology (55-XX) 1 Statistics (62-XX)

#### Citations contained in zbMATH Open

233 Publications have been cited 8,120 times in 6,516 Documents Cited by Year
Computational complexity. Zbl 0833.68049
1994
Combinatorial optimization: algorithms and complexity. Zbl 0503.90060
1982
Computational complexity. Zbl 0557.68033
1985
Optimization, approximation, and complexity classes. Zbl 0765.68036
1991
Worst-case equilibria. Zbl 1099.91501
1999
Combinatorial optimization: algorithms and complexity. Corr. repr. of the 1982 original. Zbl 0944.90066
1998
The complexity of multiterminal cuts. Zbl 0809.68075
Dahlhaus, E.; Johnson, D. S.; Papadimitriou, C. H.; Seymour, P. D.; Yannakakis, M.
1994
On generating all maximal independent sets. Zbl 0654.68086
Johnson, David S.; Yannakakis, Mihalis; Papadimitriou, Christos H.
1988
Algorithms, games, and the internet. Zbl 1323.68022
2001
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
1988
On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048
1994
The complexity of pure Nash equilibria. Zbl 1192.91042
Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal
2004
The complexity of computing a Nash equilibrium. Zbl 1185.91019
2009
Hamilton paths in grid graphs. Zbl 0506.05043
Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz
1982
The complexity of searching a graph. Zbl 0637.68081
Megiddo, N.; Hakimi, S. L.; Garey, M. R.; Johnson, D. S.; Papadimitriou, C. H.
1988
Worst-case equilibria. Zbl 1303.91012
2009
The NP-completeness of the bandwidth minimization problem. Zbl 0321.65019
1976
Searching and pebbling. Zbl 0616.68064
Kirousis, Lefteris M.; Papadimitriou, Christos H.
1986
The Euclidean traveling salesman problem is NP-complete. Zbl 0386.90057
1977
The complexity of facets (and some facets of complexity). Zbl 0571.68028
1984
The complexity of coloring circular arcs and chords. Zbl 0499.05058
Garey, M. R.; Johnson, D. S.; Miller, G. L.; Papadimitriou, C. H.
1980
The traveling salesman problem with distances one and two. Zbl 0778.90057
1993
On the complexity of cooperative solution concepts. Zbl 0824.90146
1994
Shortest paths without a map. Zbl 0733.68065
1991
On a network creation game. Zbl 1322.91013
Fabrikant, Alex; Luthra, Ankur; Maneva, Elitza; Papadimitriou, Christos H.; Shenker, Scott
2003
Elements of the theory of computation. Zbl 0464.68001
Lewis, Harry R.; Papadimitriou, Christos H.
1981
The discrete geodesic problem. Zbl 0625.68051
Mitchell, Joseph S. B.; Mount, David M.; Papadimitriou, Christos H.
1987
The complexity of computing a Nash equilibrium. Zbl 1301.68142
2006
On the complexity of reconfiguration problems. Zbl 1207.68166
Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi
2011
The serializability of concurrent database updates. Zbl 0419.68036
1979
The complexity of Markov decision processes. Zbl 0638.90099
Papadimitriou, Christos H.; Tsitsiklis, John N.
1987
On the complexity of integer programming. Zbl 0468.68050
1981
1979
Bounds for sorting by prefix reversal. Zbl 0397.68062
Gates, William H.; Papadimitriou, Christos H.
1979
Inverval scheduling: a survey. Zbl 1143.90337
Kolen, Antoon W. J.; Lenstra, Jan Karel; Papadimitriou, Christos H.; Spieksma, Frits C. R.
2007
Probabilistic satisfiability. Zbl 0647.68049
1988
The complexity of facets resolved. Zbl 0655.68041
1988
Flowshop scheduling with limited temporary storage. Zbl 0475.68014
Papadimitriou, Christos H.; Kanellakis, Paris C.
1980
On the $$k$$-server conjecture. Zbl 0885.68075
1995
The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03024
Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza; Papadimitriou, Christos H.
2009
Interval graphs and searching. Zbl 0566.05056
Kirousis, Lefteris M.; Papadimitriou, Christos H.
1985
The weighted region problem: Finding shortest paths through a weighted planar subdivision. Zbl 0799.68150
Mitchell, Joseph S. B.; Papadimitriou, Christos H.
1991
The complexity of restricted spanning tree problems. Zbl 0478.68068
1982
Latent semantic indexing: A probabilistic analysis. Zbl 0963.68063
Papadimitriou, Christos H.; Raghavan, Prabhakar; Tamaki, Hisao; Vempala, Santosh
2000
On total functions, existence theorems and computational complexity. Zbl 0731.68036
1991
Games against nature. Zbl 0583.68020
1985
A deterministic $$(2-2/(k+1))^{n}$$ algorithm for $$k$$-SAT based on local search. Zbl 1061.68071
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe
2002
Sharing the cost of multicast transmissions. Zbl 0996.68026
Feigenbaum, Joan; Papadimitriou, Christos H.; Shenker, Scott
2001
Symmetric space-bounded computation. Zbl 0491.68045
Lewis, Harry R.; Papadimitriou, Christos H.
1982
The complexity of the travelling repairman problem. Zbl 0585.68057
1986
Exploring an unknown graph. Zbl 0941.68099
1999
Beyond competitive analysis. Zbl 0959.68131
2000
On limited nondeterminism and the complexity of the V-C dimension. Zbl 0859.68031
1996
On two geometric problems related to the travelling salesman problem. Zbl 0551.90093
Papadimitriou, Christos H.; Vazirani, Umesh V.
1984
On a conjecture related to geometric routing. Zbl 1079.68078
2005
Topological bandwidth. Zbl 0573.05052
Makedon, F. S.; Papadimitriou, C. H.; Sudborough, I. H.
1985
How to learn an unknown environment. I: The rectilinear case. Zbl 0904.68115
Deng, Xiaotie; Kameda, Tiko; Papadimitriou, Christos
1998
Towards an architecture-independent analysis of parallel algorithms. Zbl 0692.68032
1990
Computing correlated equilibria in multi-player games. Zbl 1314.91012
2008
Worst-case and probabilistic analysis of a geometric location problem. Zbl 0461.68078
1981
On the complexity of edge traversing. Zbl 0351.90079
1976
The complexity of optimal queuing network control. Zbl 0977.90008
Papadimitriou, Christos H.; Tsitsiklis, John N.
1999
The adjacency relation on the traveling salesman polytope is NP-complete. Zbl 0376.90067
1978
Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024
Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V.
2008
The theory of database concurrency control. Zbl 0609.68073
1986
A note on approximate Nash equilibria. Zbl 1167.91390
2009
Communication complexity. Zbl 0584.68064
1984
Inclusion dependencies and their interaction with functional dependencies. Zbl 0586.68082
Casanova, Marco A.; Fagin, Ronald; Papadimitriou, Christos H.
1984
On linear characterizations of combinatorial optimization problems. Zbl 0505.65020
Karp, Richard M.; Papadimitriou, Christos H.
1982
An algorithm for shortest-path motion in three dimensions. Zbl 0603.68070
1985
Why not negation by fixpoint? Zbl 0753.68028
Kolaitis, Phokion G.; Papadimitriou, Christos H.
1991
Some examples of difficult traveling salesman problems. Zbl 0383.90105
1978
Map graphs. Zbl 1323.05039
Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H.
2002
On Horn envelopes and hypergraph transversals. (Extended abstract). Zbl 0925.03036
Kavvdias, Dimitris; Papadimitriou, Christos; Sideri, Martha
1993
On the complexity of database queries. Zbl 0939.68024
1999
Exponential lower bounds for finding Brouwer fixed points. Zbl 0696.65045
Hirsch, Michael D.; Papadimitriou, Christos H.; Vavasis, Stephen A.
1989
The complexity of the capacitated tree problem. Zbl 0443.68048
1978
A linear programming approach to reasoning about probabilities. Zbl 0878.68034
1990
An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1094.68528
Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva
2003
A note on succinct representations of graphs. Zbl 0616.68041
1986
Local search for the asymmetric traveling salesman problem. Zbl 0447.90082
1980
Covering graphs by simple circuits. Zbl 0468.68071
Itai, Alon; Lipton, Richard J.; Papadimitriou, Christos H.; Rodeh, M.
1981
On complexity as bounded rationality (extended abstract). Zbl 1345.68216
1994
On the complexity of protein folding (extended abstract). Zbl 1007.68511
Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis
1998
The even-path problem for graphs and digraphs. Zbl 0552.68059
LaPaugh, Andrea S.; Papadimitriou, Christos H.
1984
Searching a fixed graph. Zbl 1045.90532
Koutsoupias, Elias; Papadimitriou, Christos; Yannakakis, Mihalis
1996
Deciding stability and mortality of piecewise affine dynamical systems. Zbl 0973.68067
Blondel, V. D.; Bournez, O.; Koiran, P.; Papadimitriou, C. H.; Tsitsiklis, J. N.
2001
Computing correlated equilibria in multi-player games. Zbl 1192.91021
2005
On oblivious PTAS’s for Nash equilibrium. Zbl 1304.91014
2009
Computing equilibria in multi-player games. Zbl 1297.91005
2005
Efficient search for rationals. Zbl 0411.65037
1979
Planar map graphs. Zbl 1028.68104
Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H.
1998
Performance guarantees for heuristics. Zbl 0574.90086
Johnson, D. S.; Papadimitriou, C. H.
1985
Continuous local search. Zbl 1373.68263
2011
Reducibility among equilibrium problems. Zbl 1301.68161
Goldberg, Paul W.; Papadimitriou, Christos H.
2006
On the approximability of the traveling salesman problem. Zbl 1106.90071
2006
NP-completeness: a retrospective. Zbl 1401.68100
1997
Algorithms, games, and the internet (extended abstract). Zbl 0986.68566
2001
On players with a bounded number of states. Zbl 0767.90097
1992
On the complexity of local search for the traveling salesman problem. Zbl 0381.68043
1977
Towards a unified complexity theory of total functions. Zbl 1393.68053
Goldberg, Paul W.; Papadimitriou, Christos H.
2018
Cycles in adversarial regularized learning. Zbl 1403.68200
Mertikopoulos, Panayotis; Papadimitriou, Christos; Piliouras, Georgios
2018
From battlefields to elections: winning strategies of Blotto and auditing games. Zbl 1403.91013
2018
On satisfiability problems with a linear structure. Zbl 1398.68235
Gaspers, Serge; Papadimitriou, Christos H.; Sæther, Sigve Hortemo; Telle, Jan Arne
2017
TFNP: an update. Zbl 06751046
Goldberg, Paul W.; Papadimitriou, Christos H.
2017
Stathis zachos at 70! Zbl 06751084
Bakali, Eleni; Cheilaris, Panagiotis; Fotakis, Dimitris; Fürer, Martin; Koutras, Costas D.; Markou, Euripides; Nomikos, Christos; Pagourtzis, Aris; Papadimitriou, Christos H.; Papaspyrou, Nikolaos S.; Potika, Katerina
2017
Zero-sum polymatrix games: a generalization of minmax. Zbl 1336.91009
2016
Can almost everybody be almost happy? Zbl 1335.91021
2016
From Nash equilibria to chain recurrent sets: solution concepts and topology. Zbl 1335.91009
2016
2016
On the complexity of dynamic mechanism design. Zbl 1417.91247
2016
Approximate Nash equilibria in anonymous games. Zbl 1330.91015
2015
Sparse covers for sums of indicators. Zbl 1334.60048
2015
Optimal deterministic auctions with correlated priors. Zbl 1318.91102
2015
Algorithms, games, and evolution. Zbl 1355.91017
2014
On simplex pivoting rules and complexity theory. Zbl 1418.90145
2014
Efficiency-revenue trade-offs in auctions. Zbl 1367.91077
Diakonikolas, Ilias; Papadimitriou, Christos; Pierrakos, George; Singer, Yaron
2012
On the complexity of reconfiguration problems. Zbl 1207.68166
Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi
2011
Continuous local search. Zbl 1373.68263
2011
On optimal single-item auctions. Zbl 1288.90087
2011
Modeling social networks through user background and behavior. Zbl 1328.91262
Foudalis, Ilias; Jain, Kamal; Papadimitriou, Christos; Sideri, Martha
2011
The complexity of the homotopy method, equilibrium selection and Lemke-Howson solutions. Zbl 1292.91013
Goldberg, Paul W.; Papadimitriou, Christos H.; Savani, Rahul
2011
Kurt Gödel and the foundations of mathematics. Horizons of truth. Zbl 1253.00009
Baaz, Matthias; Papadimitriou, Christos H.; Putnam, Hilary W.; Scott, Dana S.; Harper, Charles L. jun.
2011
An analytical contrast between fitness maximization and selection for mixability. Zbl 1405.92197
2011
When the players are not expectation maximizers. Zbl 1253.91009
2010
Inapproximability for VCG-based combinatorial auctions. Zbl 1288.91099
Buchfuhrer, Dave; Dughmi, Shaddin; Fu, Hu; Kleinberg, Robert; Mossel, Elchanan; Papadimitriou, Christos; Schapira, Michael; Singer, Yaron; Umans, Chris
2010
The myth of the folk theorem. Zbl 1207.91012
Borgs, Christian; Chayes, Jennifer; Immorlica, Nicole; Kalai, Adam Tauman; Mirrokni, Vahab; Papadimitriou, Christos
2010
On learning algorithms for Nash equilibria. Zbl 1310.91033
2010
An impossibility theorem for price-adjustment mechanisms. Zbl 1205.91067
2010
The complexity of computing a Nash equilibrium. Zbl 1185.91019
2009
Worst-case equilibria. Zbl 1303.91012
2009
The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03024
Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza; Papadimitriou, Christos H.
2009
A note on approximate Nash equilibria. Zbl 1167.91390
2009
On oblivious PTAS’s for Nash equilibrium. Zbl 1304.91014
2009
Congestion games with malicious players. Zbl 1173.91301
Babaioff, Moshe; Kleinberg, Robert; Papadimitriou, Christos H.
2009
On a network generalization of the minmax theorem. Zbl 1248.91006
2009
A note on strictly competitive games. Zbl 1377.91006
2009
Logicomix. An epic search for truth. Character design and drawings by Alecos Papadatos, color by Annie Di Donna. Zbl 1248.00011
2009
Computing correlated equilibria in multi-player games. Zbl 1314.91012
2008
Market equilibrium via a primal-dual algorithm for a convex program. Zbl 1325.91024
Devanur, Nikhil R.; Papadimitriou, Christos H.; Saberi, Amin; Vazirani, Vijay V.
2008
The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond. Zbl 1192.68357
2008
On the complexity of reconfiguration problems. Zbl 1183.68310
Ito, Takehiro; Demaine, Erik D.; Harvey, Nicholas J. A.; Papadimitriou, Christos H.; Sideri, Martha; Uehara, Ryuhei; Uno, Yushi
2008
The myth of the folk theorem. Zbl 1231.91006
Borgs, Christian; Chayes, Jennifer; Immortica, Nicole; Kalai, Adam Tauman; Mirrokni, Vahab; Papadimitriou, Christos
2008
Linked decompositions of networks and the power of choice in Pólya urns. Zbl 1192.90027
Lin, Henry; Amanatidis, Christos; Sideri, Martha; Karp, Richard M.; Papadimitriou, Christos H.
2008
Incentive-compatible interdomain routing with linear utilities. Zbl 1195.90019
Hall, Alexander; Nikolova, Evdokia; Papadimitriou, Christos
2008
Inverval scheduling: a survey. Zbl 1143.90337
Kolen, Antoon W. J.; Lenstra, Jan Karel; Papadimitriou, Christos H.; Spieksma, Frits C. R.
2007
The complexity of finding Nash equilibria. Zbl 1151.91381
2007
Approximately dominating representatives. Zbl 1108.68042
2007
The complexity of computing a Nash equilibrium. Zbl 1301.68142
2006
Reducibility among equilibrium problems. Zbl 1301.68161
Goldberg, Paul W.; Papadimitriou, Christos H.
2006
On the approximability of the traveling salesman problem. Zbl 1106.90071
2006
Recognizing hole-free 4-map graphs in cubic time. Zbl 1095.68076
Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H.
2006
On certain connectivity properties of the internet topology. Zbl 1090.68002
Mihail, Milena; Papadimitriou, Christos; Saberi, Amin
2006
The connectivity of Boolean satisfiability: computational and structural dichotomies. Zbl 1201.03023
Gopalan, Parikshit; Kolaitis, Phokion G.; Maneva, Elitza N.; Papadimitriou, Christos H.
2006
The game world is flat: the complexity of Nash equilibria in succinct games. Zbl 1223.91008
2006
On a conjecture related to geometric routing. Zbl 1079.68078
2005
Computing correlated equilibria in multi-player games. Zbl 1192.91021
2005
Computing equilibria in multi-player games. Zbl 1297.91005
2005
A BGP-based mechanism for lowest-cost routing. Zbl 1264.68215
Feigenbaum, Joan; Papadimitriou, Christos; Sami, Rahul; Shenker, Scott
2005
The complexity of games on highly regular graphs. Zbl 1162.91306
2005
The complexity of low-distortion embeddings between point sets. Zbl 1297.68246
2005
Approximately dominating representatives. Zbl 1108.68446
2005
Approximating the distortion. Zbl 1142.68612
2005
The complexity of pure Nash equilibria. Zbl 1192.91042
Fabrikant, Alex; Papadimitriou, Christos; Talwar, Kunal
2004
Segmentation problems. Zbl 1317.90329
Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar
2004
An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1181.91077
Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva
2004
Selfish caching in distributed systems, a game-theoretic analysis. Zbl 1321.68068
Chun, Byung-Gon; Chaudhuri, Kamalika; Wee, Hoeteck; Barreno, Marco; Papadimitriou, Christos H.; Kubiatowicz, John
2004
Global synchronization in sensornets. Zbl 1196.68024
Elson, Jeremy; Karp, Richard M.; Papadimitriou, Christos H.; Shenker, Scott
2004
On a conjecture related to geometric routing. Zbl 1104.68328
2004
On a network creation game. Zbl 1322.91013
Fabrikant, Alex; Luthra, Ankur; Maneva, Elitza; Papadimitriou, Christos H.; Shenker, Scott
2003
An approximate truthful mechanism for combinatorial auctions with single parameter agents. Zbl 1094.68528
Archer, Aaron; Papadimitriou, Christos; Talwar, Kunal; Tardos, Éva
2003
On the complexity of price equilibria. Zbl 1067.90102
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
2003
On the complexity of single-rule datalog queries. Zbl 1055.68033
2003
Auditing Boolean attributes. Zbl 1026.68042
Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar
2003
A deterministic $$(2-2/(k+1))^{n}$$ algorithm for $$k$$-SAT based on local search. Zbl 1061.68071
Dantsin, Evgeny; Goerdt, Andreas; Hirsch, Edward A.; Kannan, Ravi; Kleinberg, Jon; Papadimitriou, Christos; Raghavan, Prabhakar; Schöning, Uwe
2002
Map graphs. Zbl 1323.05039
Chen, Zhi-Zhong; Grigni, Michelangelo; Papadimitriou, Christos H.
2002
Heuristically optimized trade-offs: A new paradigm for power laws in the internet. Zbl 1056.68503
Fabrikant, Alex; Koutsoupias, Elias; Papadimitriou, Christos H.
2002
On the complexity of equilibria. Zbl 1192.91145
Deng, Xiaotie; Papadimitriou, Christos; Safra, Shmuel
2002
A BGP-based mechanism for lowest-cost routing. Zbl 1292.68152
Feigenbaum, Joan; Papadimitriou, Christos; Sami, Rahul; Shenker, Scott
2002
On the eigenvalue power law. Zbl 1028.68569
2002
On a model of indexability and its bounds for range queries. Zbl 1323.68252
Hellerstein, Joseph M.; Koutsoupias, Elias; Miranker, Daniel P.; Papadimitriou, Christos H.; Samoladas, Vasilis
2002
Algorithms, games, and the internet. Zbl 1323.68022
2001
Sharing the cost of multicast transmissions. Zbl 0996.68026
Feigenbaum, Joan; Papadimitriou, Christos H.; Shenker, Scott
2001
Deciding stability and mortality of piecewise affine dynamical systems. Zbl 0973.68067
Blondel, V. D.; Bournez, O.; Koiran, P.; Papadimitriou, C. H.; Tsitsiklis, J. N.
2001
Algorithms, games, and the internet (extended abstract). Zbl 0986.68566
2001
On approximating a scheduling problem. Zbl 1066.90027
Crescenzi, Pierluigi; Deng, Xiaotie; Papadimitriou, Christos H.
2001
Latent semantic indexing: A probabilistic analysis. Zbl 0963.68063
Papadimitriou, Christos H.; Raghavan, Prabhakar; Tamaki, Hisao; Vempala, Santosh
2000
Beyond competitive analysis. Zbl 0959.68131
2000
On the approximability of the traveling salesman problem (extended abstract). Zbl 1296.68083
2000
On the difficulty of designing good classifiers. Zbl 0959.68044
Grigni, Michelangelo; Mirelli, Vincent; Papadimitriou, Christos H.
2000
Sharing the cost of muliticast transmissions (preliminary version). Zbl 1296.68066
Feigenbaum, Joan; Papadimitriou, Christos; Shenker, Scott
2000
Worst-case equilibria. Zbl 1099.91501
1999
Exploring an unknown graph. Zbl 0941.68099
1999
The complexity of optimal queuing network control. Zbl 0977.90008
Papadimitriou, Christos H.; Tsitsiklis, John N.
1999
On the complexity of database queries. Zbl 0939.68024
1999
Topological queries in spatial databases. Zbl 0943.68051
Papadimitriou, C. H.; Suciu, D.; Vianu, V.
1999
Decision-making by hierarchies of discordant agents. Zbl 0939.90009
1999
Combinatorial optimization: algorithms and complexity. Corr. repr. of the 1982 original. Zbl 0944.90066
1998
How to learn an unknown environment. I: The rectilinear case. Zbl 0904.68115
Deng, Xiaotie; Kameda, Tiko; Papadimitriou, Christos
1998
On the complexity of protein folding (extended abstract). Zbl 1007.68511
Crescenzi, Pierluigi; Goldman, Deborah; Papadimitriou, Christos; Piccolboni, Antonio; Yannakakis, Mihalis
1998
...and 133 more Documents
all top 5

#### Cited by 8,700 Authors

 64 Papadimitriou, Christos Harilaos 37 Paschos, Vangelis Th. 35 Spirakis, Paul G. 30 Eiter, Thomas 30 Fomin, Fedor V. 30 Woeginger, Gerhard Johannes 29 Monnot, Jérôme 26 Bilò, Vittorio 25 Makino, Kazuhisa 24 Ibaraki, Toshihide 23 Bazgan, Cristina 23 Flammini, Michele 23 Yannakakis, Mihalis 22 Epstein, Leah 22 Ito, Takehiro 22 Monien, Burkhard 21 Demaine, Erik D. 21 Deng, Xiao-Tie 21 Wooldridge, Michael J. 21 Yang, Boting 20 Escoffier, Bruno 19 Goldberg, Paul W. 19 Golovach, Petr A. 19 Gottlob, Georg 19 Mavronicolas, Marios 19 Saurabh, Saket 19 Subramani, Krishnan 19 Vazirani, Vijay V. 18 Lohrey, Markus 17 Dereniowski, Dariusz 17 Kratsch, Dieter 17 Moscardelli, Luca 17 Niedermeier, Rolf 17 Pelc, Andrzej 17 Rothe, Jörg-Matthias 17 Szeider, Stefan 16 Demange, Marc 16 Kreinovich, Vladik Yakovlevich 16 Raman, Venkatesh 15 Boros, Endre 15 Deĭneko, Vladimir G. 15 Flocchini, Paola 15 Fotakis, Dimitris A. 15 Hromkovič, Juraj 15 Mitchell, Joseph S. B. 15 Nisse, Nicolas 15 Ye, Yinyu 14 Chen, Jian-er 14 Fraigniaud, Pierre 14 Goldberg, Leslie Ann 14 Gutin, Gregory Z. 14 Heggernes, Pinar 14 Koutsoupias, Elias 14 Mauri, Giancarlo 14 Porreca, Antonio E. 14 Sudborough, Ivan Hal 14 Xu, Yinfeng 13 Arkin, Esther M. 13 Creignou, Nadia 13 Fanelli, Angelo 13 Fearnley, John 13 Monaco, Gianpiero 13 Pardalos, Panos M. 13 Rizzi, Romeo 13 Savani, Rahul 13 Thilikos, Dimitrios M. 13 Wang, Lusheng 12 Bampis, Evripidis 12 Bentz, Cédric 12 Bertsekas, Dimitri Panteli 12 Bodlaender, Hans L. 12 Chatterjee, Krishnendu 12 Christodoulou, George C. 12 Faria, Luerbio 12 Fernau, Henning 12 Gairing, Martin 12 Hansen, Pierre 12 Hoefer, Martin 12 Ilcinkas, David 12 Jiang, Tao 12 Kanj, Iyad A. 12 Mirrokni, Vahab S. 12 Roughgarden, Tim 12 Santoro, Nicola 12 Serna, Maria José 12 Steiner, George 12 Tamir, Tami 12 Tsitsiklis, John N. 12 Uehara, Ryuhei 12 Vollmer, Heribert 11 Anshelevich, Elliot 11 Bose, Prosenjit K. 11 Caragiannis, Ioannis 11 de Figueiredo, Celina M. Herrera 11 Gagliardi Cozman, Fabio 11 Jonsson, Peter A. 11 Lampis, Michael 11 López-Ortiz, Alejandro 11 Lukasiewicz, Thomas 11 Maheshwari, Anil ...and 8,600 more Authors
all top 5

#### Cited in 453 Serials

 803 Theoretical Computer Science 416 Discrete Applied Mathematics 260 European Journal of Operational Research 251 Journal of Computer and System Sciences 240 Algorithmica 228 Information Processing Letters 194 Artificial Intelligence 141 Theory of Computing Systems 127 Information and Computation 114 Operations Research Letters 112 Computers & Operations Research 105 Mathematical Programming. Series A. Series B 105 Journal of Combinatorial Optimization 85 Annals of Operations Research 85 Games and Economic Behavior 83 Discrete Mathematics 69 Annals of Mathematics and Artificial Intelligence 57 Journal of Discrete Algorithms 54 Computational Geometry 49 Discrete Optimization 46 Networks 43 Journal of Scheduling 41 Acta Informatica 39 International Journal of Foundations of Computer Science 36 International Journal of Approximate Reasoning 36 Distributed Computing 35 Discrete & Computational Geometry 35 Linear Algebra and its Applications 34 SIAM Journal on Computing 30 Journal of Global Optimization 29 Information Sciences 29 Mathematics of Operations Research 29 International Journal of Computational Geometry & Applications 27 Annals of Pure and Applied Logic 26 SIAM Journal on Discrete Mathematics 25 Optimization Letters 22 Journal of Combinatorial Theory. Series B 22 Journal of Complexity 22 Cybernetics and Systems Analysis 21 Applied Mathematics and Computation 21 Mathematical Social Sciences 21 SIAM Journal on Algebraic and Discrete Methods 21 Machine Learning 20 International Journal of Game Theory 20 Computational Complexity 20 RAIRO. Operations Research 19 Operations Research 18 Optimization 18 Constraints 17 Journal of Graph Theory 17 The Journal of Symbolic Logic 17 RAIRO. Theoretical Informatics and Applications 17 Computer Science Review 16 Computing 15 Journal of Economic Theory 15 Mathematical Programming 15 Journal of Automated Reasoning 15 International Journal of Algebra and Computation 15 Computational Optimization and Applications 15 4OR 14 Automatica 14 European Journal of Combinatorics 14 International Journal of Computer Mathematics 14 Journal of Applied Logic 13 Combinatorica 13 Pattern Recognition 13 RAIRO. Informatique Théorique et Applications 13 Games 12 Computers & Mathematics with Applications 12 Fuzzy Sets and Systems 12 Mathematical Systems Theory 12 Naval Research Logistics 12 Mathematical and Computer Modelling 12 Mathematical Problems in Engineering 12 Optimization Methods & Software 12 Mathematical Methods of Operations Research 12 Discrete Mathematics, Algorithms and Applications 11 Journal of Statistical Physics 11 Mathematics of Computation 11 Discrete Event Dynamic Systems 11 Formal Methods in System Design 11 Economic Theory 11 The Journal of Artificial Intelligence Research (JAIR) 11 Journal of Heuristics 11 INFORMS Journal on Computing 11 CEJOR. Central European Journal of Operations Research 11 ACM Transactions on Computational Logic 11 Algorithms 10 Journal of Mathematical Economics 10 Journal of Symbolic Computation 10 Journal of Parallel and Distributed Computing 10 Random Structures & Algorithms 10 Data Mining and Knowledge Discovery 10 Logical Methods in Computer Science 9 Journal of Optimization Theory and Applications 9 Advances in Applied Mathematics 9 OR Spektrum 9 International Journal of Production Research 9 Physica D 9 Social Choice and Welfare ...and 353 more Serials
all top 5

#### Cited in 55 Fields

 3,903 Computer science (68-XX) 2,149 Operations research, mathematical programming (90-XX) 1,367 Combinatorics (05-XX) 1,085 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 400 Mathematical logic and foundations (03-XX) 235 Numerical analysis (65-XX) 136 Biology and other natural sciences (92-XX) 127 Information and communication theory, circuits (94-XX) 110 Convex and discrete geometry (52-XX) 103 Statistics (62-XX) 81 Probability theory and stochastic processes (60-XX) 73 Systems theory; control (93-XX) 60 Group theory and generalizations (20-XX) 59 Order, lattices, ordered algebraic structures (06-XX) 59 Quantum theory (81-XX) 51 Linear and multilinear algebra; matrix theory (15-XX) 41 Number theory (11-XX) 33 Calculus of variations and optimal control; optimization (49-XX) 31 Dynamical systems and ergodic theory (37-XX) 31 Statistical mechanics, structure of matter (82-XX) 21 Algebraic geometry (14-XX) 15 Manifolds and cell complexes (57-XX) 14 General topology (54-XX) 12 Operator theory (47-XX) 12 Geometry (51-XX) 11 General and overarching topics; collections (00-XX) 11 General algebraic systems (08-XX) 11 Field theory and polynomials (12-XX) 9 Commutative algebra (13-XX) 9 Differential geometry (53-XX) 8 Measure and integration (28-XX) 7 History and biography (01-XX) 7 Functional analysis (46-XX) 7 Mechanics of particles and systems (70-XX) 5 Real functions (26-XX) 5 Partial differential equations (35-XX) 5 Mechanics of deformable solids (74-XX) 4 Category theory; homological algebra (18-XX) 4 Fluid mechanics (76-XX) 4 Relativity and gravitational theory (83-XX) 3 Ordinary differential equations (34-XX) 3 Approximations and expansions (41-XX) 3 Algebraic topology (55-XX) 3 Optics, electromagnetic theory (78-XX) 3 Geophysics (86-XX) 2 Functions of a complex variable (30-XX) 2 Special functions (33-XX) 2 Integral transforms, operational calculus (44-XX) 2 Global analysis, analysis on manifolds (58-XX) 2 Astronomy and astrophysics (85-XX) 2 Mathematics education (97-XX) 1 Associative rings and algebras (16-XX) 1 Several complex variables and analytic spaces (32-XX) 1 Difference and functional equations (39-XX) 1 Classical thermodynamics, heat transfer (80-XX)

#### Wikidata Timeline

The data are displayed as stored in Wikidata under a Creative Commons CC0 License. Updates and corrections should be made in Wikidata.